Submission #761596

#	Time	Username	Problem	Language	Result	Execution time	Memory
761596		SanguineChameleon	Jousting tournament (IOI12_tournament)	C++17	100 / 100	75 ms	22472 KiB

tournament

#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 / 17
• Subtask 2: 32 / 32
• Subtask 3: 51 / 51