Submission #1225748

#TimeUsernameProblemLanguageResultExecution timeMemory
1225748Muhammad_AneeqSum Zero (RMI20_sumzero)C++20
61 / 100
526 ms26032 KiB
#include <iostream> #include <map> #include <vector> #include <deque> #include <set> #include <algorithm> using namespace std; int const N=4e5+2,lg=19; int nx[N],pre[N],ans[N],l[N],r[N]; int calc[N][3]={}; inline void solve() { int n,q; cin>>n; map<long long,int>ind; ind[0]=-1; for (int i=0;i<n;i++) cin>>pre[i]; long long sm=0; for (int i=0;i<n;i++) { nx[i]=-1; sm+=pre[i]; if (ind.find(sm)!=ind.end()) { pre[i]=ind[sm]+1; nx[ind[sm]+1]=i; } ind[sm]=i; } sm=0; ind.clear(); for (int i=0;i<=n+1;i++) for (int j=0;j<3;j++) calc[i][j]=n; nx[n]=n+10; set<pair<int,int>>s; for (int i=n-1;i>=0;i--) { int fr=nx[i]; nx[i]=nx[i+1]; if (fr!=-1) { int f=nx[fr+1]; nx[i]=min(nx[i],fr); s.insert({fr,i}); } if (s.size()==0) continue; calc[i][2]=(*begin(s)).first; } s.clear(); cin>>q; for (int i=1;i<=q;i++) { cin>>l[i]>>r[i]; l[i]--;r[i]--; ans[i]=0; } for (int cur=lg-1;cur>=0;cur--) { for (int j=0;j<n;j++) calc[j][0]=calc[j][2]; for (int i=1;i<=cur;i++) { for (int j=0;j<n;j++) calc[j][1]=calc[min(n,calc[j][0]+1)][0]; for (int j=0;j<n;j++) calc[j][0]=calc[j][1]; } for (int i=1;i<=q;i++) { if (calc[l[i]][0]<=r[i]) { ans[i]+=(1<<cur); l[i]=calc[l[i]][0]+1; } } } for (int i=1;i<=q;i++) cout<<ans[i]<<endl; } signed main() { ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL); int t=1; for (int i=1;i<=t;i++) { solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...