oj.uz

Submission #561474

# Submission time Handle Problem Language Result Execution time Memory
561474 2022-05-12T22:45:35 Z CaroLinda Jousting tournament (IOI12_tournament) C++14
0 / 100
 66 ms 6324 KB 
#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 ;

	for(int i = LOG-1 ; i >= 0 ; i-- ){
		if(!dp[i][x] || 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)] ;
		if(idRight != -1 ) ans2 -= lvl[getLca(idRight+1, i)] ;

		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 ;
	} */

	return pos ;

}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 6 ms 1212 KB Output is correct
3 Incorrect 4 ms 724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 6324 KB Output isn't correct
2 Halted 0 ms 0 KB -