Submission #1137954

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137954		AMnu	Sum Zero (RMI20_sumzero)	C++20	61 / 100	55 ms	11336 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<pii,ll> piii;
typedef pair<pii,pii> piiii;

const int MAXN = 1e5+5, LOG = 17;

int N, Q, A, L, R, par[MAXN][LOG];
ll P[MAXN];
map <ll,int> last;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> N;
    for (int i=1;i<=N;i++) {
        cin >> A;
        P[i] = P[i-1]+A;
    }
    L = N+1;
    for (int i=0;i<LOG;i++) {
        par[L][i] = L;
    }
    for (int i=N;i>=0;i--) {
        if (last.count(P[i])) {
            L = min(L,last[P[i]]);
        }
        last[P[i]] = i;
        par[i][0] = L;
        for (int j=1;j<LOG;j++) {
            par[i][j] = par[par[i][j-1]][j-1];
        }
    }
    cin >> Q;
    for (int i=1;i<=Q;i++) {
        cin >> L >> R;
        L--;
        A = 0;
        for (int j=LOG-1;j>=0;j--) {
            if (par[L][j] <= R) {
                A += 1<<j;
                L = par[L][j];
            }
        }
        cout << A << "\n";
    }
}

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