Submission #289949

#	Time	Username	Problem	Language	Result	Execution time	Memory
289949		emanIaicepsa	Jousting tournament (IOI12_tournament)	C++14	100 / 100	253 ms	18144 KiB

tournament

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define mem(x,i) memset(x,i,sizeof(x))
#define dbg(x) cerr<<#x<<" = "<<x<<'\n';
#define pii pair<int,int>
#define fi first
#define se second
#define pb emplace_back
using namespace std;
using namespace __gnu_pbds;
tree<pii,null_type,less<pii>,rb_tree_tag,tree_order_statistics_node_update> tr;

vector<pii> in[100005], out[100005];
int seg[200005];

void build(int N,int *K){
	for(int i=N;i<2*N;i++) seg[i] = K[i-N];
	for(int i=N-1;i>0;i--) seg[i] = max(seg[i*2], seg[i*2+1]);
}

int query(int N,int l,int r){
	int ans = -1;
	for(l+=N,r+=N+1;l<r;l>>=1,r>>=1){
		if(l&1) ans = max(ans, seg[l++]);
		if(r&1) ans = max(ans, seg[--r]);
	}
	return ans;
}

int cnt[100005];
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for(int i=0;i<N;i++) tr.insert({i,i});
	build(N-1,K);
	for(int i=0;i<C;i++){
		auto fr = tr.find_by_order(S[i]), ba = tr.find_by_order(E[i]);
		int L = fr->fi, R = ba->se;
		auto iter = fr;
		while(iter != ba) iter = tr.erase(iter);
		tr.erase(iter);
		tr.insert({L,R});
		S[i] = L, E[i] = R;
		int rmq = query(N-1,S[i],E[i]-1);
		in[S[i]].pb(rmq,++cnt[rmq]);
		out[E[i]+1].pb(rmq,cnt[rmq]);
		//cout<<S[i]<<" "<<E[i]<<" "<<rmq<<'\n';
	}
	tr.clear();
	int ans = 0, mx = 0;
	for(int i=0;i<N;i++){
		for(auto x:in[i]) tr.insert(x);
		for(auto x:out[i]) tr.erase(x);
		int rk = tr.order_of_key({R,0});
		//cout<<i<<" "<<rk<<'\n';
		if(rk > mx){
			mx = rk;
			ans = i;
		}
	}
	return ans;
}

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