Submission #1225751

#TimeUsernameProblemLanguageResultExecution timeMemory
1225751Muhammad_AneeqSum Zero (RMI20_sumzero)C++20
61 / 100
525 ms22936 KiB
#include <iostream> #include <map> #include <vector> #include <deque> #include <set> #include <algorithm> using namespace std; int const N=4e5+2,lg=19; int 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>>ans[i]; long long sm=0; for (int i=0;i<n;i++) { r[i]=-1; sm+=ans[i]; if (ind.find(sm)!=ind.end()) r[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; r[n]=n+10; set<int>s; for (int i=n-1;i>=0;i--) { int fr=r[i]; r[i]=r[i+1]; if (fr!=-1) { int f=r[fr+1]; r[i]=min(r[i],fr); s.insert(fr); } if (s.size()==0) continue; calc[i][2]=(*begin(s)); } 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...