Submission #646864

#TimeUsernameProblemLanguageResultExecution timeMemory
646864DobromirAngelovSum Zero (RMI20_sumzero)C++14
0 / 100
2 ms852 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAXN=4e5+5; const int INF=1e9+5; int n,q; int a[MAXN]; long long pref[MAXN]; int nxt[MAXN]; int prv[20][MAXN]; map<int,int> m; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>a[i]; for(int i=1;i<=n;i++) { pref[i]=pref[i-1]+a[i];//cout<<pref[i]<<" "; }//cout<<endl; for(int i=n;i>=0;i--) { if(!m[pref[i]]) nxt[i]=INF; /// else nxt[i]=m[pref[i]]; m[pref[i]]=i; //cout<<nxt[i]<<" "; }//cout<<endl; delete []pref; int ptr=n; ///memset(prv,-1,sizeof(prv)); for(int i=n;i>=0;i--) { while(ptr>=nxt[i]) { prv[0][ptr]=i+1; ptr--; } } for(;ptr>=0;ptr--) prv[0][ptr]=-1; delete []nxt; //for(int i=1;i<=n;i++) cout<<prv[0][i]<<" "; cout<<endl; int log_n=0; for(int i=1;(1<<i)<=n;i++) { for(int j=1;j<=n;j++) { if(prv[i-1][j]>1) prv[i][j]=prv[i-1][prv[i-1][j]-1]; else prv[i][j]=-1; //cout<<prv[i][j]<<" "; }//cout<<endl; if(prv[i][n]==-1) break; log_n=i; } cin>>q; for(int i=0;i<q;i++) { int l,r; cin>>l>>r; int j=log_n; int ans=0; for(;;) { if(l>r || j<0) break; if(prv[j][r]>=l) { ans+=(1<<j); r=prv[j][r]-1; } j--; /// } cout<<ans<<endl; } return 0; }

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:36:10: warning: deleting array 'pref'
   36 | delete []pref;
      |          ^~~~
sumzero.cpp:50:10: warning: deleting array 'nxt'
   50 | delete []nxt;
      |          ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...