Submission #646781

#	Time	Username	Problem	Language	Result	Execution time	Memory
646781		k_balint31415	Sum Zero (RMI20_sumzero)	C++14	61 / 100	525 ms	52128 KiB

sumzero

#include <bits/stdc++.h>
using namespace std;
const int c=4e5+5;
typedef long long ll;

int n,q;
ll arr[c];
int seg[c];
map<ll,int> mp;

int up[c][20];

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    cin>>n; mp[0]=0;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        arr[i]+=arr[i-1];
        if(mp.find(arr[i]) != mp.end()){
            seg[i]=mp[arr[i]]+1;
        }
        else seg[i]=-1;
        mp[arr[i]]=i;
        up[i][0]=c;
    }

    up[n+1][0]=n+2; up[n+2][0]=n+2;
    for(int i=n;i>=1;i--){
        if(seg[i]!=-1) up[seg[i]][0]=i+1;
        up[i][0]=min(up[i][0],up[i+1][0]);
    }

    for(int j=1;j<20;j++){
        for(int i=1;i<=n+2;i++){
            up[i][j]=up[up[i][j-1]][j-1];
        }
    }

    cin>>q;
    while(q--){
        int l,r; cin>>l>>r;
        int ans=0; int cur=l;
        for(int i=19;i>=0;i--){
            if(up[cur][i]<=r+1){
                cur=up[cur][i];
                ans+=1<<i;
            }
        }
        cout << ans << '\n';
    }
}

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