Submission #1049027

#TimeUsernameProblemLanguageResultExecution timeMemory
1049027MalixDistributing Candies (IOI21_candies)C++17
11 / 100
266 ms9052 KiB
#include "candies.h" #include <bits/stdc++.h> using namespace std; typedef long long ll; typedef vector<int> vi; typedef vector<vi> vii; typedef pair<int,int> pi; typedef vector<pi> pii; typedef tuple<int,ll,int> tii; #define REP(i,a,b) for(int i=a;i<b;i++) #define F first #define S second #define PB push_back #define MP make_pair #define LSOne(s) ((s)&(-s)) ll INF=1e18+10; int inf=1e9+10; ll M=1e9+7; vector<ll> ft; int n,q; vi a,st,loc,st2,loc2; int mx=1e9; void update(int x,ll y){ x++; while(x<n+1){ ft[x]+=y; x+=LSOne(x); } } ll solve(int x){ x++; ll ans=0; while(x){ ans+=ft[x]; x-=LSOne(x); } return ans; } void build(int x,int l,int r){ if(l==r){ st[x]=a[l]; loc[x]=l; st2[x]=a[l]; loc2[x]=-l; return; } int m=(l+r)/2; build(2*x,l,m); build(2*x+1,m+1,r); st[x]=max(st[2*x],st[2*x+1]); st2[x]=min(st2[2*x],st2[2*x+1]); if(st[2*x]<=st[2*x+1])loc[x]=loc[2*x+1]; else loc[x]=loc[2*x]; if(st2[2*x]>=st2[2*x+1])loc2[x]=loc2[2*x+1]; else loc2[x]=loc2[2*x]; } pi maximum(int x,int l,int r,int a,int b){ if(a>b)return {-1,-1}; if(l==a&&r==b)return {st[x],loc[x]}; int m=(l+r)/2; return max(maximum(2*x,l,m,a,min(b,m)),maximum(2*x+1,m+1,r,max(a,m+1),b)); } pi minimum(int x,int l,int r,int a,int b){ if(a>b)return {inf,inf}; if(l==a&&r==b)return {st2[x],loc2[x]}; int m=(l+r)/2; return min(minimum(2*x,l,m,a,min(b,m)),minimum(2*x+1,m+1,r,max(a,m+1),b)); } std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l, std::vector<int> r, std::vector<int> v) { n=c.size(),q=l.size(); if(n<=2000){ vi ans(n,0); REP(i,0,q)REP(j,l[i],r[i]+1)ans[j]=max(0,min(c[j],ans[j]+v[i])); return ans; } bool flag=1; REP(i,0,n)if(v[i]<0)flag=0; if(flag){ vi ans(n); ft.resize(n+1,0); REP(i,0,q){ update(l[i],(ll)v[i]); update(r[i]+1,(ll)(-v[i])); } REP(i,0,n){ ll x=solve(i); if(x>1e9)x=1e9; ans[i]=min(c[i],(int)x); } return ans; } int pos=0; ll tot=0; flag=0; while(pos<q){ while(pos<q&&v[pos]>0){ tot+=v[pos]; pos++; } a.PB(tot); if(tot>=mx){ a.clear(); flag=1; tot=mx; } while(pos<q&&v[pos]<0){ tot+=v[pos]; pos++; } a.PB(tot); if(tot<=0){ a.clear(); flag=0; tot=0; } } int m=a.size(); if(m==0){ vi ans(n); if(flag)REP(i,0,n)ans[i]=c[i]; else REP(i,0,n)ans[i]=0; return ans; } st.resize(4*m+1);loc.resize(4*m+1); st2.resize(4*m+1);loc2.resize(4*m+1); build(1,0,m-1); pos=0;int lval=0,rval=1e9; vector<tii> arr; if(flag){ pi val=minimum(1,0,m-1,pos,m-1); lval=val.F;pos=-val.S+1; arr.PB({rval-lval,a[m-1]-(-val.S-1<0?0:a[-val.S-1]),1}); } while(pos<m){ pi val=maximum(1,0,m-1,pos,m-1); rval=val.F;pos=val.S+1; arr.PB({rval-lval,a[m-1]-(val.S-1<0?0:a[val.S-1]),0}); if(pos>=m)break; val=minimum(1,0,m-1,pos,m-1); lval=val.F;pos=-val.S+1; arr.PB({rval-lval,a[m-1]-(-val.S-1<0?0:a[-val.S-1]),1}); } arr.PB({0,0,0}); reverse(arr.begin(),arr.end()); vi ans(n); REP(i,0,n){ tuple<int,ll,int> temp={c[i],-1,-1}; auto it=upper_bound(arr.begin(),arr.end(),temp); it--; ll x=get<1>(*it); int y=get<2>(*it); if(y==1)ans[i]=c[i]; else ans[i]=0; ans[i]+=(int)x; } 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...