# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
467960 | MilosMilutinovic | Sum Zero (RMI20_sumzero) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=400005;
const int L=10;
int st[L][N];
void Build(int n){
for(int i=0;i<N;i++){
for(int j=0;j<L;j++)st[j][i]=N-2;
}
ll sum=0;
was[0]=0;
int x;
for(int i=1;i<=n;i++){
scanf("%i",&x);
sum+=x;
if(was.count(sum)){
st[0][was[sum]+1]=i;
}
was[sum]=i;
}
int mn=N-1;
for(int i=n;i>=1;i--)st[0][i]=min(st[0][i+1],st[0][i]);
for(int i=1;i<L;i++){
for(int j=1;j<=n;j++){
st[i][j]=st[i-1][st[i-1][j]+1];
}
}
}
int main(){
int n;scanf("%i",&n);
Build(n);
int q;scanf("%i",&q);
int l,r,ans=0;
while(q--){
scanf("%i%i",&l,&r);
ans=0;
for(int i=L-1;i>=0;i--){
if(st[i][l]<=r)ans+=(1<<i),l=st[i][l]+1;
}
printf("%i\n",ans);
}
return 0;
}