Submission #1136172

#	Time	Username	Problem	Language	Result	Execution time	Memory
1136172		quannnguyen2009	Sum Zero (RMI20_sumzero)	C++20	100 / 100	156 ms	18920 KiB

sumzero

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;
const int N=4e5+5;

int n, Q, i, k, j;
int a[N], nxt[N], ans[N];
ii q[N];
long long sum;
unordered_map<long long, int> mp;

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for (i=1; i<=n; i++) cin >> a[i];
    mp[0] = n+1; nxt[n+1] = n+2; nxt[n+2] = n+2;
    for (i=n; i>=1; i--) {
        sum += a[i];
        if (mp.find(sum)==mp.end()) nxt[i] = nxt[i+1];
        else nxt[i] = min(mp[sum], nxt[i+1]);
        mp[sum] = i;
    }
    cin >> Q;
    for (int i=0; i<Q; i++) cin >> q[i].fi >> q[i].se;
    for (k=18; k>=0; k--) {
        for (i=1; i<=n+2; i++) a[i]=nxt[i];
        for (j=1; j<=k; j++) {
            for (i=1; i<=n+2; i++) a[i] = a[a[i]];
        }
        for (i=0; i<Q; i++) {
            if(a[q[i].fi]<=q[i].se+1) {
                ans[i] += (1<<k);
                q[i].fi = a[q[i].fi];
            }
        }
    }
    for(i=0; i<Q; i++) cout << ans[i] << "\n";
}

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