Submission #561476

#	Time	Username	Problem	Language	Result	Execution time	Memory
561476		CaroLinda	Jousting tournament (IOI12_tournament)	C++14	100 / 100	177 ms	22352 KiB

tournament

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 

#define debug printf
#define ff first
#define ss second
#define mk make_pair
#define lp(i,a,b) for(int i = a ; i < b ; i++)
#define pii pair<int,int>
#define pb push_back
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())

const int LOG = 20 ;
const int MAXN = 1e5+10 ;

using namespace std ;
using namespace __gnu_pbds ;

#define ordered_set tree<pii, null_type,less<pii>, rb_tree_tag,tree_order_statistics_node_update> 


int currNode ;
int dsu[MAXN*2] , lvl[MAXN*2] ;
int dp[LOG][MAXN*2] ;

int getLca(int x, int y){

	if(x == y) return x ;

	if(lvl[x] < lvl[y]) swap(x,y) ;

	for(int i = LOG-1 ; i >= 0 ; i-- )
		if(dp[i][x] && lvl[dp[i][x]] >= lvl[y])
			x = dp[i][x] ;

	for(int i = LOG-1 ; i >= 0 ; i-- ){
		if(dp[i][x] == dp[i][y]) continue ;
		x = dp[i][x] ;
		y = dp[i][y] ;
	}
	return dp[0][x] ;
}

int GetBestPosition(int N, int C, int R, int *K, int *s, int *e) 
{

	ordered_set o_set ;
	for(int i = 0 ; i < N ; i++ ) o_set.insert(make_pair(i,i)) ;

	currNode = N-1 ;

	for(int i= 0 ; i < C ; i++ ){
		
		auto l = o_set.find_by_order(s[i]) ;
		int K = e[i]-s[i]+1 , aux = l->first; 

		++currNode ;

		while(K--){

			dp[0][l->second] = currNode ;
			l = o_set.erase(l) ;

		}

		o_set.insert(make_pair(aux, currNode)) ;

	}

	for(int i = currNode-1 ; i >= 0 ; i-- )
		lvl[i] = lvl[ dp[0][i] ]+1 ;

	for(int i = 1 ; i < LOG ; i++ )
		for(int j = 0 ; j <= currNode ; j++ )
			if(dp[i-1][j]) dp[i][j] = dp[i-1][dp[i-1][j]] ;

	vector<int> maiorDir ;
	for(int i = N-2 ; i >= 0 ; i-- ){
		if(K[i] > R) maiorDir.push_back(i) ;
	}

	int idEsq = -1 ;
	int ans = 0 , pos = 0 ;

	for(int i = 0 ; i < N ; i++ ){

		int idRight = -1 ;

		while(!maiorDir.empty() && maiorDir.back() < i ) maiorDir.pop_back() ;

		if(!maiorDir.empty()) idRight = maiorDir.back() ;

		int ans1 = lvl[i] , ans2 = lvl[i] ;

		if(idEsq != -1 ) ans1 -= lvl[getLca(idEsq,i)]+1 ;
		if(idRight != -1 ) ans2 -= lvl[getLca(idRight+1, i)]+1 ;

		if(min(ans1,ans2) > ans){
			pos = i ;
			ans = min(ans1, ans2) ;
		}

		if(K[i] > R) idEsq = i ;

	}

	/*for(int i = 0 ; i < currNode ; i++ ){
		cout << i << " -> " << dp[0][i] << endl ;
	}  */
	//cout << ans << endl ;

	return pos ;

}

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