Submission #241120

#	Time	Username	Problem	Language	Result	Execution time	Memory
241120		rqi	Jousting tournament (IOI12_tournament)	C++14	100 / 100	320 ms	34144 KiB

tournament

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

typedef pair<int, int> pi;

#define mp make_pair
#define f first
#define s second
#define sz(x) (int)x.size()
#define ins insert
#define lb lower_bound

template<class T> bool ckmax(T& a, const T& b) { 
    return a < b ? a = b, 1 : 0; } 

/**
 * Description: A set (not multiset!) with support for finding the $n$'th
 * element, and finding the index of an element. Change \texttt{null\_type} for map.
 * Time: O(\log N)
 * Source: KACTL
 * Verification: many
 */

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, 
	rb_tree_tag, tree_order_statistics_node_update>; 
#define ook order_of_key
#define fbo find_by_order

void treeExample() {
	Tree<int> t, t2; t.insert(8);
	auto it = t.insert(10).f; assert(it == t.lb(9));
	assert(t.ook(10) == 1 && t.ook(11) == 2 && *t.fbo(0) == 8);
	t.join(t2); // assuming T < T2 or T > T2, merge t2 into t
}

/**
int atMost(Tree<pi>& T, int r) { 
	return T.ook({r,MOD}); }
int getSum(Tree<pi>& T, int l, int r) { 
	return atMost(T,r)-atMost(T,l-1); }
*/

pi topi[200005];
int par[200005][30];
int curind = 0;

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	Tree<pi> ranges; //[start, ind]
	for(int i = 0; i < N; i++){
		assert(i == curind);
		ranges.ins(mp(i, i));
		topi[curind++] = mp(i, i);
	}

	for(int i = 0; i < C; i++){
		// cout << ("Round " + to_string(i) + "\n");
		// for(auto u: ranges){
		// 	cout << u.f << " " << u.s << ", ";
		// }
		// cout << "\n";
		auto it1 = ranges.fbo(S[i]);
		auto it2 = ranges.fbo(E[i]);
		pi np = mp(topi[it1->s].f, topi[it2->s].s); //new range
		int nind = curind++;
		while(next(it1) != it2){
			par[(next(it1))->s][0] = nind;
			ranges.erase(next(it1));
		}
		par[it1->s][0] = nind;
		ranges.erase(it1);
		par[it2->s][0] = nind;
		ranges.erase(it2);
		topi[nind] = np;
		ranges.ins(mp(np.f, nind));
		// for(auto u: ranges){
		// 	cout << u.f << " " << u.s << ", ";
		// }
		// cout << "\n";
	}
	assert(sz(ranges) == 1);
	par[curind-1][0] = curind;
	topi[curind] = mp(-3, N+3);
	par[curind][0] = curind;

	for(int j = 1; j < 30; j++){
		for(int i = 0; i <= curind; i++){
			par[i][j] = par[par[i][j-1]][j-1];
		}
	}

	// for(int i = 0; i <= curind; i++){
	// 	cout << i << " " << topi[i].f << " " << topi[i].s << "\n";
	// }

	// for(int i = 0; i <= curind; i++){
	// 	cout << i << " " << par[i][0] << "\n";
	// }
	
	set<int> poses;
	poses.ins(-1);
	poses.ins(N-1);
	for(int i = 0; i < N-1; i++){
		if(K[i] > R){
			poses.ins(i);
		}
	}

	pi ans = mp(-1, -N);
	for(int i = 0; i < N; i++){
		//cout << ("Test " + to_string(i) + "\n");
		//last thing that is < i
		//first thing that is >= i, add 1 to that
		int l, r;
		l = *(prev(poses.lb(i)));
		r = *(poses.lb(i))+1;
		//cout << l << " " << r << "\n";
		int node = i;
		int curans = 0;
		for(int j = 29; j >= 0; j--){
			int nnode = par[node][j];
			pi np = topi[nnode];
			if(np.f <= l || r <= np.s){
				continue;
			}
			//cout << j << " " << node << " " << nnode << "\n";
			node = nnode;
			curans+=(1<<j);
		}
		ckmax(ans, mp(curans, -i));
	}

	return -ans.s;
}

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