Submission #1312441

#	Time	Username	Problem	Language	Result	Execution time	Memory
1312441		seriousgrey	Sum Zero (RMI20_sumzero)	C++20	0 / 100	1 ms	1080 KiB

sumzero

#pragma GCC optimize("O3,unroll-loops,no-stack-protector,fast-math")
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;

#define OmPatel() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define fr(i,n) for(int i=0;i<n;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define rep(i,a,b) for(int i=a;i<=b;i--)
#define all(x) (x).begin(), (x).end()

const int LOG = 19; // 2^19 > 4e5

int main(){
    OmPatel();

    int n; cin >> n;
    vi c(n);
    vector<ll> pref(n);

    unordered_map<ll, vi> mpp;
    mpp.reserve(n*2);
    mpp.max_load_factor(0.7);
    mpp[0].push_back(-1);

    fr(i,n){
        cin >> c[i];
        pref[i] = c[i] + (i ? pref[i-1] : 0LL);
        mpp[pref[i]].push_back(i);
    }

    // nxt[i]: earliest j >= i with sum(i..j)=0
    vi nxt(n);
    fr(i,n){
        ll need = (i ? pref[i-1] : 0LL);
        if(!mpp.count(need)){
            nxt[i] = n;
        } else {
            auto &v = mpp[need];
            auto it = lower_bound(all(v), i);
            nxt[i] = (it == v.end() ? n : *it);
        }
    }

    // best[i]: earliest finishing interval among starts >= i
    vi best(n+1, n);
    per(i,n-1,0) best[i] = min(best[i+1], nxt[i]);

    // go[i]: next position after taking that interval
    vi go(n+1, n);
    fr(i,n) if(best[i] != n) go[i] = best[i] + 1;

    // binary lifting on go[]
    vector<vi> pos(LOG, vi(n+1, n));
    fr(i,n+1) pos[0][i] = go[i];

    rep(k,1,LOG-1){
        fr(i,n+1){
            int mid = pos[k-1][i];
            pos[k][i] = (mid < n ? pos[k-1][mid] : n);
        }
    }

    int q; cin >> q;
    while(q--){
        int l, r; cin >> l >> r;
        --l; --r;

        int p = l, ans = 0;
        per(k,LOG-1,0){
            if(p == n) break;
            int np = pos[k][p];
            if(np <= r+1 && np != n){
                ans += (1 << k);
                p = np;
            }
        }
        cout << ans << '\n';
    }
}

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:11:20: warning: iteration 2147483649 invokes undefined behavior [-Waggressive-loop-optimizations]
   11 | #define rep(i,a,b) for(int i=a;i<=b;i--)
      |                    ^~~
sumzero.cpp:59:5: note: in expansion of macro 'rep'
   59 |     rep(k,1,LOG-1){
      |     ^~~
sumzero.cpp:11:33: note: within this loop
   11 | #define rep(i,a,b) for(int i=a;i<=b;i--)
      |                                 ^
sumzero.cpp:59:5: note: in expansion of macro 'rep'
   59 |     rep(k,1,LOG-1){
      |     ^~~

• Subtask 1: 0 / 22
• Subtask 2: 0 / 39
• Subtask 3: 0 / 39