Submission #349854

#	Time	Username	Problem	Language	Result	Execution time	Memory
349854		Kerim	Jousting tournament (IOI12_tournament)	C++17	100 / 100	293 ms	31980 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,P[MAXN][18];
vector<int>adj[MAXN];
ordered_set s;
int in[MAXN],out[MAXN],T;
void add(int x,int y){
	P[y][0]=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));
	}
	for(int j=1;j<18;j++)
		for(int i=0;i<=id;i++)
			if(P[i][j-1])
				P[i][j]=P[P[i][j-1]][j-1];
	dfs(id);
	for(int i=1;i<N;i++)
		upd(in[i],(K[i-1]>R));	
	int res=-1,who;
	for(int i=0;i<N;i++){
		int ans=0,nd=i;
		for(int j=17;j>=0;j--)	
			if(P[nd][j] and get(out[P[nd][j]])==get(in[P[nd][j]]-1))
				nd=P[nd][j],ans+=(1<<j);
		if(i+1<N){
			upd(in[i+1],-(K[i]>R));
			upd(in[i],(K[i]>R));	
		}
		if(umax(res,ans))who=i;
	}
  	return who;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:73:11: warning: 'who' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |    return who;
      |           ^~~

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