Submission #1019903

#	Time	Username	Problem	Language	Result	Execution time	Memory
1019903		pcc	Jousting tournament (IOI12_tournament)	C++17	100 / 100	166 ms	38084 KiB

tournament

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

#define pii pair<int,int>
#define fs first
#define sc second
const int mxn = 2e5+10;
template<typename T>
using ordered_set = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;
vector<int> tr[mxn];
int par[mxn][20],dep[mxn];
pii arr[mxn];
vector<pii> rng;
ordered_set<pii> st;

void dfs(int now){
	for(int i = 1;i<20;i++){
		par[now][i] = par[par[now][i-1]][i-1];
	}
	for(auto nxt:tr[now]){
		dep[nxt] = dep[now]+1;
		par[nxt][0] = now;
		dfs(nxt);
	}
	return;
}

int up(int now,int l,int r){
	int lim = dep[now];
	int ans = 0;
	for(int i = 19;i>=0;i--){
		int p = par[now][i];
		if(arr[p].fs>l&&arr[p].sc<r){
			now = p;
			ans += 1<<i;
		}
	}
	return min(ans,lim);
}

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for(int i = 0;i<C;i++){
		rng.push_back(pii(S[i],E[i]));
	}
	int ptr = N;
	for(int i = 0;i<=N;i++)st.insert(pii(i,i)),arr[i] = pii(i,i);
	for(auto &i:rng){
		ptr++;
		auto lit = st.find_by_order(i.fs);
		auto rit = st.find_by_order(i.sc+1);
		arr[ptr].fs = arr[lit->sc].fs;
		arr[ptr].sc = arr[rit->sc].fs-1;
		for(auto it = lit;it != rit;it++){
			tr[ptr].push_back(it->sc);
		}
		int tmp = lit->fs;
		auto it = lit;
		while((it = st.find_by_order(i.fs))->fs<=arr[ptr].sc)st.erase(it);
		st.insert(pii(tmp,ptr));
	}
	assert(st.size() == 2);
	par[ptr][0] = ptr;
	dfs(ptr);
	std::priority_queue<int,vector<int>,greater<int>> pq;
	pq.push(N);
	for(int i = 0;i+1<N;i++){
		if(K[i]>R)pq.push(i);
	}
	int pl = -1,pr = pq.top();
	int ans = 0;
	int pos = 0;
	for(int i = 0;i<N;i++){
		if(pq.top()<i){
			pl = pq.top();
			pq.pop();
		}
		pr = pq.top();
		int tans = up(i,pl,pr+1);
		if(tans>ans){
			ans = tans;
			pos = i;
		}
	}
	return pos;
}

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