Submission #1203667

#TimeUsernameProblemLanguageResultExecution timeMemory
1203667simona1230Distributing Candies (IOI21_candies)C++17
0 / 100
1280 ms51892 KiB
#include "candies.h" #include <bits/stdc++.h> using namespace std; const long long maxn=2*1e5+5; struct upd { long long l,r,v,i; upd(){} upd(long long _l,long long _r,long long _v,long long _i) { l=_l; r=_r; v=_v; i=_i; } bool operator<(const upd&u)const { return l<u.l; } }; struct segm { long long maxx,minn,maxi,mini,sum; segm(){} segm(long long x,long long n,long long xi,long long ni,long long s) { maxx=x; minn=n; maxi=xi; mini=ni; sum=s; } }; segm t[4*maxn]; void init(long long i,long long l,long long r) { if(l==r) { t[i].maxi=t[i].mini=l; return; } long long m=(l+r)/2; init(i*2,l,m); init(i*2+1,m+1,r); t[i].maxi=t[i].mini=l; } segm pull(segm s1,segm s2) { segm s={0,0,0,0,0}; if(s1.maxx>s2.maxx) { s.maxx=s1.maxx; s.maxi=s1.maxi; } else { s.maxx=s2.maxx; s.maxi=s2.maxi; } if(s1.minn<s2.minn) { s.minn=s1.minn; s.mini=s1.mini; } else { s.minn=s2.minn; s.mini=s2.mini; } s.sum=s1.sum+s2.sum; return s; } long long lz[4*maxn]; void push(long long i,long long l,long long r) { t[i].minn+=lz[i]; t[i].maxx+=lz[i]; t[i].sum+=(r-l+1)*lz[i]; if(l!=r) { lz[i*2]+=lz[i]; lz[i*2+1]+=lz[i]; } lz[i]=0; } void update(long long i,long long l,long long r,long long ql,long long qr,long long x) { push(i,l,r); if(ql>qr)return; if(ql<=l&&r<=qr) { lz[i]+=x; push(i,l,r); return; } long long m=(l+r)/2; update(i*2,l,m,ql,min(qr,m),x); update(i*2+1,m+1,r,max(m+1,ql),qr,x); t[i]=pull(t[i*2],t[i*2+1]); } segm query(long long i,long long l,long long r,long long ql,long long qr) { push(i,l,r); if(ql>qr)return {(long long)-1e18,(long long)1e18,0,0,0}; if(ql<=l&&r<=qr)return t[i]; long long m=(l+r)/2; return pull(query(i*2,l,m,ql,min(qr,m)),query(i*2+1,m+1,r,max(m+1,ql),qr)); } upd u[maxn]; vector<upd> q[maxn]; std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) { for(long long i=0;i<l.size();i++) u[i]={l[i],r[i],v[i],i}; sort(u,u+l.size()); vector<int> ans(c.size()); init(1,0,l.size()); long long j=0; long long sum=0; for(long long i=0;i<c.size();i++) { while(j<l.size()&&u[j].l==i) { //cout<<"+ "<<u[j].i<<" "<<j<<endl; sum+=u[j].v; update(1,0,l.size()-1,u[j].i,l.size()-1,u[j].v); q[u[j].r+1].push_back(u[j]); j++; } for(long long j=0;j<q[i].size();j++) { //cout<<"- "<<q[i][j].i<<endl; sum-=q[i][j].v; update(1,0,l.size()-1,q[i][j].i,l.size()-1,-q[i][j].v); } long long wall=-1,tp=0; long long lf=0,rt=c.size()-1; while(lf<=rt) { long long m=(lf+rt)/2; segm s=query(1,0,l.size()-1,m,l.size()-1); //cout<<m<<": "<<s.minn<<" "<<s.maxx<<" "<<s.mini<<" "<<s.maxi<<endl; if(s.maxx-s.minn>=c[i]) { //cout<<"in "<<endl; if(s.maxi>s.mini)wall=s.maxi,tp=1; else wall=s.mini,tp=0; lf=m+1; } else rt=m-1; } //cout<<sum<<endl; if(wall==-1) { wall=0; segm s=query(1,0,l.size()-1,0,l.size()-1); if(s.minn<0&&-s.minn>=c[i])wall=s.minn; if(s.maxx>0&&s.maxx>=c[i])wall=s.maxx-c[i]; ans[i]=sum-wall; continue; } //cout<<c[i]<<" > "<<wall<<endl; wall=query(1,0,l.size()-1,wall,wall).sum; if(tp==1)wall-=c[i]; ans[i]=sum-wall; //cout<<i<<" "<<sum<<" "<<wall<<endl; } return ans; }
#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...