Submission #1225657

#TimeUsernameProblemLanguageResultExecution timeMemory
1225657MuhammadSaramSum Zero (RMI20_sumzero)C++20
22 / 100
95 ms23364 KiB
#include <bits/stdc++.h> using namespace std; #define int long long const int M = 4e5+5, lg = 19; int nxt[M][lg],a[M],pre[M]; map<int,vector<int>> ind; signed main() { ios::sync_with_stdio(0); cin.tie(NULL), cout.tie(NULL); int n; cin>>n; for (int i=1;i<=n;i++) cin>>a[i],pre[i]=pre[i-1]+a[i]; for (int i=n;i>=0;i--) ind[pre[i]].push_back(i); set<int> se={n+1}; for (auto [x,v]:ind) if (v.size()>1) se.insert(v[v.size()-2]); for (int i=1;i<=n+1;i++) { nxt[i][0]=*se.begin(); ind[pre[i-1]].pop_back(); int m=ind[pre[i-1]].size(); if (m) se.erase(ind[pre[i-1]].back()); if (m>1) se.insert(ind[pre[i-1]][m-2]); } nxt[n+2][0]=n+1; for (int p=1;p<lg;p++) for (int i=1;i<=n+2;i++) nxt[i][p]=nxt[nxt[i][p-1]+1][p-1]; int q; cin>>q; while (q--) { int l,r; cin>>l>>r; int ans=0; for (int p=lg-1;p>=0;p--) if (nxt[l][p]<=r) ans+=(1<<p),l=nxt[l][p]+1; cout<<ans<<'\n'; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...