Submission #219056

#	Time	Username	Problem	Language	Result	Execution time	Memory
219056		CaroLinda	Jousting tournament (IOI12_tournament)	C++14	0 / 100	94 ms	7540 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()

const int MAXN = 1e5+10 ;
const int INF = 1e9+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 mn_global[MAXN] ;

struct Vez
{

	int falta , N ;
	int maior[MAXN] ;
	vector<int> seq ;
	vector< pair<int,int> > queries ;
	int mn[MAXN*4] , resp[MAXN] , bit[MAXN] ;

	void bit_upd(int pos, int val) { for(int i = pos ; i < MAXN ; i+= (i&-i)) bit[i] += val ; }
	int qry(int pos)
	{
		int tot = 0 ;
		for(int i = pos ; i > 0 ; i -= (i&-i)) 
			tot += bit[i] ;
		return tot ;
	}

	void print_info()
	{
		debug("Falta eh %d\n" , falta ) ;
		debug("Seq: ") ;
		for(auto p : seq ) debug("%d " , p) ;
		debug("\nQueries:\n") ;
		for(auto p : queries ) debug("%d %d\n" , p.ff, p.ss ) ;
		debug("Maior: ") ;
		lp(i,0,N) debug("%d ", maior[i] );
		debug("\n") ;
		debug("Resp: ") ;
		lp(i,0,N) debug("%d " , resp[i] ) ;
		debug("\n\n") ;
	}

	void acha_primeiro_direita()
	{

		int idx = N-2 ;
		maior[N-1] = INF ;

		for(int i = N-2 ; i >= 0 ; i-- )
		{
			maior[i] = maior[i+1] ;

			if( seq[idx] > falta )
				maior[i] = i+1 ;

			idx -- ;
		}

	}

	int m(int l, int r) { return (l+r)>>1 ; } 

	void build(int pos, int l, int r)
	{

		if( l == r )
			return (void)( mn[pos] = maior[l] ) ;

		build(pos<<1 , l , m(l,r) ) ;
		build((pos<<1)|1 , m(l,r)+1, r) ;

		mn[pos] = min( mn[ pos<<1 ] , mn[(pos<<1)|1] ) ;

	}

	void upd( int pos, int l, int r, int beg , int k , int idx )
	{
		if( r < beg || mn[pos] > k ) return ;
		if( l == r )
		{
			resp[l] = idx ;
			mn[l] = INF ;
			return ;
		}
		
		upd( pos<<1 , l , m(l,r) , beg, k, idx ) ;
		upd( (pos<<1)|1 , m(l,r)+1, r ,beg, k , idx ) ;

		mn[pos] = min( mn[ pos<<1 ] , mn[(pos<<1)|1] ) ;

	}

	void make_upd()
	{

		vector<pii> aux ;
		int idx = 1 , ptr = 0 ;

		for(auto p : queries )
		{
			upd( 1 , 0 , N-1 , p.ff , p.ss , idx ) ;
			idx ++ ;
		}

		lp(i,0,N) 
		{
			if(resp[i] == 0) resp[i] = INF ;
			aux.pb( mk( resp[i] , i ) ) ;
		}
		sort(all(aux)) ;

		idx = 1 ;
		for(auto p : queries )
		{

			while( ptr < N && aux[ptr].ff <= idx )
			{
				resp[aux[ptr].ss]= qry( aux[ptr].ss+1 ) ;
				ptr ++ ;
			}

			bit_upd( p.ff+1 , 1 ) ;
			bit_upd( p.ss + 2 , -1 ) ;

			idx ++ ;

		}

		while( ptr < N ) 
			resp[aux[ptr].ss]= qry( aux[ptr].ss+1 ) , ptr ++ ;

	}

} v[2]; 


int sou[MAXN] ;
ordered_set o_set ;

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

	for(int i = 0; i < 2 ; i++ ) v[i].falta = R , v[i].N = N ;

	for(int i = 0 ; i < N-1 ; i++ ) v[0].seq.pb( K[i] ) ;
	for(int i = N-2 ; i >= 0 ; i-- ) v[1].seq.pb( K[i] ) ;

	for(int i = N-1 , j = 0 ; i >= 0 ; i-- , j++ ) sou[i] = j ;

	lp(i,0,N) o_set.insert( mk(i,i) ) ;

	for(int i = 0 ; i < C ; i++ )
	{
		int ord = s[i] ;

		ordered_set::iterator it1 = o_set.find_by_order( s[i] ) ;
		ordered_set::iterator it2 = o_set.find_by_order( e[i] ) ;

		s[i] = it1->ff ;
		e[i] = it2->ss ;

		pii par = *it2 ;

		while( true )
		{
			o_set.erase( it1 ) ;
			if( (*it1) == par ) break ;
			it1 = o_set.find_by_order( ord ) ;
		}

		o_set.insert( mk( s[i] , e[i] ) ) ;

	}

	lp(i,0,C) 
	{
		v[0].queries.pb( mk( s[i] ,e[i] ) ) ;
		v[1].queries.pb( mk( sou[ e[i] ], sou[ s[i] ] ) ) ;
	}

	lp(i,0,N) mn_global[i] = INF ;

	lp(i,0,2)
	{

		v[i].acha_primeiro_direita() ;
		v[i].build(1, 0 ,  N-1 ) ;
		v[i].make_upd() ;

	}

	//lp(i,0,2) v[i].print_info() ;

	for(int i = 0 ; i < N ; i++ ) 
		mn_global[i] = min( v[0].resp[i] , v[1].resp[ sou[i] ] ) ;

	int h = *max_element( mn_global, mn_global+N ) ;

	lp(i,0,N) 
		if( mn_global[i] == h ) return i ;
}

Compilation message (stderr)

tournament.cpp: In function 'int GetBestPosition(int, int, int, int*, int*, int*)':
tournament.cpp:219:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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