oj.uz

Submission #13554

# Submission time Handle Problem Language Result Execution time Memory
13554 2015-02-24T01:51:25 Z ainta Jousting tournament (IOI12_tournament) C++
100 / 100
 85 ms 4668 KB 
#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.0 / 17.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 3968 KB Output is correct
2 Correct 85 ms 4668 KB Output is correct
3 Correct 31 ms 3916 KB Output is correct
4 Correct 69 ms 4668 KB Output is correct
5 Correct 71 ms 4632 KB Output is correct
6 Correct 67 ms 4404 KB Output is correct
7 Correct 76 ms 4668 KB Output is correct
8 Correct 76 ms 4668 KB Output is correct
9 Correct 28 ms 3916 KB Output is correct
10 Correct 28 ms 3916 KB Output is correct