 # Why doesn't my code pass sample input?

Problem: https://codeforces.com/contest/862/problem/E.
My code follows the same logic as the official editorial and the USACO Guide solutions. I read all solutions and understood them before implementing it myself.

I tried printing out the values of variables, but everything seems good. However, the code gives the wrong output on the sample test case.

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int MX = 1e18;
using vi = vector<int>;
#define F0R(i,n) for(int i=0;i<n;++i)

int32_t main()
{
int n, m, q;
cin >> n >> m >> q;

vi A(n), B(m);
auto sign_a = [&](int x){ return x%2==0?1:-1; };
auto sign_b = [&](int x){ return -sign_a(x); };

int Asum = 0;
F0R(i,n){
cin >> A[i];
Asum += sign_a(i)*A[i];
}

F0R(i,m) cin >> B[i];
vi Bsum(m); multiset<int> Bs;
F0R(i,n){
Bsum += sign_b(i)*B[i];
}
Bs.insert(Bsum);
F0R(j,m-n){
// Bsum[j] = sum of n length sliding window starting from B[j]
// -B +B -B +B...
//       -B +B -B +B...
Bsum[j+1] = -(Bsum[j]+B[j]) + sign_b(n-1)*B[j+n];
Bs.insert(Bsum[j+1]);
}

int l, r, x;
auto ans = [&]() -> void{
// find minimum value of Asum + Bsum[j]
auto ub = Bs.upper_bound(-Asum);
int ret = MX;
if (ub != Bs.end()) ret = min(ret, abs(Asum+*ub));
if (ub != Bs.begin()) ret = min(ret, abs(Asum+*--ub));
cout << ret << '\n';
};
ans();
while(q--){
cin >> l >> r >> x;
l--, r--;
if ((r-l)%2==0){
Asum += sign_a(l)*A[l];
}
ans();
}
}


Can you please explain this? Thanks!

I tried printing out the values of variables, but everything seems good

Are you sure you printed out everything?

Fixed.
In this line:

if ((r-l)%2==0){
Asum += sign_a(l)*A[l];
}


I had to actually add sign_a(l)*x, since we add x alternatingly to the interval A[i], i \in [l,r].
AC.

2 Likes

Also, why do we use a multiset to store the Bsums? Wouldn’t the following suffice in the ans function?

sort(Bsum.begin(),Bsum.end());
auto ans = [&]() -> void{
// find minimum value of Asum + Bsum[j]
auto ub = upper_bound(Bsum.begin(),Bsum.end(),-Asum);
int ret = INF;
if (ub != Bsum.end()) ret = min(ret, abs(Asum+*ub));
if (ub != Bsum.begin()) ret = min(ret, abs(Asum+*--ub));
cout << ret << '\n';
};


However, this doesn’t pass. The only time I use multiset Bs is to find the closest element of Bsum to -Asum. The Bsum array never changes after initially computing all values and sorting. Can you please explain this?

I am not fluent in C++, but your idea should be correct. Keeping a sorted array and binarysearching should be ok. It’s something to do with your implementation(are you finding upper and lower bound)?