Submission #1225710

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