Submission #1242011

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242011		AMnu	Sum Zero (RMI20_sumzero)	C++20	61 / 100	214 ms	35724 KiB

sumzero

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> pli;

const int MAXN = 4e5+5;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N;
    cin >> N;
    int par[N+2], sub[N+2], big[N+2], rot[N+2], dep[N+2];
	pli P[N+2];
	vector <int> ch[N+2];
    for (int i=0;i<=N+1;i++) {
        par[i] = N+1;
        big[i] = N+2;
        rot[i] = -1;
        sub[i] = 0;
    }
    P[0] = {0,0};
    for (int i=1;i<=N;i++) {
        cin >> P[i].fi;
        P[i].fi += P[i-1].fi;
        P[i].se = i;
    }
    sort(P,P+N+1);
    for (int i=1;i<=N;i++) {
        if (P[i].fi == P[i-1].fi) {
            par[P[i-1].se] = P[i].se;
        }
    }
    dep[N+1] = 0;
    for (int i=N;i>=0;i--) {
        par[i] = min(par[i],par[i+1]);
        dep[i] = dep[par[i]]+1;
    }
    for (int i=0;i<=N;i++) {
        sub[i]++;
        sub[par[i]] += sub[i];
        if (sub[i] > sub[big[par[i]]]) {
            big[par[i]] = i;
        }
    }
    for (int i=N+1;i>=0;i--) {
        if (rot[i] != -1) continue;
        int j = i;
        while (j != N+2) {
            rot[j] = i;
            ch[i].push_back(j);
            j = big[j];
        }
        reverse(ch[i].begin(),ch[i].end());
    }
    int Q;
    cin >> Q;
    while (Q--) {
		int L, R;
        cin >> L >> R;
        L--;
        int ans = dep[L];
        while (par[rot[L]] <= R) {
            L = par[rot[L]];
        }
        int x = upper_bound(ch[rot[L]].begin(),ch[rot[L]].end(),R) - ch[rot[L]].begin() - 1;
        x = ch[rot[L]][x];
        cout << ans - dep[x] << "\n";
    }
}

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