Submission #105686

#	Time	Username	Problem	Language	Result	Execution time	Memory
105686		RezwanArefin01	Jousting tournament (IOI12_tournament)	C++17	0 / 100	80 ms	7700 KiB

tournament

#include <bits/stdc++.h> 
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds;
using namespace std; 

typedef pair<int, int> ii; 
typedef tree<
ii, null_type, less<ii>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;

const int M = 2e5 + 10; 

struct node {
	int sum, flag, l, d; 
	node(int s=0, int f=0, int l=0, int d=0) :
		sum(s), flag(f), l(l), d(d) {} 

} t[M];

int idx; 
ordered_set st; 

int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for(int i = 0; i < N - 1; i++) { 
		t[i] = node(K[i] > R, K[i] > R, i, 0); 
		st.insert({i, i}); 
	}

	t[N - 1] = node(0, 0, N - 1, 0);
	st.insert({N - 1, N - 1});
	idx = N; 

	for(int i = 0; i < C; i++) {
		int l = S[i], r = E[i]; 
		auto s = st.find_by_order(l);  
		auto e = st.find_by_order(r); 
		int lid = s -> second, rid = e -> second; 
		
		t[idx].l = t[lid].l; 
		// cout << "Processing " << S[i] << " " << E[i] << endl;
		// cout << "lid " << lid << ", rid " << rid << endl;

		vector<ordered_set::iterator> v; 

		while(1) {
			int id = s -> second; 
			// cout << "merge node " << id << endl; 
			t[idx].sum += t[id].sum; 
			t[idx].d = max(t[idx].d, t[id].d + 1); 
			v.push_back(s);  
			if(s == e) break;
			s++; 
		}
			
		for(auto it : v) st.erase(it);

		t[idx].flag = t[rid].flag; 
		st.insert({l, idx});

		// cout << idx << " " << t[idx].l << " " << t[idx].sum << " " << t[idx].d << endl;
		idx++; 
	}	

	int maxwin = 0, ans = 0;

	for(int i = 0; i < idx; i++) if(t[i].d >= maxwin){
		if(t[i].sum == 0 || (t[i].sum == 1 && t[i].flag)) {
			if(t[i].d > maxwin) {
				maxwin = t[i].d;
				ans = t[i].l; 
			} else {
				ans = min(ans, t[i].l);
			}
		}
	}

	return ans; 
}	

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