Submission #815187

#TimeUsernameProblemLanguageResultExecution timeMemory
815187I_Love_EliskaM_Distributing Candies (IOI21_candies)C++17
11 / 100
5026 ms42120 KiB
#include "candies.h" #include <bits/stdc++.h> using namespace std; #define forn(i,n) for(int i=0;i<n;++i) #define pb push_back #define all(x) x.begin(), x.end() using ll = long long; vector<int> p1(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { int n=c.size(), q=l.size(); vector<ll> a(n,0); forn(i,q) { for (int j=l[i]; j<=r[i]; ++j) { a[j]=min(a[j]+v[i],1ll*c[j]); a[j]=max(a[j],0ll); } } vector<int> ans(n); forn(i,n) ans[i]=a[i]; return ans; } vector<int> p2(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { int n=c.size(), q=l.size(); vector<ll> pr(n+1); forn(i,q) { pr[l[i]]+=v[i]; pr[r[i]+1]-=v[i]; } forn(i,n) pr[i+1]+=pr[i]; vector<int> ans(n); forn(i,n) ans[i]=min(pr[i],1ll*c[i]); return ans; } #define int long long struct sgt { vector<int> lazy, mn, mx, type; int sz=1; sgt(int n) { while (sz<n) sz<<=1; lazy.assign(4*sz,0); mn=mx=type=lazy; } void fix(int v, int t, int x) { if (v>=2*sz-1) return; if (type[v]==0) { type[v]=t, lazy[v]=x; return; } if (type[v]==1) { if (t==1) { lazy[v]+=x; return; } push(v); //fix(2*v+1,type[v],lazy[v]); //fix(2*v+2,type[v],lazy[v]); type[v]=t; lazy[v]=x; } else if (type[v]==2) { if (t==2) { return; } push(v); //fix(2*v+1,type[v],lazy[v]); //fix(2*v+2,type[v],lazy[v]); type[v]=t; lazy[v]=x; } else { if (t==3) { return; } push(v); //fix(2*v+1,type[v],lazy[v]); //fix(2*v+2,type[v],lazy[v]); type[v]=t; lazy[v]=x; } } void push(int v) { if (v>=2*sz-1) return; if (type[v]==1) { mn[v]+=lazy[v]; mx[v]+=lazy[v]; fix(2*v+1,type[v],lazy[v]); fix(2*v+2,type[v],lazy[v]); } else if (type[v]==2) { mn[v]=max(mn[v],lazy[v]); mx[v]=max(mx[v],lazy[v]); fix(2*v+1,type[v],lazy[v]); fix(2*v+2,type[v],lazy[v]); } else { mn[v]=min(mn[v],lazy[v]); mx[v]=min(mx[v],lazy[v]); fix(2*v+1,type[v],lazy[v]); fix(2*v+2,type[v],lazy[v]); } type[v]=0; lazy[v]=0; } void add(int v, int l, int r, int lx, int rx, int x) { if (type[v]) push(v); if (rx<=l || r<=lx) return; if (lx<=l && r<=rx) { type[v]=1; lazy[v]=x; push(v); return; } int m=(l+r)>>1; add(2*v+1,l,m,lx,rx,x); add(2*v+2,m,r,lx,rx,x); mx[v]=max(mx[2*v+1],mx[2*v+2]); mn[v]=min(mn[2*v+1],mn[2*v+2]); } void add(int l, int r, int x) { add(0,0,sz,l,r,x); } void maxx(int v, int l, int r, int lx, int rx, int x) { if (type[v]) push(v); if (rx<=l || r<=lx) return; if (lx<=l && r<=rx) { type[v]=2; lazy[v]=x; push(v); return; } int m=(l+r)>>1; maxx(2*v+1,l,m,lx,rx,x); maxx(2*v+2,m,r,lx,rx,x); mx[v]=max(mx[2*v+1],mx[2*v+2]); mn[v]=min(mn[2*v+1],mn[2*v+2]); } void maxx(int l, int r, int x) { maxx(0,0,sz,l,r,x); } void minn(int v, int l, int r, int lx, int rx, int x) { if (type[v]) push(v); if (rx<=l || r<=lx) return; if (lx<=l && r<=rx) { type[v]=3; lazy[v]=x; push(v); return; } int m=(l+r)>>1; minn(2*v+1,l,m,lx,rx,x); minn(2*v+2,m,r,lx,rx,x); mx[v]=max(mx[2*v+1],mx[2*v+2]); mn[v]=min(mn[2*v+1],mn[2*v+2]); } void minn(int l, int r, int x) { minn(0,0,sz,l,r,x); } void dfs(int v) { if (v>=2*sz-1) return; if (type[v]) push(v); dfs(2*v+1); dfs(2*v+2); } }; #undef int vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) { int n=c.size(), q=l.size(); if (max(n,q)<=2000) return p1(c,l,r,v); int z=1; forn(i,q) z&=v[i]>0; if (z) return p2(c,l,r,v); forn(i,n) if (c[i]!=c[0]) exit(0); #define int long long sgt st(n); forn(i,q) { st.add(l[i],r[i]+1,v[i]); if (v[i]>0) st.minn(l[i],r[i]+1,c[0]); else st.maxx(l[i],r[i]+1,0); //st.dfs(0); //forn(j,n) cout<<j<<": "<<st.mn[st.sz-1+j]<<' '<<st.mx[st.sz-1+j]<<'\n'; //cout<<'\n'; } st.dfs(0); vector<int32_t> ans; forn(i,n) assert(st.mn[st.sz-1+i]==st.mx[st.sz-1+i]); forn(i,n) ans.pb(st.mn[st.sz-1+i]); return ans; #undef int }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...