Submission #715770

#	Time	Username	Problem	Language	Result	Execution time	Memory
715770		snpmrnhlol	Sum Zero (RMI20_sumzero)	C++17	61 / 100	1087 ms	45856 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
int v[400001];
int ps[400001];
int jump[400001][17];
map <int,int> f;
int main(){
    int n,i,nr = 2e9,j,l,r;
    cin>>n;
    for(i = 0;i < n;i++){
        cin>>v[i];
        ps[i + 1] = ps[i] + v[i];
    }
    f[ps[n]] = n;
    for(i = n - 1;i >= 0;i--){
        if(f[ps[i]] != 0){
            nr = min(nr,f[ps[i]]);
        }
        jump[i][0] = (nr==2e9?n + 1:nr);
        f[ps[i]] = i;
    }
    for(i = 1;i <= 16;i++){
        for(j = 0;j < n;j++){
            jump[j][i] = (jump[j][i - 1] >= n?n + 1:jump[jump[j][i - 1]][i - 1]);
        }
    }
    int q;
    cin>>q;
    for(i = 0;i < q;i++){
        cin>>l>>r;l--;r--;
        int cur = l,ans = 0;
        for(j = 16;j >= 0;j--){
            if(cur != n && jump[cur][j] <= r + 1){
                cur = jump[cur][j];
                ans+=(1<<j);
            }
        }
        cout<<ans<<'\n';
    }
    return 0;
}

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