Submission #753437

#	Time	Username	Problem	Language	Result	Execution time	Memory
753437		lukameladze	Sum Zero (RMI20_sumzero)	C++14	61 / 100	420 ms	25584 KiB

sumzero

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pb push_back
const int N = 4e5 + 2, inf = 1e9;
int t, n, a[N],par[N][5],nxt[N],frst[N];
long long pr;
map <long long, int> mp;
main() {
    std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n;
    for (int i = 1; i <= n; i++) {
        cin>>a[i];
        nxt[i] = -1;
    }
    mp[pr] = 0;
    for (int i = 1; i <= n; i++) {
    	pr += a[i];
        if (mp[pr] != 0 || pr == 0) { nxt[mp[pr] + 1] = i; }
        mp[pr] = i;
    }
    int mn = inf;
    vector <int> v;
    for (int i = n; i >= 1; i--) {
        if (nxt[i] == -1) continue;
        if (mn <= nxt[i]) continue;
        v.pb(i);
        mn = min(mn, nxt[i]);
    }
    sort(v.begin(), v.end()); // if (l[i] > l[j]) ---> r[i] > r[j]
    int m = v.size();
    for (int i = 1; i < N; i++) frst[i] = n + 1;
    for (int i = (int)v.size() - 1; i >= 0;i--){
    	frst[v[i]] = i + 1;
	}
	frst[n + 1] = n + 1;
	for (int i = n; i >= 1; i--) {
		frst[i] = min(frst[i], frst[i + 1]);
	}
	for (int i = (int)v.size() - 1; i >= 0; i--) {
        par[i + 1][0] = frst[nxt[v[i]] + 1];
    }
    for (int j = 1; j <= 4; j++) {
        for (int i = 1; i <= m; i++) {
        	int cur = i;
        	for (int it = 1; it <= 4; it++) {
        		if (par[cur][j - 1] == n + 1 || cur == n + 1) {
        			cur = n + 1; break;
				}
				cur = par[par[cur][j - 1]][j - 1];
			}
			par[i][j] = cur;
        }
    }
    int q; cin>>q;
    while (q--) {
        int le, ri;
        cin>>le>>ri;
        int st_idx = frst[le];
        if (st_idx == n + 1 || v[st_idx - 1] > ri) {
            cout<<0<<"\n"; continue;
        }
        int cur = st_idx, ans = 0;
        for (int i = 4; i >= 0; i--) {
        	for (int it = 1; it <= 8 + (i == 4 ? 24 : 0); it++) {
        		if (par[cur][i] != n + 1 && v[par[cur][i] - 1] <= ri) {
        			cur = par[cur][i];
        			ans += (1<<(3*i));
				}
			}
        }
        if (nxt[v[cur - 1]] <= ri) ans++;
        cout<<ans<<"\n";
    }
}

Compilation message (stderr)

sumzero.cpp:10:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   10 | main() {
      | ^~~~

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