Submission #891568

#TimeUsernameProblemLanguageResultExecution timeMemory
891568khoquennguoiminhthuongSum Zero (RMI20_sumzero)C++17
0 / 100
2 ms4444 KiB
#include<bits/stdc++.h> using namespace std; int n,q; int a[400005]; map<long long,int>dd; int l[400005]; int nxt[400005]; int pa[20][400005]; int main() { freopen("sum0.inp","r",stdin); freopen("sum0.out","w",stdout); ios_base::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++)l[i]=n+1; long long sum=0; dd[0]=n; for(int i=n;i>=1;i--) { sum+=a[i]; if(dd.count(sum)) { l[i]=dd[sum]; } dd[sum]=i-1; } l[n+1]=n+2; int pos=n+1; int minn=2e9; for(int i=n;i>=1;i--) { if(minn>=l[i]) { minn=l[i]; pos=i; } nxt[i]=pos; } for(int i=1;i<=n;i++) { pa[0][i]=l[nxt[i]]+1; } for(int i=1;i<=18;i++) for(int j=1;j<=n;j++) { pa[i][j]=pa[i-1][pa[i-1][j]]; } cin>>q; while(q--) { int l,r; cin>>l>>r; int ans=0; for(int i=18;i>=0;i--) { if(pa[i][l]!=0&&pa[i][l]-1<=r) { ans+=(1<<i);l=pa[i][l]; } } cout<<ans<<'\n'; } return 0; }

Compilation message (stderr)

sumzero.cpp: In function 'int main()':
sumzero.cpp:12:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   12 | freopen("sum0.inp","r",stdin);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
sumzero.cpp:13:8: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   13 | freopen("sum0.out","w",stdout);
      | ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...