oj.uz

Submission #65676

# Submission time Handle Problem Language Result Execution time Memory
65676 2018-08-08T11:38:44 Z gnoor Holiday (IOI14_holiday) C++17
100 / 100
 2528 ms 14340 KB 
#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

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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 5024 KB Output is correct
2 Correct 7 ms 5220 KB Output is correct
3 Correct 7 ms 5220 KB Output is correct
4 Correct 7 ms 5220 KB Output is correct
5 Correct 7 ms 5288 KB Output is correct
6 Correct 7 ms 5288 KB Output is correct
7 Correct 6 ms 5380 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1561 ms 12312 KB Output is correct
2 Correct 1726 ms 12492 KB Output is correct
3 Correct 1645 ms 12492 KB Output is correct
4 Correct 1802 ms 12492 KB Output is correct
5 Correct 2418 ms 12492 KB Output is correct
6 Correct 707 ms 12492 KB Output is correct
7 Correct 1114 ms 12492 KB Output is correct
8 Correct 1329 ms 12492 KB Output is correct
9 Correct 554 ms 12492 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 12492 KB Output is correct
2 Correct 48 ms 12492 KB Output is correct
3 Correct 36 ms 12492 KB Output is correct
4 Correct 35 ms 12492 KB Output is correct
5 Correct 29 ms 12492 KB Output is correct
6 Correct 13 ms 12492 KB Output is correct
7 Correct 14 ms 12492 KB Output is correct
8 Correct 14 ms 12492 KB Output is correct
9 Correct 14 ms 12492 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 1603 ms 12944 KB Output is correct
2 Correct 1729 ms 13732 KB Output is correct
3 Correct 968 ms 13732 KB Output is correct
4 Correct 32 ms 13732 KB Output is correct
5 Correct 12 ms 13732 KB Output is correct
6 Correct 12 ms 13732 KB Output is correct
7 Correct 12 ms 13732 KB Output is correct
8 Correct 2465 ms 13732 KB Output is correct
9 Correct 2528 ms 14340 KB Output is correct