Submission #1293444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1293444		Jawad_Akbar_JJ	Jousting tournament (IOI12_tournament)	C++20	49 / 100	80 ms	30576 KiB

tournament

#include <iostream>
#include <vector>

using namespace std;
const int N = (1<<17) + 1;
int cnt[N<<1], Par[N<<1][20], Mn[N], Mx[N], hei[N], num[N];
vector<int> nei[N<<1];

void insert(int i, int t, int cur = 1, int st = 1, int en = N){
	if (i < st or i >= en)
		return;
	cnt[cur] += t;
	if (en - st == 1)
		return;
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	insert(i, t, lc, st, mid);
	insert(i, t, rc, mid, en);
}

int get(int k, int cur = 1, int st = 1, int en = N){
	if (en - st == 1)
		return st;
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	if (cnt[lc] >= k)
		return get(k, lc, st, mid);
	return get(k - cnt[lc], rc, mid, en);
}

void dfs(int u, int p){
	hei[u] = hei[p] + 1;
	Par[u][0] = p;
	for (int i=0;i<17;i++)
		Par[u][i+1] = Par[Par[u][i]][i];

	for (int i : nei[u])
		dfs(i, u);

	if (nei[u].size() > 0)
		Mn[u] = Mn[nei[u].front()], Mx[u] = Mx[nei[u].back()];
}

int goUp(int u, int l, int r){
	for (int i=17;i>=0;i--){
		if (Par[u][i] != 0 and l <= Mn[Par[u][i]] and Mx[Par[u][i]] <= r)
			u = Par[u][i];
	}
	return hei[u];
}

int GetBestPosition(int n, int c, int rnk, int k[], int s[], int e[]){
	for (int i=1;i<=n;i++)
		insert(i, 1), num[i] = Mn[i] = Mx[i] = i;

	int cur = n + 1;
	for (int i=0;i<c;i++){
		int k = s[i] + 1, len = e[i] - s[i] + 1, lst;
		
		while (len--){
			insert(lst = get(k), -1);
			nei[cur].push_back(num[lst]);
		}
		num[lst] = cur++;

		insert(lst, 1);
	}

	dfs(cur - 1, 0);

	int ans = 0, id = 0;
	for (int i=0, l = -1, r = 0;i<n;i++){
		r = max(r, i);
		while (r < n - 1 and k[r] < rnk)
			r++;
		int h = hei[i + 1] - goUp(i + 1, l + 2, r + 1);
		if (h > ans)
			ans = h, id = i;
		if (k[i] > rnk)
			l = i;
	}
	return id;
}

• Subtask 1: 17 / 17
• Subtask 2: 32 / 32
• Subtask 3: 0 / 51