Submission #139328

#	Time	Username	Problem	Language	Result	Execution time	Memory
139328		CaroLinda	Meetings (IOI18_meetings)	C++14	0 / 100	76 ms	3396 KiB

meetings

//Se apenas tiver 2 no intervalo, nao esquecer de printar a reposta como 2*(R-L+1)
//Se tiver pelo menos um 1, preciso encontrar o maior bloco de 1 possível (minimizando a quantidade de 2)
//A resposta vai ser igual para todo mundo: (R-L+1 - qtd(1) ) * 2 , então eu quero maximizar a qtd de 1
//Lembrar que o primeiro e o último bloco são especiais e precisam ser tratados com carinho

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

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

const int MAXN = 1e5+ 10 ;
const ll inf = 1e17 ;
const int intInf = 1e9+10 ;

using namespace std ;

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

struct Seg
{

	int v[MAXN*4] ;

	Seg() { memset(v , 0 , sizeof v) ; }


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

	void upd(int pos, int l, int r , int x , int val)
	{

		if( l == r ) { v[pos] = val ; return ; }

		if( x <= m(l,r) ) upd(pos*2, l, m(l,r) , x , val) ;
		else upd(pos*2+1,m(l,r)+1, r , x , val ) ;

		v[pos] = max( v[pos*2] , v[pos*2+1] ) ;

	}

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

		if( l > en || r < beg ) return 0 ;
		if( l >= beg && r <= en ) return v[pos] ;

		int al = query(pos*2 , l , m(l,r) , beg , en) ;
		int ar = query(pos*2+1, m(l,r)+1, r, beg, en) ;

		return max(al,ar) ;

	}

	void print(int pos, int l, int r)
	{
		printf("%d %d %d\n" , l , r , v[pos]) ;
		if(l==r) return ;
		print(pos*2, l , m(l,r)) ;
		print(pos*2+1, m(l,r)+1, r) ;
	}

} ;


int n , q , tot , val , ini ;

Seg seg ;

vector<pii> intervalR  , intervalL ;


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

int apaga(int id , int L , int R )
{
	//Retorna infinito caso nao exista alguem nesses padroes
	//retorna o valor da seg com esse valor apagado 

	int c = seg.query(1,0,n-1,L , R) ;

	if( id == tot ) return c + ( R-L+1 - c )*2 ;

	ini = intervalR[id].ss ;
	val = seg.query( 1 , 0 , n-1  , ini , ini) ;

	seg.upd( 1 , 0 , n-1 , ini , R-ini+1 ) ;
	c = seg.query( 1 , 0 , n-1 , L , R ) ;
	seg.upd( 1 , 0 , n-1 , ini , val ) ;

	return  c + ( R - L + 1 - c)*2 ;
}

vector<ll> minimum_costs( vector<int> h , vector<int> l , vector<int> r )
{
	q = l.size() ;
	n = h.size() ;
	vector<ll> ans ;
	
	int ant = MAXN ;

	lp(i,0,n)
	{

		if( h[i] == 2 )
		{
			if( ant < MAXN ) 
			{
				intervalL.pb( mk(ant, i-1) ) ;
				intervalR.pb( mk( i-1 , ant ) ) ;
				seg.upd( 1 , 0 , n-1 , ant , i - ant ) ;
				tot ++ ;
			}

			ant = MAXN ;

		}

		else ant = min( i , ant ) ;

	}


	lp(i,0,q)
	{

		int L = l[i] , R = r[i] , id ;
		int tempAns = 2*(R-L+1) ;
		pii p ;

		//Procuro pelo primeiro tal que o r eh maior que R
		//Isso significa que ele pode estar fracionado
		//Seu valor nao pode ser levado em consideracao na seg, porque ela vai dar a resposta inteira
		id = upper_bound( intervalR.begin() , intervalR.end() , mk(R , -1) )  - intervalR.begin() ;

		tempAns = min( tempAns , apaga(id , L , R) ) ;

		//Ultimo tal que o começo está entre L e R inclusive
		id = lower_bound( intervalL.begin() , intervalL.end() , mk( L , -1 ) ) - intervalL.begin() - 1 ;

		if( id >= 0 )
		{
			p = intervalL[id] ;

			if( p.ss >= L ) tempAns = min( tempAns , ( p.ss - L + 1 ) + ( R - p.ss ) * 2 ) ;	
		}

		ans.pb(1LL*tempAns) ;

	}

	return ans ;

}

• Subtask 1: 0 / 4
• Subtask 2: 0 / 15
• Subtask 3: 0 / 17
• Subtask 4: 0 / 24
• Subtask 5: 0 / 40