Why doesn't my code pass sample input?

Problems and Contests
#1

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[0] += sign_b(i)*B[i];
    }
    Bs.insert(Bsum[0]);
    F0R(j,m-n){
        // Bsum[j] = sum of n length sliding window starting from B[j]
        // -B[0] +B[1] -B[2] +B[3]...
        //       -B[1] +B[2] -B[3] +B[4]...
        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!

#2

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

Are you sure you printed out everything?

#3

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
#4

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?

#5

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)?