Submission #168665

#	Time	Username	Problem	Language	Result	Execution time	Memory
168665		CaroLinda	Teams (IOI15_teams)	C++14	100 / 100	1889 ms	163904 KiB

teams

#include <bits/stdc++.h>
#include "teams.h"

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

const int MAXN = 5e5+10 , MAX = 1e6+10 ;

using namespace std ;

struct Seg
{

	vector<int> e , d , soma ;

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

	int create()
	{
		e.pb( 0 ) ;
		d.pb( 0 ) ;
		soma.pb( 0 ) ;
		return (int)(e.sz) - 1 ;
	}

	int create_and_copy(int pos)
	{
		e.pb( e[pos] ) ;
		d.pb( d[pos] ) ;
		soma.pb( soma[pos] ) ;
		return (int)(e.sz) - 1 ;
	}

	int upd(int pos, int l, int r, int idx )
	{

		int novo = create_and_copy(pos) ;

		if( l == r ) 
		{
			soma[novo] ++ ;
			return novo ;
		}
		int aux ;
		if( idx <= m(l,r) )
		{
			aux = upd(e[novo] , l, m(l,r) , idx ) ;
			e[novo] = aux ;
		}
		else
		{
			aux = upd(d[novo] ,m(l,r)+1, r , idx ) ;
			d[novo] = aux ;
		}

		soma[novo] = soma[ e[novo] ] + soma[ d[novo] ] ;

		return novo ;

	}

	int bbp(int v1, int v2, int l, int r, int& val )
	{

		if( l == r )
		{
			val -= soma[v2] - soma[v1] ;
			return l ;
		}

		int aux = soma[ e[v2] ] - soma[ e[v1] ] ;

		if( aux >= val )
			return bbp( e[v1] , e[v2] , l , m(l,r) , val ) ;

		val -= aux ;

		return bbp( d[v1] , d[v2] , m(l,r)+1, r, val ) ;

	}

	int qry(int pos, int l, int r, int beg, int en)
	{
		if( l > en || r < beg ) return 0 ;
		if( l >= beg && r <= en ) return soma[pos] ;

		int al = qry(e[pos] , l , m(l,r) , beg, en) ;
		int ar = qry(d[pos] , m(l,r)+1, r, beg, en ) ;

		return al + ar ;

	}

	void print(int pos, int l, int r)
	{
		if( l == r ) return (void)( printf("%d ", soma[pos]) ) ;
		print(e[pos] , l, m(l,r)) ;
		print(d[pos],m(l,r)+1, r) ;
	}

} ;

//Declarations
int n , q , m , cnt = 1 ;
int A[MAXN] , B[MAXN] , version[MAX] , isThere[MAX+5] ;
vector< tuple<int,int,int> > littleCompr , untitled ;
Seg seg ;

int find(int val, int t)
{
	//T == 0 -> procura o menor de todos cuja compressao eh maior ou igual a val
	//T == 1 -> procura o maior de todos cuja compressao eh menor ou igual a val

	int l = 0 , r = (int)( littleCompr.sz ) - 1 , mid , best=0;

	if( t == 0 && get<0>(littleCompr[r]) < val ) return -1 ;

	while( l <= r )
	{

		mid = (l+r)>>1 ;

		if( t == 0 )
		{
			if( get<0>(littleCompr[mid]) >= val )
			{
				best = mid ; 
				r = mid - 1 ;
			}

			else l = mid + 1 ;
		}
		else
		{

			if( get<0>(littleCompr[mid]) <= val )
			{
				best = mid ;
				l = mid+1 ;
			}
			else r = mid -1 ;

		}

	}

	return best + 1 ;

}


bool processQuery()
{

	stack< tuple<int,int,int> > pilha ;


	sort( all(untitled) ) ;

	// begL , enL , limR
	pilha.push( mkt( 0 , 0 , MAX ) ) ;

	bool isPossible = true ;

	for(auto p : untitled )
	{

		int x = get<0>(p) , y = get<1>(p) , val = get<2>(p) ;
		int fineLine = y ; 

		while( val )
		{

			//printPile() ;

			if( pilha.sz == 0 ) 
			{
				isPossible = false ;
				break ;
			}

			tuple<int,int,int> cur = pilha.top() ;

			int  enL = get<1>(cur) , limR = get<2>(cur) ;

			if( limR < fineLine )
			{
				pilha.pop() ; 
				continue ;
			}

			val += seg.qry( version[x] , 0 , MAX , 0,fineLine-1 ) - seg.qry(version[enL] , 0 , MAX ,0, fineLine-1 ) ;

			int couldBe = seg.qry( version[x] , 0 , MAX , 0,limR ) - seg.qry( version[enL] , 0 ,MAX , 0,limR ) ;

			if( val > couldBe )
			{
				pilha.pop() ;
				fineLine = limR+1 ;
				val -= couldBe ;
				continue ;

			}

			fineLine = seg.bbp( version[ enL ] , version[ x ] , 0 , MAX , val  ) ;

			pilha.push( mkt( enL , x , fineLine ) ) ;

		}

		if( !isPossible ) break ;

	}

	return isPossible ;

}


void init(int N, int a[], int b[]) {

	seg.create() ; 

	n = N ;

	lp(i,1,n+1) A[i] = a[i-1] , B[i] = b[i-1] ;

	//Little compression
	//This way, nobody will have the same R
	//Makes life easier
	lp(i,1,n+1) 
	{
		littleCompr.pb( mkt( A[i] , 0 , i ) ) ;
		littleCompr.pb( mkt( B[i] , 1 , i ) ) ;
	}
	sort( littleCompr.begin() , littleCompr.end() ) ;
	for(auto p : littleCompr )
	{
		int type = get<1>(p) , id = get<2>(p) ;
		int& ref = ( type == 0 ? A[id] : B[id] ) ;

		ref = cnt ++ ;

		if( type == 0 ) isThere[ref] = id ;

	}

	//Updating the segment tree
	for(int i = 1 ; i <= MAX ; i++ )
	{
		if( isThere[i] == 0 )
		{
			version[i] = version[i-1] ;
			continue ;
		}

		version[i] = seg.upd( version[i-1] , 0 , MAX , B[ isThere[i] ] ) ;

	}

}

int can(int M, int K[]) {
	
	m = M ;

		untitled.clear() ;

		bool cantAlready = false ;

		lp(i,0,m)
		{

			int x = K[i];

			int l = find(x,1);
			int r = find(x,0) ;

			if( r == -1 ) cantAlready = true ;

			untitled.pb( mkt( l , r , x ) ) ;

		}

		m = (int)( untitled.sz ) ;

		if( cantAlready  ) return 0 ;

		return processQuery() ;


}

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 23 / 23