| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1008732 | tosivanmak | Holiday (IOI14_holiday) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll val[100005];
vector<ll>disc;
ll n;
ll find(ll k){
return lower_bound(disc.begin(),disc.end(),k)-disc.begin();
}
struct PSEG{
vector<vector<ll> >sum;
vector<vector<int> >cnt,lc,rc;
void init(ll n){
sum.resize(4*n+5),cnt.resize(4*n+5),lc.resize(4*n+5),rc.resize(4*n+5);
for(int i=0;i<4*n+5;i++){
sum[i].push_back(0),cnt[i].push_back(0),lc[i].push_back(0),rc[i].push_back(0);
}
}
void upd(ll ver, ll ul, ll l, ll r, ll valsum, ll valcnt, ll id){
if(l==r){
sum[id].push_back(sum[id][ver]+valsum);
cnt[id].push_back(cnt[id][ver]+valcnt);
lc[id].push_back(0),rc[id].push_back(0);
}
else{
ll mid=(l+r)>>1;
if(ul<=mid){
sum[id].push_back(sum[id][ver]+valsum),cnt[id].push_back(cnt[id][ver]+valcnt);
upd(lc[id][ver],ul,l,mid,valsum,valcnt,id*2);
lc[id].push_back(lc[id*2].size()-1),rc[id].push_back(rc[id][ver]);
}
else{
sum[id].push_back(sum[id][ver]+valsum),cnt[id].push_back(cnt[id][ver]+valcnt);
upd(rc[id][ver],ul,mid+1,r,valsum,valcnt,id*2+1);
lc[id].push_back(lc[id][ver]),rc[id].push_back(rc[id*2+1].size()-1);
}
}
}
void bs(ll& totsum, ll ver1, ll ver2, ll l, ll r, ll id, ll k){
if(l==r){
totsum+=min(k,cnt[id][ver1])*val[l];
// cout<<totsum<<'\n';
return;
}
ll mid=(l+r)>>1;
if(cnt[id*2+1][rc[id][ver1]]-cnt[id*2+1][rc[id][ver2]]>=k){
bs(totsum,rc[id][ver1],rc[id][ver2],mid+1,r,id*2+1,k);
}
else{
totsum+=sum[id*2+1][rc[id][ver1]]-sum[id*2+1][rc[id][ver2]];
bs(totsum,lc[id][ver1],lc[id][ver2],l,mid,id*2,k-(cnt[id*2+1][rc[id][ver1]]-cnt[id*2+1][rc[id][ver2]]));
}
}
void clear(){sum.clear(),cnt.clear(),lc.clear(),rc.clear();}
}st;
int starting,day;
ll ans=0;
vector<ll>att;
ll cost(ll from, ll to, ll k){
// cout<<from<<" "<<to<<" "<<k<<'\n';
if(from>to)return -1e18;
if(k<0)return -1e18;
ll extra=to-from;
if(k<=extra)return -1e18;
k-=extra;
ll ans=0;
// cout<<to+1<<' '<<from<<" "<<k<<'\n';
st.bs(ans,to+1,from,0,n-1,1,k);
return ans;
}
void find_bst(ll l, ll r, ll optl, ll optr){
if(l>r)return;
ll mid=(l+r)>>1;
ll bstid=optl,bst=cost(mid,optl,day-(abs(mid-starting)));
ll kk=day-abs(mid-starting);
for(int i=optl+1;i<=optr;i++){
if(cost(mid,i,kk)>bst){
bst=cost(mid,i,kk),bstid=i;
}
}
ans=max(ans,bst);
find_bst(l,mid-1,optl,bstid),find_bst(mid+1,r,bstid,optr);
}
ll findMaxAttraction(int _n, int start, int d, int attraction[]){
n=_n;
for(int i=0;i<_n;i++){
att.push_back(attraction[i]);
}
for(int i=0;i<_n;i++){
disc.push_back(att[i]);
}
sort(disc.begin(),disc.end());disc.erase(unique(disc.begin(),disc.end()),disc.end());
n=disc.size();
for(int i=0;i<n;i++)val[i]=disc[i];
st.init(n);
for(int i=0;i<_n;i++){
st.upd(i,find(att[i]),0,n-1,att[i],1,1);
}
starting=start,day=d;
find_bst(0,start,0,_n-1);
st.clear();
reverse(att.begin(),att.end());
st.init(n);
starting=_n-starting-1;
for(int i=0;i<_n;i++){
st.upd(i,find(att[i]),0,n-1,att[i],1,1);
}
find_bst(0,starting,0,_n-1);
return ans;
}