Submission #1268796

#	Time	Username	Problem	Language	Result	Execution time	Memory
1268796		nikolashami	Holiday (IOI14_holiday)	C++20	23 / 100	81 ms	48200 KiB

holiday

#include<bits/stdc++.h>
#include"holiday.h"
using namespace std;
using ll=long long;

#pragma GCC optimize("O3")
const ll N=1e5+7;
ll A[N],a[N],br[N],opt[3*N],sol[3*N],frS[3*N],frO[3*N],On,NN,s,DD;

const ll N2=21*N;
int root[N],lc[N2],rc[N2],cnt[N2],nd;
ll sum[N2];

void bd(ll i,ll l=1,ll r=NN){
	cnt[i]=sum[i]=0;
	if(l==r)return;
	ll md=(l+r)/2;
	lc[i]=++nd;
	rc[i]=++nd;
	bd(lc[i],l,md);
	bd(rc[i],md+1,r);
}

void upd(ll pr,ll tr,ll x,ll l=1,ll r=NN){
	if(l==r){
		cnt[tr]=cnt[pr]+1;
		sum[tr]=sum[pr]+br[x];
		return;
	}
	ll md=(l+r)/2;
	if(x<=md){
		rc[tr]=rc[pr];
		lc[tr]=++nd;
		upd(lc[pr],lc[tr],x,l,md);
	}
	else{
		lc[tr]=lc[pr];
		rc[tr]=++nd;
		upd(rc[pr],rc[tr],x,md+1,r);
	}
	cnt[tr]=cnt[lc[tr]]+cnt[rc[tr]];
	sum[tr]=sum[lc[tr]]+sum[rc[tr]];
}

ll qry(ll i,ll cc,ll l=1,ll r=NN){
	if(cc<=0||!cnt[i])return 0;
	if(cc>=cnt[i])return sum[i];
	if(l==r)return(cc*br[l]);
	ll md=(l+r)/2;
	if(cc<=cnt[rc[i]])return qry(rc[i],cc,md+1,r);
	else return sum[rc[i]]+qry(lc[i],cc-cnt[rc[i]],l,md);
}

void dnc(ll l,ll r,ll tl,ll tr){
	if(l>r||tl>tr)return;
	ll md=(l+r)/2;
	opt[md]=tl;
	sol[md]=qry(root[tl],md-tl+1);
	for(int i=1+tl;i<=tr;++i){
		ll qu=qry(root[i],md-i+1);
		if(qu>sol[md]){
			sol[md]=qu;
			opt[md]=i;
		}
	}
	dnc(l,md-1,tl,opt[md]);
	dnc(md+1,r,opt[md],tr);
}

void _reset(){
	map<ll,ll>mp;
	set<ll>ss;
	for(int i=1;i<=NN;++i)
		ss.insert(a[i]);
	ll CC=0;
	for(ll x:ss){
		mp[x]=++CC;
		br[CC]=x;
	}
	for(int i=1;i<=NN;++i)
		a[i]=mp[a[i]];
	nd=0;
	root[0]=++nd;
	bd(root[0],1,NN);
	for(int i=1;i<=NN;++i){
		root[i]=++nd;
		upd(root[i-1],root[i],a[i]);
	}
}

void _test(){
	cout<<qry(root[5],2)<<'\n';
	cout<<qry(root[3],3)<<'\n';
	cout<<qry(root[7],1)<<'\n';
	cout<<qry(root[7],6)<<'\n';
}

ll findMaxAttraction(int _n,int _s,int _d,int _a[]){
	On=_n,s=_s+1,DD=_d;
	for(int i=0;i<_n;++i)A[1+i]=_a[i];
	for(int i=s;i<=On;++i)
		a[i-s+1]=A[i];
	NN=On-s+1;
	//assert(n>0);
	if(NN<=0)return 0;
	if(NN>0)_reset();
	//_test();
	if(NN>0)dnc(1,DD,1,NN);
	for(int i=1;i<=DD;++i){
		frS[i]=sol[i];
		frO[i]=opt[i];
	}

	if(s==1)return*max_element(frS+1,frS+DD+1);

	ll P=0;
	for(int i=s-1;i>=1;--i){
		a[++P]=A[i];
	}
	NN=P;

	if(NN>0){
		_reset();
		dnc(1,DD,1,NN);
	}

	ll ans=0;
	for(int i=1;i<=DD;++i){
		ll d2=DD-i-frO[i];
		if(d2<=0)continue;
		ans=max(ans,frS[i]+sol[d2]);
	}

	On=_n,s=_n-_s,DD=_d;
	for(int i=0;i<_n;++i)A[1+i]=_a[_n-i-1];
	for(int i=s;i<=On;++i)
		a[i-s+1]=A[i];
	NN=On-s+1;
	if(NN>0)_reset();
	//_test();
	if(NN>0)dnc(1,DD,1,NN);
	for(int i=1;i<=DD&&NN>0;++i){
		frS[i]=sol[i];
		frO[i]=opt[i];
	}

	if(s==1)return*max_element(frS+1,frS+DD+1);

	P=0;
	for(int i=s-1;i>=1;--i){
		a[++P]=A[i];
	}
	NN=P;

	if(NN>0){
		_reset();
		dnc(1,DD,1,NN);
	}

	for(int i=1;i<=DD;++i){
		ll d2=DD-i-frO[i];
		if(d2<=0)continue;
		ans=max(ans,frS[i]+sol[d2]);
	}

	return ans;
}

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