Submission #8112

#	Time	Username	Problem	Language	Result	Execution time	Memory
8112		qja0950	Holiday (IOI14_holiday)	C++98	100 / 100	604 ms	8864 KiB

holiday

#include"holiday.h"
#include <algorithm>
#include <stdio.h>

#define MAXN 101101
typedef long long ll;

using namespace std;

int N, Start, D;
int *Attraction;

struct RENUMBER{
	int att;
	int index;
}ForReNumber[MAXN];
int ReNumber[MAXN];
bool operator<(RENUMBER X, RENUMBER Y) {
	return X.att>Y.att;
}
void Init() {
	for(int i=0; i<N; i++) {
		ForReNumber[i].att   = Attraction[i];
		ForReNumber[i].index = i;
	}
	sort(ForReNumber, ForReNumber+N);
}
int P;
struct TREE{
	int cnt;
	 ll sum;
}Tree[MAXN*4];
void Update(int v) {
	while(v) {
		Tree[v].cnt = Tree[v*2  ].cnt
					+ Tree[v*2+1].cnt;
		Tree[v].sum = Tree[v*2  ].sum
					+ Tree[v*2+1].sum;
		v/=2;
	}
}
void UpdateTree(int v, int cnt, ll sum) {
	Tree[v].cnt = cnt;
	Tree[v].sum = sum;
	Update(v/2);
}
ll GetMax(int v, int k) {
	if(v>=P) return Tree[v].sum;
	if(Tree[v*2].cnt>=k) return GetMax(v*2  , k);
	else return Tree[v*2].sum + GetMax(v*2+1, k-Tree[v*2].cnt);
}

ll Ans=0;
void Get(int la, int lb, int ra, int rb) {
	if(la>lb || ra>rb) return;

	int lm = (la + lb)/2;

	for(int i=lm; i<=lb; i++) UpdateTree( P+ReNumber[i], 1, ForReNumber[ReNumber[i]].att );

	ll max = -1;
	int rm = -1;
	for(int i=ra; i<=rb; i++) {
		int day = D - (Start - lm)*2 - (i - Start);
		if(day<=0) break;

		UpdateTree( P+ReNumber[i], 1, ForReNumber[ReNumber[i]].att );

		ll now = GetMax(1, day);
		if(max<now) {
			max = now;
			 rm = i;
			if(Ans<max) Ans=max;
		}
	}

	for(int i=ra; i<=rb; i++) UpdateTree( P+ReNumber[i], 0, 0 );
	Get(la, lm-1, ra, rm);

	for(int i=lm; i<=lb; i++) UpdateTree( P+ReNumber[i], 0, 0 );
	for(int i=ra; i< rm; i++) UpdateTree( P+ReNumber[i], 1, ForReNumber[ReNumber[i]].att );
	Get(lm+1, lb, rm, rb);

	for(int i=ra; i< rm; i++) UpdateTree( P+ReNumber[i], 0, 0 );
}
int MyMax(int a, int b) {
	if(a>b) return a;
	else return b;
}
long long int findMaxAttraction(int n, int start, int d, int attraction[]) {
	N = n; D = d; Attraction = attraction;
	Init();
	for(P=1; P<N; P<<=1);

	for(int i=0; i<N; i++)
		ReNumber[ ForReNumber[i].index ] = i;
	for(int i=0; i<2*P; i++) {
		Tree[i].cnt = 0;
		Tree[i].sum = 0;
	}
	Start = start;
	Get( MyMax(0,Start - (D-1)/2), Start, Start, N-1);

	for(int i=0; i<N; i++)
		ReNumber[ N - 1 - ForReNumber[i].index  ] = i;
	for(int i=0; i<2*P; i++) {
		Tree[i].cnt = 0;
		Tree[i].sum = 0;
	}
	Start = N - 1 - start;

	Get( MyMax(0,Start - (D-1)/2), Start, Start, N-1);

    return Ans;
}

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