oj.uz

Submission #274720

# Submission time Handle Problem Language Result Execution time Memory
274720 2020-08-19T14:43:20 Z Saboon Jousting tournament (IOI12_tournament) C++14
100 / 100
 137 ms 32376 KB 
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 10;

int newint;
int par[maxn][19], fen[maxn];
int l[maxn], r[maxn];
vector<int> t[maxn];
int h[maxn];
int P[maxn];

int get_par(int v){ return P[v] < 0 ? v : P[v] = get_par(P[v]); }

int lca(int v, int u){
	if (h[v] < h[u])
		swap(v, u);
	for (int i = 18; i >= 0; i--)
		if (h[v] - (1 << i) >= h[u])
			v = par[v][i];
	if (v == u)
		return v;
	for (int i = 18; i >= 0; i--)
		if (par[v][i] != par[u][i])
			v = par[v][i], u = par[u][i];
	return par[v][0];
}

void dfs(int v, int p = -1){
	par[v][0] = p;
	for (int i = 1; i < 19 and par[v][i-1] != -1; i++)
		par[v][i] = par[par[v][i-1]][i-1];
	for (auto u : t[v]){
		h[u] = h[v]+1;
		dfs(u, v);
	}
}

int get(int x){
	int ret = 0;
	for (int i = 17; i >= 0; i--){
		if (ret + (1 << i) >= maxn)
			continue;
		if (fen[ret+(1<<i)] < x){
			ret += (1 << i);
			x -= fen[ret];
		}
	}
	return ret;
}

void add(int idx, int val){
	idx ++;
	for (; idx < maxn; idx += idx & -idx)
		fen[idx] += val;
}

int GetBestPosition(int n, int C, int R, int *K, int *S, int *E){
	memset(P, -1, sizeof P);
	newint = n;
	for (int i = 0; i < n; i++)
		add(i, +1);
	for (int i = 0; i < C; i++){
		for (int j = S[i]; j <= E[i]; j++){
			int x = get(j+1);
			t[newint].push_back(get_par(x));
		}
		for (int j = E[i]; j > S[i]; j--){
			int x = get(j+1);
			add(x, -1);
		}
		P[get(S[i]+1)] = newint ++;
	}
	int root = newint-1;
	memset(par, -1, sizeof par);
	dfs(root);
	l[0] = -1;
	for (int i = 1; i < n; i++){
		if (K[i-1] > R)
			l[i] = i-1;
		else
			l[i] = l[i-1];
	}
	r[n-1] = -1;
	for (int i = n-2; i >= 0; i--){
		if (K[i] > R)
			r[i] = i+1;
		else
			r[i] = r[i+1];
	}
	int answer = 0, sum = 0;
	for (int i = 0; i < n; i++){
		int me = h[i];
		if (l[i] != -1)
			me = min(me, h[i] - h[lca(i,l[i])]);
		if (r[i] != -1)
			me = min(me, h[i] - h[lca(i,r[i])]);
		if (me > sum){
			sum = me;
			answer = i;
		}
	}
	return answer;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 20736 KB Output is correct
2 Correct 18 ms 21248 KB Output is correct
3 Correct 15 ms 20864 KB Output is correct
4 Correct 18 ms 21120 KB Output is correct
5 Correct 18 ms 21120 KB Output is correct
6 Correct 18 ms 20992 KB Output is correct
7 Correct 18 ms 21248 KB Output is correct
8 Correct 18 ms 21120 KB Output is correct
9 Correct 15 ms 20864 KB Output is correct
10 Correct 19 ms 21120 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 69 ms 23700 KB Output is correct
2 Correct 132 ms 32376 KB Output is correct
3 Correct 71 ms 24052 KB Output is correct
4 Correct 130 ms 29944 KB Output is correct
5 Correct 133 ms 30584 KB Output is correct
6 Correct 131 ms 26616 KB Output is correct
7 Correct 137 ms 30712 KB Output is correct
8 Correct 133 ms 30712 KB Output is correct
9 Correct 60 ms 23664 KB Output is correct
10 Correct 78 ms 24084 KB Output is correct