Submission #1262913

#TimeUsernameProblemLanguageResultExecution timeMemory
1262913trinhvtuanSum Zero (RMI20_sumzero)C++20
61 / 100
322 ms46272 KiB
#include <bits/stdc++.h> using namespace std; const int N=5e5+5; long long c,d,x,y,z,n,q; int i,j,k; int a[N],lf[N],st[N][22]; struct gv { long long val,vitri; }; gv s[N]; bool cmp(gv x,gv y) { if (x.val<y.val) return true; if (x.val==y.val && x.vitri<y.vitri) return true; return false; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n; for (int i=1;i<=n;i++) { cin>>a[i]; s[i].val=s[i-1].val+a[i]; s[i].vitri=i; } s[n+1].val=0; s[n+1].vitri=0; sort(s+1,s+n+1+1,cmp); for (int i=0;i<=n;i++) lf[i]=-1e9; for (int i=2;i<=n+1;i++) { if (s[i].val==s[i-1].val) { x=s[i].vitri; lf[x]=s[i-1].vitri; } } for (int j=0;j<=20;j++) for (int i=0;i<=n;i++) st[i][j]=-1e9; for (int i=1;i<=n;i++) { lf[i]=max(lf[i-1],lf[i]); st[i][0]=lf[i]; } for (int j=1;j<=20;j++) for (int i=1;i<=n;i++) { if (st[i][j-1]==-1e9) continue; st[i][j]=st[st[i][j-1]][j-1]; } cin>>q; for (int rep=1;rep<=q;rep++) { cin>>x>>y; int u=y; long long ans=0; for (long long j=20;j>=0;j--) { if (st[u][j]!=-1e9 && st[u][j]+1>=x && st[u][j]<y) { ans+=(1<<j); u=st[u][j]; } } cout<<ans<<"\n"; } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...