Submission #1225698

#TimeUsernameProblemLanguageResultExecution timeMemory
1225698MuhammadSaramSum Zero (RMI20_sumzero)C++20
61 / 100
335 ms34728 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long const int M = 4e5+5, lg = 19; int nxt[M][3],ans[M],a[M]; map<ll,pair<int,int>> ind; int main() { ios::sync_with_stdio(0); cin.tie(NULL), cout.tie(NULL); int n; cin>>n; ll su=0; ind[su]={-1,-1}; for (int i=1;i<=n;i++) cin>>a[i],su+=a[i],ind[su]={-1,-1}; set<int> se={n+1}; for (int i=n+1;i>=1;i--) { ind[su].second=ind[su].first,ind[su].first=i-1; if (~ind[su].second) se.insert(ind[su].second); nxt[i][2]=*se.begin(); su-=a[i-1]; } ind.clear(),se.clear(); nxt[n+2][2]=n+1; int q; cin>>q; int l[q],r[q]; for (int i=0;i<q;i++) cin>>l[i]>>r[i]; for (int lim=lg-1;lim>=0;lim--) { for (int i=1;i<=n+2;i++) nxt[i][0]=nxt[i][2]; for (int p=1;p<=lim;p++) for (int i=1;i<=n+2;i++) nxt[i][p%2]=nxt[nxt[i][1-p%2]+1][1-p%2]; for (int i=0;i<q;i++) if (nxt[l[i]][lim%2]<=r[i]) ans[i]+=(1<<lim),l[i]=nxt[l[i]][lim%2]+1; } for (int i=0;i<q;i++) cout<<ans[i]<<'\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...