제출 #646888

#제출 시각아이디문제언어결과실행 시간메모리
646888DobromirAngelovSum Zero (RMI20_sumzero)C++14
61 / 100
301 ms25052 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 previous[MAXN]; int prv[MAXN]; int l[MAXN], r[MAXN]; int ans[MAXN]; map<long long,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>>pref[i]; // pref[i]=a[i] for(int i=1;i<=n;i++) { pref[i]=pref[i-1]+pref[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; int ptr=n; ///memset(prv,-1,sizeof(prv)); for(int i=n;i>=0;i--) { while(ptr>=nxt[i]) { previous[ptr]=i+1; ptr--; } } //for(;ptr>=0;ptr--) prv[0][ptr]=-1; //for(int i=1;i<=n;i++) cout<<prv[0][i]<<" "; cout<<endl; cin>>q; for(int i=1;i<=q;i++) { cin>>l[i]>>r[i]; } for(int lg=18;lg>=0;lg--) { for(int i=1;i<=n;i++) prv[i]=previous[i]; 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(l[i]<=r[i] && prv[r[i]]>=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...