oj.uz

Submission #2035

# Submission time Handle Problem Language Result Execution time Memory
2035 2013-07-19T22:17:03 Z kriii Jousting tournament (IOI12_tournament) C++
100 / 100
 65 ms 5128 KB 
const int Z = 1 << 17;
int next[Z],cnt[Z*2];

int getnth(int n)
{
	int x = 1;

	while (x < Z){
		x <<= 1;
		if (cnt[x] < n) n -= cnt[x++];
	}

	return x - Z;
}

void up(int x, int p)
{
	x += Z;
	while (x){
		cnt[x] += p;
		x >>= 1;
	}
}

int maxtree[Z*2],res[Z];
int max(int a, int b){return a > b ? a : b;}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	int i,peo,x,y,r;

	for (i=0;i<N;i++) next[i] = i+1, cnt[i+Z] = 1;
	for (i=Z-1;i>=1;i--) cnt[i] = cnt[i*2] + cnt[i*2+1];

	for (i=0;i<C;i++){
		peo = E[i] - S[i] + 1;
		S[i] = x = getnth(S[i]+1);
		up(x,1);
		while (peo--){
			up(x,-1);
			x = next[x];
		}
		E[i] = x - 1;
		next[S[i]] = x;
	}

	for (i=0;i<N-1;i++) maxtree[i+Z] = K[i];
	for (i=Z-1;i>=1;i--) maxtree[i] = max(maxtree[i*2],maxtree[i*2+1]);

	for (i=0;i<C;i++){
		x = S[i] + Z; y = E[i] - 1 + Z; r = 0;
		while (x < y){
			if (x & 1) r = max(r,maxtree[x++]);
			if (~y & 1) r = max(r,maxtree[y--]);
			x >>= 1; y >>= 1;
		} if (x == y) r = max(r,maxtree[x]);
		if (r < R){
			res[S[i]]++;
			res[E[i]]--;
		}
	}

	int s = 0, p = -1, ind;
	for (i=0;i<N;i++){
		s += res[i];
		if (p < s){
			p = s; ind = i;
		}
	}

	return ind;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

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

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4428 KB Output is correct
2 Correct 62 ms 5128 KB Output is correct
3 Correct 18 ms 4376 KB Output is correct
4 Correct 63 ms 5128 KB Output is correct
5 Correct 63 ms 5092 KB Output is correct
6 Correct 49 ms 4864 KB Output is correct
7 Correct 65 ms 5128 KB Output is correct
8 Correct 61 ms 5128 KB Output is correct
9 Correct 15 ms 4376 KB Output is correct
10 Correct 18 ms 4376 KB Output is correct