Submission #94106

#	Time	Username	Problem	Language	Result	Execution time	Memory
94106		fjzzq2002	Jousting tournament (IOI12_tournament)	C++14	100 / 100	182 ms	31984 KiB

tournament

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<class T>
struct rbt: tree<T,int,less<T>,
rb_tree_tag,tree_order_statistics_node_update>{};
typedef pair<int,int> pii;
#define fi first
#define se second
#define SZ 666666
rbt<pii> s; int fa[SZ];
pii gs[SZ]; int gn=0,su[SZ];
vector<int> ch[SZ];
pii ans(-1,0);
void dfs(int t,int d=0,int s=0)
{
	s+=(su[gs[t].se]-su[gs[t].fi]==0);
	if(gs[t].fi==gs[t].se)
		ans=max(ans,pii(s-1,-gs[t].fi));
	for(auto c:ch[t]) dfs(c,d+1,s);
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E)
{
	gn=0; ans=pii(-1,0); s.clear();
	for(int i=0;i<N;++i)
		gs[++gn]=pii(i,i),
		fa[gn]=0,ch[gn].clear(),
		s[pii(i,i)]=gn;
	for(int i=0;i<N-1;++i)
		su[i+1]=su[i]+(K[i]>=R);
	for(int i=0;i<C;++i)
	{
		auto g=s.find_by_order(S[i]);
		int L=g->fi.fi,R; ++gn;
		fa[gn]=0; ch[gn].clear();
		for(int j=1;j<=E[i]-S[i]+1;++j)
			R=g->fi.se,fa[g->se]=gn,
			ch[gn].push_back(g->se),
			s.erase(g++);
		gs[gn]=pii(L,R);
		s[pii(L,R)]=gn;
	}
	dfs(gn); return -ans.se;
}

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