Submission #945840

#	Time	Username	Problem	Language	Result	Execution time	Memory
945840		hmm789	Jousting tournament (IOI12_tournament)	C++14	100 / 100	74 ms	22864 KiB

tournament

#include <bits/stdc++.h>
using namespace std;

int fw[100005];

void update(int x, int v) {
	for(x++; x < 100005; x += x&-x) fw[x] += v;
}
int query(int x) {
	int ans = 0;
	for(x++; x; x -= x&-x) ans += fw[x];
	return ans;
}
int pre[100005], fans;
vector<int> adj[200005];
int depth[200005], st[200005], ed[200005], dans[200005];
bool ans[200005];

void dfs(int x) {
	st[x] = (int)1e9; ed[x] = 0;
	dans[x] = 0;
	bool f = true;
	for(int i : adj[x]) {
		f = false;
		dfs(i);
		depth[x] = max(depth[x], depth[i]+1);
		st[x] = min(st[x], st[i]);
		ed[x] = max(ed[x], ed[i]);
		dans[x] = max(dans[x], dans[i]);
	}
	if(f) st[x] = ed[x] = x;
	if(pre[ed[x]] == pre[st[x]]) {
		ans[x] = true;
		dans[x] = depth[x];
	} else ans[x] = false;
	//cout << "dfs " << x << " " << st[x] << " " << ed[x] << " " << dans[x] << " "<< ans[x] << endl;
}

void dfs2(int x) {
	if(st[x] == ed[x]) fans = x;
	int search = dans[x];
	if(ans[x]) search--;
	for(int i : adj[x]) {
		if(dans[i] == search) {
			dfs2(i);
			break;
		}
	}
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for(int i = 0; i < N; i++) update(i, 1);
	int idx = N;
	int nidx[N], nxt[N];
	// nxt[i]: next '1' idx
	for(int i = 0; i < N; i++) {
		nidx[i] = i;
		nxt[i] = i+1;
	}
	pre[0] = 0;
	for(int i = 0; i < N-1; i++) pre[i+1] = pre[i] + (K[i] > R);
	for(int i = 0; i < C; i++) {
		int l = 0, r = N-1, m;
		while(l < r) {
			m = (l+r)/2;
			if(query(m) < S[i]+1) l = m+1;
			else r = m;
		}
		int s = l;
		l = 0; r = N-1;
		while(l < r) {
			m = (l+r)/2;
			if(query(m) < E[i]+1) l = m+1;
			else r = m;
		}
		int e = l;
		int cur = s;
		adj[idx].push_back(nidx[cur]);
		//cout << idx << " " << nidx[cur] << endl;
		while(nxt[cur] <= e) {
			cur = nxt[cur];
			adj[idx].push_back(nidx[cur]);
			//cout << idx << " " << nidx[cur] << endl;
			update(cur, -1);
		}
		nxt[s] = nxt[cur];
		nidx[s] = idx;
		idx++;
		/*cout << "aaa" << endl;
		for(int i = 0; i < N; i++) cout << nidx[i] << " ";
		cout << endl;
		for(int i = 0; i < N; i++) cout << nxt[i] << " ";
		cout << endl;
		cout << "bbb" << endl;*/
	}
	dfs(idx-1);
	dfs2(idx-1);
	return fans;
}

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