Submission #154250

#	Time	Username	Problem	Language	Result	Execution time	Memory
154250		CaroLinda	Teams (IOI15_teams)	C++14	0 / 100	1100 ms	153732 KiB

teams

#include <bits/stdc++.h>

#define lp(i,a,b) for(int i = a ; i < b ; i++ )
#define ff first
#define ss second
#define sz size()
#define ll long long
#define mk make_pair
#define pii pair<int,int>
#define pb push_back

const int MAXN=5e5+10 ;
const int MAXS = 2e5+10 ;

using namespace std ;

struct persistentSeg
{

	vector<int> e , d , soma ;

	int m(int l , int r) { return (l+r)/2 ; }

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

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

	int updPoint(int pos, int l ,int r , int idx, int val)
	{
		int novo = pos == -1 ? create() : createAndCopy(pos) ;

		if(l==r)
		{
			soma[novo] += val ;
			return novo ;
		}

		int aux ;

		if( idx <= m(l,r) )
		{
			aux = updPoint(e[novo],l,m(l,r),idx,val) ; 
			e[novo]=aux ;
		}

		else
		{
			aux = updPoint( d[novo] , m(l,r)+1, r , idx , val ) ;
			d[novo] = aux ;
		}

		int al = e[novo] == -1 ? 0 : soma[e[novo]] ;
		int ar=d[novo] == -1 ? 0 : soma[d[novo]] ;

		soma[novo] = al + ar ;

		return novo ;

	}

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

	int qry(int pos , int l , int r , int beg, int en)
	{

		if( l > en || r < beg || pos == -1) 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 ;

	}

} ;

// --------------------------------------

int rt[MAXN] ;
persistentSeg seg;


int littleQry(int x1, int x2 , int y1, int y2)
{

	int rt1 = x1 == 0 ? rt[0] : rt[x1-1] , rt2 = rt[x2] ;

	return seg.qry( rt2 , 0 , MAXN , y1  , y2 ) - seg.qry( rt1 , 0  , MAXN , y1, y2 ) ;

}


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

	vector<pii> v , temp ;
	rt[0] = seg.create() ;
	temp.pb( {rt[0] , 0} ) ;

	lp(i,0,n) v.pb({a[i],b[i]}) ;
	sort(v.begin() , v.end()) ;

	lp(i,0,n)
		temp.pb( mk( seg.updPoint( temp[ temp.sz-1 ].ff , 0  , MAXN , v[i].ss , 1 ) , v[i].ff ) ) ;

	lp( i , 0 , temp.sz-1 )
		if( temp[i].ss != temp[i+1].ss )
			rt[ temp[i].ss ] = temp[i].ff ;

	pii last = temp[ temp.sz-1 ] ;

	rt[ last.ss ] = last.ff ;

	for(int i = 1 ; i <=MAXN ; i++ )
		if( rt[i] == 0 ) rt[i] = rt[i-1] ;

}

void print(stack<tuple<int,int,int> > s)
{
	if(s.empty()) printf("It's empty already!\n") ;
	while(!s.empty())
	{
		tuple<int,int,int> Top = s.top() ;
		s.pop() ;
		printf("%d %d %d\n", get<0>(Top) , get<1>(Top) , get<2>(Top) ) ;
	}
}

bool can(int m , int k[])
{
	stack< tuple<int,int,int> > frontier ;
	bool ok = true ;

	sort( k , k + m ) ;
	frontier.push( make_tuple( 0 , MAXN , 0 ) ) ;

	//"Frontier"'s meaning: last x I took and how much I took
	//The goal is that "alreadyRemoved" will never be 0
	//Each x at the stack will be unique

	for(int i = m-1 ; i >= 0 ; i-- )
	{
		tuple<int,int,int> Top ;
		int x , y , alreadyRemoved , carry = 0 ;

		//print(frontier) ;

		while( !frontier.empty() )
		{

			Top = frontier.top() ;

			x = get<0>(Top) ;
			y = get<1>(Top) ;
			alreadyRemoved = get<2>(Top) ;

			if( x <= k[i] ) carry += alreadyRemoved ;
			if( x > k[i] || littleQry( x , k[i] , k[i] , y ) < k[i] + alreadyRemoved ) frontier.pop() ;
			else break ;

		}

		//print(frontier);

		if( frontier.empty() ) { ok = false; break ; }

		int l = x+1 , r = k[i] , mid , best = -1 ;

		while( l <= r )
		{
			mid = (l+r)/2 ;

			if( littleQry(mid , k[i] , k[i], y ) >= k[i] + carry )
			{
				best = mid ;
				l = mid + 1 ;
			}

			else r = mid -1 ;

		}

		if( best == -1 ) { ok = false ; continue ; }

		frontier.push( make_tuple( best, k[i] , k[i] - littleQry( best+1 , k[i] , k[i] , y ) ) ) ;

	} 

	return ok ;

}

Compilation message (stderr)

teams.cpp: In member function 'int persistentSeg::create()':
teams.cpp:29:14: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   return e.sz-1 ;
          ~~~~^~
teams.cpp: In member function 'int persistentSeg::createAndCopy(int)':
teams.cpp:37:14: warning: conversion to 'int' from 'std::vector<int>::size_type {aka long unsigned int}' may alter its value [-Wconversion]
   return e.sz-1 ;
          ~~~~^~
teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:3:37: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define lp(i,a,b) for(int i = a ; i < b ; i++ )
teams.cpp:126:6:
  lp( i , 0 , temp.sz-1 )
      ~~~~~~~~~~~~~~~~~               
teams.cpp:126:2: note: in expansion of macro 'lp'
  lp( i , 0 , temp.sz-1 )
  ^~
teams.cpp:135:11: warning: iteration 500009 invokes undefined behavior [-Waggressive-loop-optimizations]
   if( rt[i] == 0 ) rt[i] = rt[i-1] ;
       ~~~~^
teams.cpp:134:20: note: within this loop
  for(int i = 1 ; i <=MAXN ; i++ )
                  ~~^~~~~~

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