Submission #753428

#	Time	Username	Problem	Language	Result	Execution time	Memory
753428		lukameladze	Sum Zero (RMI20_sumzero)	C++14	61 / 100	396 ms	26156 KiB

sumzero

# include <bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair <int, int>
#define pb push_back
const int N = 4e5 + 5, inf = 1e9;
int t, n, a[N],par[N][5],nxt[N];
long long pr[N];
map <long long, int> mp;
int tree[N];
void upd(int idx, int val) {
    for (int i = idx; i > 0; i -= i&(-i)) tree[i] = min(tree[i], val);
}
int getmn(int idx) { // suffix query
    int pas = n + 1;
    for (int i = idx; i < N; i += i&(-i)) pas = min(pas, tree[i]);
    return pas;
}
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];
        pr[i] = pr[i - 1] + a[i];
        nxt[i] = -1;
    }
    mp[pr[0]] = 0;
    for (int i = 1; i <= n; i++) {
        if (mp[pr[i]] != 0 || pr[i] == 0) {
            nxt[mp[pr[i]] + 1] = i;
        }
        mp[pr[i]] = i;
    }
    int mn = inf;
    vector <pii> v;
    for (int i = n; i >= 1; i--) {
        if (nxt[i] == -1) continue;
        if (mn <= nxt[i]) continue;
        v.pb({i, nxt[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++) tree[i] = n + 1;
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        par[i + 1][0] = getmn(v[i].s + 1);
        upd(v[i].f, 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 = getmn(le);
        if (st_idx == n + 1 || v[st_idx - 1].f > ri) {
            cout<<0<<"\n"; continue;
        }
        int cur = st_idx;
        int ans = 0;
        for (int i = 4; i >= 0; i--) {
        	for (int it = 1; it <= 8; it++) {
        		if (par[cur][i] != n + 1 && v[par[cur][i] - 1].f <= ri) {
        			cur = par[cur][i];
        			ans += (1<<(3*i));
				}
			}
        }
        if (v[cur - 1].s <= ri) ans++;
        cout<<ans<<"\n";
    }
}

Compilation message (stderr)

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

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