Submission #349847

#	Time	Username	Problem	Language	Result	Execution time	Memory
349847		Kerim	Jousting tournament (IOI12_tournament)	C++17	0 / 100	94 ms	10544 KiB

tournament

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#define MAXN 200009
#define INF 1000000007
#define mp(x,y) make_pair(x,y)
#define all(v) v.begin(),v.end()
#define pb(x) push_back(x)
#define wr cout<<"----------------"<<endl;
#define ppb() pop_back()
#define tr(ii,c) for(__typeof((c).begin()) ii=(c).begin();ii!=(c).end();ii++)
#define ff first
#define ss second
#define my_little_dodge 46
#define debug(x)  cerr<< #x <<" = "<< x<<endl;
using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int,int> PII;
typedef tree<PII,null_type,less<PII>,rb_tree_tag,tree_order_statistics_node_update>ordered_set;
template<class T>bool umin(T& a,T b){if(a>b){a=b;return 1;}return 0;}
template<class T>bool umax(T& a,T b){if(a<b){a=b;return 1;}return 0;}
int id=-1,par[MAXN];
vector<int>adj[MAXN];
ordered_set s;
int in[MAXN],out[MAXN],T;
void add(int x,int y){
	par[y]=x;adj[x].pb(y);	
}
void dfs(int nd){
	in[nd]=++T;
	tr(it,adj[nd])dfs(*it);
	out[nd]=T;
}	
int F[MAXN];
void upd(int x,int val){
	for(;x<MAXN;x+=x&(-x))F[x]+=val;
}
int get(int x){
	int res=0;
	for(;x;x-=x&(-x))
		res+=F[x];
	return res;	
}
int GetBestPosition(int N, int C, int R, int *K, int *S, int *E) {
	for(int i=0;i<N;i++)s.insert(mp(i,i)),id++;
	for(int i=0;i<C;i++){
		__typeof((s).begin())it=s.find_by_order(S[i]);
		int who=it->ff;id++;
		for(int j=0;j<=E[i]-S[i];j++)
			add(id,it->ss),s.erase(it++);
		s.insert(mp(who,id));
	}
	dfs(id);
	for(int i=1;i<N;i++)
		upd(in[i],(K[i-1]>R));	
	int res=0;
	for(int i=0;i<N;i++){
		int nd=par[i],ans=0;
		while(nd and get(out[nd])==get(in[nd]-1))
			nd=par[nd],ans++;
		if(i+1<N){
			upd(in[i+1],-(K[i+1]>R));
			upd(in[i],(K[i+1]>R));	
		}umax(res,ans);
	}
  	return res;
}

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