Submission #228293

#	Time	Username	Problem	Language	Result	Execution time	Memory
228293		kig9981	Holiday (IOI14_holiday)	C++17	0 / 100	61 ms	8060 KiB

holiday

#include "holiday.h"
#include <bits/stdc++.h>

#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif

using namespace std;

const int SZ=1<<17;
vector<pair<int,int>> V;
int N, s, d, A[100000], P[100000];
long long ans, SS[100000];
pair<long long,int> tree[2*SZ];

void add_tree(int n, int v1, int v2)
{
	tree[n+=SZ].first+=v1;
	tree[n].second+=v2;
	while(n>>=1) {
		tree[n].first=tree[2*n].first+tree[2*n+1].first;
		tree[n].second=tree[2*n].second+tree[2*n+1].second;
	}
}

int kth(int k)
{
	int bit=1, s=0, e=SZ-1;
	while(s<e) {
		int m=(s+e)>>1;
		if(tree[2*bit].second>=k) {
			bit=2*bit;
			e=m;
		}
		else {
			k-=tree[2*bit].second;
			bit=2*bit+1;
			s=m+1;
		}
	}
	return s;
}

long long get_sum(int s, int e)
{
	long long ret=0;
	for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
		if(s&1) ret+=tree[s++].first;
		if(~e&1) ret+=tree[e--].first;
	}
	return ret;
}

void solve()
{
	int cd=d-1, l=s, r, k;
	long long sum=V[A[s]].first, t1, t2;
	fill(tree,tree+2*SZ,make_pair(0,0));
	add_tree(A[s],V[A[s]].first,1);
	ans=max(ans,sum); P[s]=s;
	SS[s]=V[A[s]].first;
	for(int i=s-1;i>=0;i--) SS[i]=SS[i+1]+V[A[i]].first;
	for(int i=s+1;i<N && i-s<d;i++) {
		if(cd>i-l) {
			cd-=i-l+1;
			P[i]=l;
			l=i;
			ans=max(ans,sum+=V[A[i]].first);
			add_tree(A[i],V[A[i]].first,1);
			continue;
		}
		k=kth(i-l+1-cd);
		if((t1=get_sum(0,k))<V[A[i]].first) {
			cd=0;
			P[i]=l;
			l=i;
			ans=max(ans,sum+=V[A[i]].first-t1);
			for(;;) {
				t1=kth(1);
				add_tree(t1,-V[A[t1]].first,-1);
				if(k==t1) break;
			}
			add_tree(A[i],V[A[i]].first,1);
		}
	}
	r=l; l=s;
	for(int i=s-1;i>=0 && 2*(s-i)<d;i--) {
		if(cd>2*(l-i)) {
			cd-=2*(l-i)+1;
			l=i;
			ans=max(ans,sum+=V[A[i]].first);
			add_tree(A[i],V[A[i]].first,1);
			continue;
		}
		k=kth(2*(l-i)+1-cd); t1=V[A[i]].first-get_sum(0,k);
		if(3*(l-i)<=cd+r-P[r]+1) t2=SS[i]-SS[l]-V[A[r]].first;
		else t2=-1;
		if(max(t1,t2)>0) {
			if(t1>t2) {
				cd=0;
				l=i;
				ans=max(ans,sum+=t1);
				for(;;) {
					t1=kth(1);
					add_tree(t1,-V[A[t1]].first,-1);
					if(k==t1) break;
				}
				add_tree(A[i],V[A[i]].first,1);
				while(r>s && tree[SZ+A[r]].second==0) {
					cd+=r-P[r]+1;
					r=P[r];
				}
			}
			else {
				cd-=3*(l-i)-(r-P[r]+1);
				ans=max(ans,sum+=t2);
				while(i<l--) add_tree(l,V[A[l]].first,1);
				l=i;
				add_tree(r,-V[A[r]].first,-1);
				r=P[r];
			}
		}
	}
}

long long findMaxAttraction(int n, int start, int d, int attraction[])
{
	N=n; s=start; ::d=d;
	if(d==0) return 0;
	V.resize(N);
	for(int i=0;i<N;i++) V[i]={attraction[i],i};
	sort(V.begin(),V.end());
	for(int i=0;i<N;i++) A[V[i].second]=i;
	solve();
	reverse(A,A+N); s=N-1-s;
	solve();
    return ans;
}

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