제출 #13554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
13554		ainta	마상시합 토너먼트 (IOI12_tournament)	C++98	100 / 100	85 ms	4668 KiB

tournament

#include<algorithm>
using namespace std;
#define SZ 131072
int IT[SZ + SZ + 2], IT2[SZ + SZ + 2], Sum[101000];
void Add(int a, int b){
	a += SZ;
	IT[a] = b;
	while (a != 1){
		a >>= 1;
		IT[a] = max(IT[a * 2], IT[a * 2 + 1]);
	}
}
void Add2(int a, int b){
	a += SZ;
	while (a){
		IT2[a] += b; a >>= 1;
	}
}
int Max(int b, int e){
	b += SZ, e += SZ;
	int r = 0;
	while (b <= e){
		r = max(r, IT[b]);
		r = max(r, IT[e]);
		b = (b + 1) >> 1, e = (e - 1) >> 1;
	}
	return r;
}
int Find(int a){
	int nd = 1;
	while (nd < SZ){
		nd *= 2;
		if (IT2[nd] < a){
			a -= IT2[nd];
			nd++;
		}
	}
	return nd - SZ;
}
int Next(int a){
	a += SZ;
	while (!IT2[a]){
		a = (a + 1) >> 1;
	}
	while (a < SZ){
		a *= 2;
		if (!IT2[a])a++;
	}
	return a - SZ;
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	int i, b, e, M = 0, r = -1, t;
	for (i = 0; i < N - 1; i++)Add(i, K[i]);
	for (i = 0; i <= N; i++)Add2(i, 1);
	for (i = 0; i < C; i++){
		b = Find(S[i] + 1), e = Find(E[i] + 2) - 1;
		if (Max(b, e - 1) < R) Sum[b]++, Sum[e + 1]--;
		while (1){
			b = Next(b + 1);
			if (b>e)break;
			Add2(b, -1);
		}
	}
	for (i = 0; i < N; i++){
		M += Sum[i];
		if (r < M)r = M, t = i;
	}
	return t;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51