Submission #154206

#	Time	Username	Problem	Language	Result	Execution time	Memory
154206		CaroLinda	Teams (IOI15_teams)	C++14	0 / 100	801 ms	152444 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] , rootByX[MAXN] ;
persistentSeg seg;
vector<pii> xPossible ;


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

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

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

}


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

	rt[0] = seg.create() ;
	xPossible.pb({0,0}) ;

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

	lp(i, 1, n+1 )
	{
		rt[i] = seg.updPoint( rt[i-1] , 0  , MAXN , v[i-1].ss , 1 );

		if( xPossible[ xPossible.sz-1 ].ff < v[i-1].ff ) xPossible.pb( {v[i-1].ff , rt[i]} ) ;
		else xPossible[ xPossible.sz-1 ].ss = rt[i] ;

	}

	lp(i,0, xPossible.sz )
	{
		pii p = xPossible[i] ;
		rootByX[ p.ff ] = i ;
	}

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

}

void print(stack<tuple<int,int,int> > s)
{
	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(1,MAXN , 0) ) ;

	for(int i = m-1 ; i >= 0 ; i-- )
	{

		int am = k[i] , tot = 0 , x , y , alreadyRemoved ;
		tuple<int,int,int> Top ;

		//print(frontier) ;

		while( !frontier.empty() )
		{

			Top = frontier.top() ;

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

			int val = littleQry( x , am , k[i] , y ) - alreadyRemoved;

			if( tot + val > k[i] ) break ;

			tot += val ;
			am = x ;
			frontier.pop() ;

		}

		if( frontier.empty() && tot < k[i] ) { ok = false ; break ; }

		if( frontier.empty() )
		{
			frontier.push( make_tuple(x-1,y, 0) ) ;
			continue;
		}

		int l = x+1 , r = am , mid , best = x ;

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

			int val = littleQry( mid , am , k[i] , y ) ;

			if( tot + val < k[i] ) r = mid -1 ;

			else
			{
				best = mid ;
				l = mid+1 ;
			}

		}

		int val = littleQry(best, best,k[i], y ) ;
		x = best ;
		alreadyRemoved = max( 0 , val - tot ) ;

		frontier.push(make_tuple(x,y,alreadyRemoved)) ;

	} 

	return ok ;

}

/* //Delete after usage
int n , q ;
int a[MAXN] , b[MAXN] , k[MAXS] ;
int main()
{
	scanf("%d", &n );
	lp(i,0,n) scanf("%d%d", &a[i] , &b[i]) ;

	init(n,a,b) ;

	scanf("%d", &q) ;
	lp(i,0,q)
	{
		int x ;

		scanf("%d", &x) ;
		lp(j,0,x) scanf("%d", &k[j]) ;

		cout<<can(x,k)<<endl ;
	}
} */

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:133:2: note: in expansion of macro 'lp'
  lp(i,0, xPossible.sz )
  ^~
teams.cpp:140:11: warning: iteration 500009 invokes undefined behavior [-Waggressive-loop-optimizations]
   if( rt[i] == 0 ) rt[i] = rt[i-1] ;
       ~~~~^
teams.cpp:139:20: note: within this loop
  for(int i = 1 ; i <= MAXN ; i++ )
                  ~~^~~~~~~
teams.cpp: In function 'bool can(int, int*)':
teams.cpp:194:31: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
    frontier.push( make_tuple(x-1,y, 0) ) ;
                              ~^~

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