Submission #1225701

#TimeUsernameProblemLanguageResultExecution timeMemory
1225701Muhammad_AneeqSum Zero (RMI20_sumzero)C++20
0 / 100
194 ms9868 KiB
#include <iostream> #include <map> #include <vector> #include <deque> #include <set> #include <algorithm> using namespace std; #define int long long int const N=5e3+10; int par[N],nx[N],mn[N],pre[N],ans[N],ans1[N]; deque<int>st[N],en[N]; vector<pair<int,int>>qu[N]={}; int root(int n) { return (par[n]==n?n:(par[n]=root(par[n]))); } set<pair<int,int>>s; void merge(int u,int v) { u=root(u); v=root(v); while (st[u].size()&&st[u][0]<nx[v]&&en[u][0]>nx[v]) { st[u].pop_front(); en[u].pop_front(); } if ((st[u].size()&&st[u][0]>nx[v])||st[u].size()==0) { st[u].push_front(v); en[u].push_front(nx[v]); par[v]=u; } else merge(v,v); } 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++) par[i]=i; 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; } cin>>q; for (int i=0;i<q;i++) { int l,r; cin>>l>>r; l--;r--; qu[l].push_back({r,i}); } mn[n]=n+10; 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 (f>=n) merge(i,i); else { int g=pre[f]; merge(g,i); } } for (auto [j,k]:qu[i]) { if (s.size()==0) { ans[k]=0; continue; } int f=(*begin(s)).second; f=root(f); int z=upper_bound(begin(en[f]),end(en[f]),j)-begin(en[f]); ans[k]=z; set<int>s; s.insert(0); int y=0; ans1[k]=0; for (int l=i;l<=j;l++) { y+=a[l]; if (s.find(y)!=s.end()) { ans1[k]++; s={}; y=0; } s.insert(y); } } } for (int i=0;i<q;i++) { if (ans1[i]>ans[i]) exit(-1); 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...