Submission #646898

#TimeUsernameProblemLanguageResultExecution timeMemory
646898DobromirAngelovSum Zero (RMI20_sumzero)C++14
61 / 100
269 ms21928 KiB
#include<bits/stdc++.h> #define endl '\n' using namespace std; const int MAXN=4e5+5; const int INF=1e9+5; int n,q; pair<long long,int> pref[MAXN]; //int previous[MAXN]; int prv[MAXN]; int nxt_l[MAXN], r[MAXN]; int ans[MAXN]; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for(int i=1;i<=n;i++) cin>>pref[i].first; for(int i=1;i<=n;i++) { pref[i].first=pref[i-1].first+pref[i].first; pref[i].second=i; } sort(pref,pref+n+1); for(int i=0;i<=n;i++) nxt_l[i]=INF; for(int i=0;i<=n;i++) { if(pref[i].first==pref[i+1].first) nxt_l[pref[i].second]=pref[i+1].second; } int ptr=n; for(int i=n;i>=0;i--) { while(ptr>=nxt_l[i]) { pref[ptr].second=i+1; ptr--; } } for(;ptr>=0;ptr--) pref[ptr].second=0; cin>>q; for(int i=1;i<=q;i++) { cin>>nxt_l[i]>>r[i]; } for(int lg=18;lg>=0;lg--) { for(int i=1;i<=n;i++) prv[i]=pref[i].second; for(int j=1;j<=lg;j++) { for(int i=n;i>0;i--) { if(prv[i]>1) prv[i]=prv[prv[i]-1]; else prv[i]=0; } } for(int i=1;i<=q;i++) { if(nxt_l[i]<=r[i] && prv[r[i]]>=nxt_l[i]) { ans[i]+=(1<<lg); r[i]=prv[r[i]]-1; } } } for(int i=1;i<=q;i++) cout<<ans[i]<<endl; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...