Submission #93706

#	Time	Username	Problem	Language	Result	Execution time	Memory
93706		jangwonyoung	Holiday (IOI14_holiday)	C++14	23 / 100	1288 ms	49816 KiB

holiday

#include<cstdio>
#include"holiday.h"
#include"holiday.h"
#include<iostream>
#include<queue>
#include<algorithm>
using namespace std;
typedef long long ll;
#define fi first
#define se second
ll m,boss;
vector<pair<ll,pair<ll,ll> > >hbit[100001];
pair<ll,ll>bit[100001];
ll a[100001];
pair<ll,ll>b[100001];
ll p[100001];
ll st;
ll ans1[300001],ans2[300001],ans3[300001],ans4[300001];
vector<pair<ll,ll> >good;
ll sch(ll v){
	ll res=0LL;
	ll fnd=0LL;
	for(ll i=16; i>=0LL ;i--){
		if((fnd|(1<<i))<=m && bit[fnd|(1<<i)].se<=v){
			fnd|=(1<<i);
			v-=bit[fnd].se;
			res+=bit[fnd].fi;
		}
	}
	return res;
}
ll getc(ll x,ll y,ll d,ll dx){
	ll cur=0LL;
	ll res=d*abs(x-st);
	ll val=0LL;
	for(ll i=16; i>=0LL ;i--){
		if((cur|(1<<i))>m) continue;
		auto tmp=*--lower_bound(hbit[cur|(1<<i)].begin(),hbit[cur|(1<<i)].end(),make_pair(x*dx+1,make_pair(0LL,0LL)));
		ll newi=res+tmp.se.se;
		ll newv=val+tmp.se.fi;
		if(newi<d*abs(y-st)){cur|=(1<<i);res=newi;val=newv;continue;}
		ll myv=sch(newi-d*abs(y-st));
		if(myv<newv){cur|=(1<<i);res=newi;val=newv;}
	}
	return res+1;
}
void upd(ll id,ll pos,ll v,ll dx){
	for(ll i=pos; i<=m ;i+=i&-i){
		bit[i]={bit[i].fi+v,bit[i].se+1};
		hbit[i].push_back({id*dx,bit[i]});
	}
}
void add(ll id,ll d,ll dx){
	upd(id,p[id],a[id],dx);
	if(good.empty()){
		good.push_back({id,0LL});
		return;
	}
	ll last=getc(good.back().fi,id,d,dx);
	while(good.size()>1 && good.back().se>=last){
		good.pop_back();
		last=getc(good.back().fi,id,d,dx);
	}
	good.push_back({id,last}); 
}
void init(){
	for(ll i=1; i<=m ;i++){
		hbit[i].clear();
		hbit[i].push_back({0LL,{0LL,0LL}});
	}
}
bool debug=false;
void cal(ll* ans,ll d,ll en,ll s,ll e,ll dx){
	for(ll i=1; i<=m ;i++){
		hbit[i].clear();
		hbit[i].push_back({0LL,{0LL,0LL}});
		bit[i]={0LL,0LL};
	}
	for(ll i=s; i!=e+dx ;i+=dx) add(i,d,dx);
	for(ll i=1; i<=m ;i++){
		hbit[i].clear();
		hbit[i].push_back({0LL,{0LL,0LL}});
		bit[i]={0LL,0LL};
	}
	if(good.empty()) return;
	ll ptr=-1;
	ll cur=s-dx;
	for(ll i=0LL; i<=en ;i++){
		if(ptr<(ll)good.size()-1 && good[ptr+1].se==i){
			ptr++;
			while(cur!=good[ptr].fi){
				cur+=dx;
				upd(cur,p[cur],a[cur],dx);
			}
		}
		ans[i]=sch(i-abs(cur-st)*d);
	}
	good.clear();
}
ll findMaxAttraction(int n, int start, int d, int attraction[]) {
	m=n;boss=d;
    st=start+1;
    for(ll i=1; i<=n ;i++){
    	a[i]=attraction[i-1];
    	b[i]={a[i],i};
	}
    sort(b+1,b+n+1);
    for(ll i=1; i<=n ;i++) p[b[i].se]=n+1-i;
    cal(ans1,2,(n-st)*3+1,st,n,1);
    cal(ans2,1,(st-1)*2,st-1,1,-1);
    cal(ans3,2,(st-1)*3,st-1,1,-1);
    cal(ans4,1,(n-st)*2+1,st,n,1);
    ll fans=0LL;
    for(ll i=0LL; i<=d ;i++){
    	fans=max(fans,ans1[i]+ans2[d-i]);
    	fans=max(fans,ans3[i]+ans4[d-i]);
	}
    return fans;
}

Compilation message (stderr)

grader.cpp: In function 'int main()':
grader.cpp:7:12: warning: variable 'n_s' set but not used [-Wunused-but-set-variable]
     int i, n_s;
            ^~~

• Subtask 1: 0 / 7
• Subtask 2: 23 / 23
• Subtask 3: 0 / 17
• Subtask 4: 0 / 53