oj.uz

Submission #8112

# Submission time Handle Problem Language Result Execution time Memory
8112 2014-08-30T11:38:59 Z qja0950 Holiday (IOI14_holiday) C++
100 / 100
 604 ms 8864 KB 
#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.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 8860 KB Output is correct
2 Correct 0 ms 8860 KB Output is correct
3 Correct 0 ms 8856 KB Output is correct
4 Correct 0 ms 8860 KB Output is correct
5 Correct 0 ms 8860 KB Output is correct

Subtask #2
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 180 ms 8860 KB Output is correct
2 Correct 168 ms 8860 KB Output is correct
3 Correct 176 ms 8856 KB Output is correct
4 Correct 168 ms 8856 KB Output is correct
5 Correct 160 ms 8864 KB Output is correct
6 Correct 48 ms 8860 KB Output is correct
7 Correct 84 ms 8860 KB Output is correct
8 Correct 92 ms 8860 KB Output is correct
9 Correct 32 ms 8864 KB Output is correct

Subtask #3
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 8860 KB Output is correct
2 Correct 4 ms 8864 KB Output is correct
3 Correct 4 ms 8864 KB Output is correct
4 Correct 8 ms 8860 KB Output is correct
5 Correct 8 ms 8860 KB Output is correct
6 Correct 0 ms 8856 KB Output is correct
7 Correct 0 ms 8860 KB Output is correct
8 Correct 0 ms 8856 KB Output is correct
9 Correct 0 ms 8856 KB Output is correct

Subtask #4
53.0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 168 ms 8860 KB Output is correct
2 Correct 192 ms 8856 KB Output is correct
3 Correct 112 ms 8864 KB Output is correct
4 Correct 4 ms 8860 KB Output is correct
5 Correct 0 ms 8856 KB Output is correct
6 Correct 0 ms 8856 KB Output is correct
7 Correct 0 ms 8860 KB Output is correct
8 Correct 592 ms 8864 KB Output is correct
9 Correct 604 ms 8856 KB Output is correct