Submission #1137955

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137955		AMnu	Sum Zero (RMI20_sumzero)	C++20	61 / 100	70 ms	6216 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, EXP = 26, LOG = 4;

int N, Q, A, L, R, par[MAXN][LOG], expo[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;
    expo[0] = 1;
    for (int i=0;i<LOG;i++) {
        par[L][i] = L;
        if (i) expo[i] = expo[i-1]*EXP;
    }
    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++) {
            int x = i;
            for (int k=0;k<EXP;k++) {
                x = par[x][j-1];
            }
            par[i][j] = x;
        }
    }
    cin >> Q;
    for (int i=1;i<=Q;i++) {
        cin >> L >> R;
        L--;
        A = 0;
        for (int j=LOG-1;j>=0;j--) {
            while (par[L][j] <= R) {
                A += expo[j];
                L = par[L][j];
            }
        }
        cout << A << "\n";
    }
}

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