Submission #65676

#	Time	Username	Problem	Language	Result	Execution time	Memory
65676		gnoor	Holiday (IOI14_holiday)	C++17	100 / 100	2528 ms	14340 KiB

holiday

#include"holiday.h"

#include <algorithm>
#include <cstdio>
#include <cassert>
#include <cstring>

using namespace std;

struct node {
	int cnt;
	long long val;

	void combine(const node &a, const node &b) {
		cnt=a.cnt+b.cnt;
		val=a.val+b.val;
	}
};

node seg[400100];

int pos[100100];
int posinseg[100100];
int *val;

void update(int idx,int l,int r,int k,bool state) {
	if (l+1==r) {
		if (state) {
			seg[idx].cnt=1;
			seg[idx].val=val[pos[l]];
		} else {
			seg[idx].cnt=0;
			seg[idx].val=0;
		}
		return;
	}
	int m=(l+r)>>1;
	if (k<m) update(idx*2+1,l,m,k,state);
	else update(idx*2+2,m,r,k,state);
	seg[idx].combine(seg[idx*2+1],seg[idx*2+2]);
}

long long query(int idx,int l,int r,int k) {
	if (k<=0) return 0;
	if (seg[idx].cnt<=k) return seg[idx].val;
	if (l+1==r) return 0;
	int m=(l+r)>>1;
	if (seg[idx*2+1].cnt>=k) return query(idx*2+1,l,m,k);
	return seg[idx*2+1].val+query(idx*2+2,m,r,k-seg[idx*2+1].cnt);
}

long long f[300100];
long long g[300100];
int fid[300100];
int gid[300100];

int st;
int N;
void findopt(int l,int r,int optl,int optr) {
	if (l>r) return;
	//[st,optl) has turned on
	int mid=(l+r)>>1;
	f[mid]=-1;
	int optm=-1;
	long long res;
	for (int i=optl;i<=optr;i++) {
		update(0,0,N,posinseg[i],true);	
		assert(i>=st);
		res=query(0,0,N,mid-i-i+st+st);	
		if (res>f[mid]) {
			f[mid]=res;
			optm=i;
		}
	}
	fid[mid]=optm;
	//turn [optm,optr] off
	for (int i=optm;i<=optr;i++) {
		update(0,0,N,posinseg[i],false);
	}
	findopt(mid+1,r,optm,optr);
	//turn [optl,optm) off
	for(int i=optl;i<=optr;i++) {
		update(0,0,N,posinseg[i],false);
	}
	findopt(l,mid-1,optl,optm);
}

void findopt2(int l,int r,int optl,int optr) {
	if (l>r) return;
	//(optr,st) has turned on
	int mid=(l+r)>>1;
	g[mid]=-1;
	int optm=-1;
	long long res;
	for (int i=optr;i>=optl;i--) {
		update(0,0,N,posinseg[i],true);	
		assert(i<=st);
		res=query(0,0,N,mid-st+i);	
		if (res>g[mid]) {
			g[mid]=res;
			optm=i;
		}
	}
	gid[mid]=optm;
	//turn [optl,optm] off
	for (int i=optl;i<=optm;i++) {
		update(0,0,N,posinseg[i],false);
	}
	findopt2(mid+1,r,optl,optm);
	//turn (optm,optr] off
	for(int i=optl;i<=optr;i++) {
		update(0,0,N,posinseg[i],false);
	}
	findopt2(l,mid-1,optm,optr);
}

long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	val=attraction;	
	N=n;
	st=start;
	for (int i=0;i<n;i++) {
		pos[i]=i;	
	}
	sort(pos,pos+n,[attraction](const int &a, const int &b) {
			return attraction[a]>attraction[b];
			});
	for (int i=0;i<n;i++) {
		posinseg[pos[i]]=i;
	}
	findopt(1,d,st,n-1);
	if (st!=0) findopt2(1,d,0,st-1);

	long long ans=f[d];
	for (int i=0;i<=d;i++) {
		//i to right: f[i]
		ans=max(ans,f[i]+g[d-i]);
	}
	
	memset(f,0,sizeof(f));
	memset(g,0,sizeof(g));
	reverse(posinseg,posinseg+n);
	st=n-st-1;	
	findopt(0,d,st,n-1);
	if (st!=0) findopt2(0,d,0,st-1);
	ans=max(ans,f[d]);
	for (int i=0;i<=d;i++) {
		//i to right: f[i]
		ans=max(ans,f[i]+g[d-i]);
	}
	return ans;
}

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: 7 / 7
• Subtask 2: 23 / 23
• Subtask 3: 17 / 17
• Subtask 4: 53 / 53