oj.uz

Submission #761596

# Submission time Handle Problem Language Result Execution time Memory
761596 2023-06-20T05:16:57 Z SanguineChameleon Jousting tournament (IOI12_tournament) C++17
100 / 100
 75 ms 22472 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxN = 1e5 + 20;
int tree[maxN * 4];
int bad[maxN];
int node_id[maxN];
pair<int, int> max_depth[maxN * 2];
vector<int> ch[maxN * 2];
pair<int, int> range[maxN * 2];
int node_cnt;
pair<int, int> res;

void build(int id, int lt, int rt) {
	if (lt == rt) {
		tree[id] = 1;
		return;
	}
	int mt = (lt + rt) / 2;
	build(id * 2, lt, mt);
	build(id * 2 + 1, mt + 1, rt);
	tree[id] = tree[id * 2] + tree[id * 2 + 1];
}

void update(int id, int lt, int rt, int pos, int val) {
	if (lt == rt) {
		tree[id] = val;
		return;
	}
	int mt = (lt + rt) / 2;
	if (pos <= mt) {
		update(id * 2, lt, mt, pos, val);
	}
	else {
		update(id * 2 + 1, mt + 1, rt, pos, val);
	}
	tree[id] = tree[id * 2] + tree[id * 2 + 1];
}

int get(int id, int lt, int rt, int cnt) {
	if (lt == rt) {
		return lt;
	}
	int mt = (lt + rt) / 2;
	if (tree[id * 2] >= cnt) {
		return get(id * 2, lt, mt, cnt);
	}
	else {
		return get(id * 2 + 1, mt + 1, rt, cnt - tree[id * 2]);
	}
}

void dfs(int u) {
	max_depth[u] = make_pair(0, -u);
	for (auto v: ch[u]) {
		dfs(v);
		max_depth[u] = max(max_depth[u], make_pair(max_depth[v].first + 1, max_depth[v].second));
	}
	if (bad[range[u].second - 1] == bad[range[u].first - 1]) {
		res = max(res, max_depth[u]);
	}
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for (int i = 1; i <= N; i++) {
		node_id[i] = i;
		range[i] = make_pair(i, i);
	}
	for (int i = 1; i <= N - 1; i++) {
		bad[i] = (K[i - 1] > R) + bad[i - 1];
	}
	build(1, 1, N);
	node_cnt = N;
	for (int i = 0; i < C; i++) {
		node_cnt++;
		int first = -1;
		for (int j = 0; j < E[i] - S[i] + 1; j++) {
			int pos = get(1, 1, N, S[i] + 1);
			if (j == 0) {
				first = pos;
				range[node_cnt].first = range[node_id[pos]].first;
			}
			if (j == E[i] - S[i]) {
				range[node_cnt].second = range[node_id[pos]].second;
			}
			update(1, 1, N, pos, 0);
			ch[node_cnt].push_back(node_id[pos]);
		}
		node_id[first] = node_cnt;
		update(1, 1, N, first, 1);
	}
	res = make_pair(-1, -1);
	dfs(node_cnt);
	return -res.second - 1;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5076 KB Output is correct
2 Correct 5 ms 5844 KB Output is correct
3 Correct 3 ms 5240 KB Output is correct
4 Correct 5 ms 5588 KB Output is correct
5 Correct 5 ms 5588 KB Output is correct
6 Correct 5 ms 5404 KB Output is correct
7 Correct 5 ms 5716 KB Output is correct
8 Correct 5 ms 5588 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 7 ms 5460 KB Output is correct

Subtask #3
51.0 / 51.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 8612 KB Output is correct
2 Correct 66 ms 22472 KB Output is correct
3 Correct 32 ms 9584 KB Output is correct
4 Correct 66 ms 17300 KB Output is correct
5 Correct 70 ms 18932 KB Output is correct
6 Correct 66 ms 13472 KB Output is correct
7 Correct 75 ms 20740 KB Output is correct
8 Correct 67 ms 20708 KB Output is correct
9 Correct 26 ms 9804 KB Output is correct
10 Correct 31 ms 10128 KB Output is correct