Submission #578308

#	Time	Username	Problem	Language	Result	Execution time	Memory
578308		Justin1	Jousting tournament (IOI12_tournament)	C++14	17 / 100	1082 ms	9228 KiB

tournament

#include <bits/stdc++.h>
using namespace std;
 
struct qry{
	int l, r, id;
};

int root;
vector<int> ch[200005];
int par[200005];
int ar[200005], order[200005], sz[200005], pos[200005];
int segR[800005], nodeid[200005];

void updR(int tar, int val, int id, int l, int r) {
	if (l == r) {
		segR[id] = val;
		return;
	}
	int mid = (l+r)/2;
	if (tar <= mid) updR(tar,val,id*2,l,mid);
	else updR(tar,val,id*2+1,mid+1,r);
	segR[id] = segR[id*2] + segR[id*2+1];
}

int qryR(int tar, int id, int l, int r) {
	if (l == r) return l;
	int mid = (l+r)/2;
	if (tar < segR[id*2]) return qryR(tar,id*2,l,mid);
	else return qryR(tar-segR[id*2],id*2+1,mid+1,r);
}

void maketree(int N, int C, int *S, int *E) {
	for (int i = 0; i < N; i++) nodeid[i] = i;
	for (int i = 0; i < N; i++) updR(i,1,1,0,N-1);
	for (int i = 0; i < C; i++) {
		root = N+i;
		vector<int> tmp;
		for (int j = S[i]; j <= E[i]; j++) tmp.push_back(qryR(j,1,0,N-1));
		for (int j = 1; j < int(tmp.size()); j++) updR(tmp[j],0,1,0,N-1);
		for (int j = 0; j < int(tmp.size()); j++) {
			ch[root].push_back(nodeid[tmp[j]]);
			par[nodeid[tmp[j]]] = root;
		}
		nodeid[tmp[0]] = root;
	}
}

void dfs(int id) {
	static int T = 0;
	pos[id] = T;
	order[T++] = id;
	sz[id] = 1;
	for (auto i : ch[id]) {
		dfs(i);
		sz[id] += sz[i];
	}
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	maketree(N,C,S,E);
	dfs(root);
	int mx = -1, ans = -1;
	for (int i = 1; i < N; i++) ar[i] = (K[i-1] > R ? 1 : 0);
	for (int i = 0; i < N; i++) { //exhaust O(N)
		int wins = 0, cur = i, doneroot = 0;
		while (!doneroot) { //optimize using binary lifting O(log N)
			bool ok = 1;
			for (int j = pos[cur]; j < pos[cur]+sz[cur]; j++) {
				if (ar[order[j]]) ok = 0; //optimize using segment tree O(log N)
			}
			wins += ok;
			if (cur == root) doneroot = 1;
			cur = par[cur];
		}
		if (wins > mx) {
			mx = wins;
			ans = i;
		}
		swap(ar[i],ar[i+1]);
	}
	return ans;
}

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