Submission #333754

#	Time	Username	Problem	Language	Result	Execution time	Memory
333754		CaroLinda	Port Facility (JOI17_port_facility)	C++14	100 / 100	3708 ms	133932 KiB

port_facility

#include <bits/stdc++.h>

/*
Entre tanta gente yo te vi llegar
Algo en el destino me hizo saludar
Te dije me nombre e no sé dónde
Como con un beso me respondes
*/

#define debug printf
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size())
#define ll long long

const int MAX = 2e6+10 ;
const int MOD = 1e9+7 ;

using namespace std ;

int N ;
int L[MAX] , R[MAX] ;
int saveL[MAX], saveR[MAX] ;
int beginsHere[MAX], endsHere[MAX] ;

struct Seg
{

	//Seg zero means I'm searching i s.t. L[i] < L

	int type ;
	int tree[MAX*4] ;

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

	int merge(int type , int lef, int rig)
	{
		if( !type ) return ( L[lef ]< L[rig] ) ? lef : rig ;
		return (R[lef] >R[rig] ) ? lef : rig ;
	}

	void build(int pos, int l, int r )
	{
		if( l == r ) 
		{
			tree[pos] = type ? beginsHere[l] : endsHere[r] ;
			return ;
		}

		build(pos<<1 , l , m(l,r) ) ;
		build(pos<<1|1 , m(l,r)+1, r ) ;

		tree[pos] = merge(type, tree[pos<<1], tree[pos<<1|1] ) ;
	}

	void makeRemoval(int pos, int l, int r, int x )
	{
		if( l == r ) return ;

		if( x <= m(l,r) ) makeRemoval(pos<<1 , l , m(l,r) ,  x ) ;
		else makeRemoval(pos<<1|1 , m(l,r)+1, r, x ) ;

		tree[pos] = merge(type, tree[pos<<1], tree[pos<<1|1] ) ;

	}

	int qry(int pos, int l, int r, int beg, int en ) 
	{
	//	debug("%d %d and look for %d %d and ans %d\n", l, r, beg, en, tree[pos] ) ;

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

		int al = qry(pos<<1 , l , m(l,r) , beg, en ) ;
		int ar = qry(pos<<1|1 , m(l,r)+1, r, beg, en ) ;

		return merge(type, al, ar ) ;

	}

} seg[2] ;

int main()
{
	
	seg[0].type = 0 ;
	seg[1].type = 1 ;

	scanf("%d", &N ) ;
	for(int i= 1 ; i <= N ; i++ ) 
	{
		scanf("%d %d", &L[i] , &R[i] ) ;

		saveL[i] = L[i] ; saveR[i] = R[i] ;
		beginsHere[ L[i] ] = i ;
		endsHere[ R[i] ] = i ;
	}

	L[0] = 2*N+1 ;
	R[0] = -1 ;

	seg[0].build(1,1,2*N) ;
	seg[1].build(1,1,2*N) ;

	vector<int> color(N+1,-1) ;
	color[0] = 0 ;

	int ans= 1 ;

	for(int i= 1 ; i <= N ; i++ )
	{
		if( color[i] != -1 ) continue ;

		ans <<= 1 ;
		if(ans >= MOD ) ans -= MOD ;

		vector<int> fila(1,i) ;
		color[i] = 0 ;
		int ini = 0 ;

		L[i] = 2*N+1 ;
		R[i] = -1 ;
		seg[0].makeRemoval(1,1,2*N, saveR[i] ) ;
		seg[1].makeRemoval(1,1,2*N, saveL[i] ) ;

		while( ini < sz(fila) )
		{
			int x = fila[ini++] ;
			int y;

			for(int j = 0 ; j < 2 ; j++ )
			{
				y = seg[j].qry(1,1,2*N, saveL[x] , saveR[x] ) ;

				while( color[y] == -1 && ( (!j && L[y] < saveL[x]) || (j && R[y] > saveR[x] ) )  )
				{

					color[y] = !color[x] ;

					L[y] = 2*N+1 ;
					R[y] = -1 ;

					seg[0].makeRemoval(1,1,2*N, saveR[y] ) ;
					seg[1].makeRemoval(1,1,2*N, saveL[y] ) ;

					fila.push_back(y) ;

					y = seg[j].qry( 1, 1, 2*N, saveL[x], saveR[x] ) ;

				} 
			}

		}

	}	

	vector<int> toSort(N) ; iota(all(toSort),1) ;

	sort( all(toSort), [&](int i, int j) { return saveL[i] < saveL[j] ; } ) ;

	set<int> s[2] ;

	for(auto e : toSort )
	{
		
		int c = color[e] ;

		auto it = s[c].upper_bound(saveR[e]) ;

		if(it != s[c].begin() )
		{
			it-- ;
			if( *it > saveL[e] )
			{
				printf("0\n" ) ;
				return 0 ;
			}
		}

		s[c].insert(saveR[e] ) ;

	}

	printf("%d\n", ans ) ;  

}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:88:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   88 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
port_facility.cpp:91:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   91 |   scanf("%d %d", &L[i] , &R[i] ) ;
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 12 / 12
• Subtask 3: 56 / 56
• Subtask 4: 22 / 22