Submission #1225746

#TimeUsernameProblemLanguageResultExecution timeMemory
1225746Muhammad_AneeqSum Zero (RMI20_sumzero)C++20
61 / 100
533 ms29132 KiB
#include <iostream> #include <map> #include <vector> #include <deque> #include <set> #include <algorithm> using namespace std; int const N=4e5+10,lg=19; int nx[N],mn[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; int a[n]; for (auto& i:a) cin>>i; long long sm=0; for (int i=0;i<n;i++) { nx[i]=-1; sm+=a[i]; if (ind.find(sm)!=ind.end()) { pre[i]=ind[sm]+1; nx[ind[sm]+1]=i; } ind[sm]=i; } ind.clear(); for (int i=0;i<=n+1;i++) for (int j=0;j<3;j++) calc[i][j]=n; mn[n]=n+10; set<pair<int,int>>s; for (int i=n-1;i>=0;i--) { mn[i]=mn[i+1]; if (nx[i]!=-1) { int f=mn[nx[i]+1]; mn[i]=min(mn[i],nx[i]); s.insert({nx[i],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...