Submission #1099163

#	Time	Username	Problem	Language	Result	Execution time	Memory
1099163		bonk	Sum Zero (RMI20_sumzero)	C++17	61 / 100	108 ms	65536 KiB

sumzero

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int LOG = 19;
const int MAX_N = 4e5 + 5;
ll a[MAX_N], pref[MAX_N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int N; cin >> N;
    vector<int>nxt(N + 5, N + 2), suff(N + 5, N + 2);
    vector<vector<int>>up(N + 5, vector<int>(LOG, N + 2));
    map<ll, int>lst;

    lst[0] = 1;
    for(int i = 1; i <= N; i++){
        cin >> a[i];
        pref[i] = pref[i - 1] + a[i]; 
        if(lst.count(pref[i])){
            nxt[lst[pref[i]]] = i + 1;
        }
        lst[pref[i]] = i + 1;
    }

    for(int i = N; i >= 1; i--){
        suff[i] = min(suff[i + 1], nxt[i]);
        up[i][0] = suff[i];
        for(int j = 1; j < LOG; j++){
            up[i][j] = up[up[i][j - 1]][j - 1];
        }
    }

    int Q; cin >> Q;
    while(Q--){
        int L, R; cin >> L >> R;
        int ans = 0;
        for(int j = LOG - 1; j >= 0; j--){
            if(up[L][j] <= R + 1){
                ans += (1<<j);
                L = up[L][j];
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

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