Submission #139395

#	Time	Username	Problem	Language	Result	Execution time	Memory
139395		CaroLinda	Meetings (IOI18_meetings)	C++14	0 / 100	61 ms	3436 KiB

meetings

#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 )
{

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

	if( id == tot || intervalR[id].ss > R ) return c 
;
	ini = intervalR[id].ss ;
	if( ini < L ) return R-L+1;
	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 ;

	h.pb(2) ;

	lp(i,0,n+1)
	{

		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] ;

			p.ss = min(p.ss, R) ;

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

		ans.pb(1LL*tempAns) ;

	}

	return ans ;

}

Compilation message (stderr)

meetings.cpp: In function 'int apaga(int, int, int)':
meetings.cpp:79:46: warning: 'c' is used uninitialized in this function [-Wuninitialized]
  int c = seg.query(1,0,n-1, L , R) + ( R-L+1 - c )*2 ;
                                      ~~~~~~~~^~~~~

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