제출 #646891

#제출 시각아이디문제언어결과실행 시간메모리
646891DobromirAngelovSum Zero (RMI20_sumzero)C++14
0 / 100
3 ms468 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]; pair<long long,int> a_pref_prev[MAXN]; //int nxt[MAXN]; //int previous[MAXN]; int prv[MAXN]; int nxt_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>>a_pref_prev[i].first; for(int i=1;i<=n;i++) { a_pref_prev[i].first=a_pref_prev[i-1].first+a_pref_prev[i].first; a_pref_prev[i].second=i; } sort(a_pref_prev+1,a_pref_prev+n+1); for(int i=1;i<=n;i++) { if(a_pref_prev[i].first==a_pref_prev[i+1].first) nxt_l[a_pref_prev[i].second]=a_pref_prev[i+1].second; else nxt_l[a_pref_prev[i].second]=INF; } /*for(int i=n;i>=0;i--) { if(!m[a_pref_prev[i]]) nxt_l[i]=INF; else nxt_l[i]=m[a_pref_prev[i]]; m[a_pref_prev[i]]=i; }*/ int ptr=n; for(int i=n;i>=0;i--) { while(ptr>=nxt_l[i]) { a_pref_prev[ptr].second=i+1; ptr--; } } 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]=a_pref_prev[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...