Submission #333702

#	Time	Username	Problem	Language	Result	Execution time	Memory
333702		CaroLinda	Port Facility (JOI17_port_facility)	C++14	78 / 100	6106 ms	788868 KiB

port_facility

#include <bits/stdc++.h>

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

char c ;
void read(int &num )
{
	num = 0 ;

	for( c = getchar() ; ( c > 47 && c < 58 ) ; c = getchar() )
		num = num*10 + c - 48 ;

}

struct Bit
{

	int bit[MAX] ;

	void upd(int i ) { for(; i < MAX ; i += i &-i ) bit[i]++ ; }
	int qry(int i )
	{
		int tot = 0 ;
		for(; i > 0 ; i -= i &-i ) tot += bit[i] ;
		return tot ;
	}

} bit[2] ;

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

int N ;
int L[MAX] , R[MAX] ;
int color[MAX] , ptr[MAX] ;
vector<int> fila ;

vector<int> byEnd[MAX*4] , byBeginning[MAX*4] ;
int ptrEnd[MAX*4] , ptrBeginning[MAX*4] ;
void makeInsertion( int pos, int l, int r, int x, int id , bool isEnd )
{
	if(isEnd) byEnd[pos].push_back( id ) , ptrEnd[ pos ]++ ;
	else byBeginning[pos].push_back(id) , ptrBeginning[pos]++ ;

	if( l == r) return ;

	if( x <= m(l,r) ) makeInsertion(pos<<1 , l , m(l,r) , x , id , isEnd ) ;
	else makeInsertion( pos<<1|1 , m(l,r)+1, r, x, id, isEnd ) ;
}
void walk(int pos, int l, int r, int id )
{

	if( l > R[id] || r < L[id] ) return ;
	if( l >= L[id] && r <= R[id] )
	{
		vector<int> &aux1 = byBeginning[pos] ;
		
		while( ptrBeginning[pos]-1 >= 0 && L[ aux1[ ptrBeginning[pos]-1 ] ] < L[id] )
		{
			int x = aux1[ ptrBeginning[pos]-1 ] ;
			ptrBeginning[pos]-- ;

			if( color[ x ] == -1 ) 
			{
				fila.push_back( x );
				color[x] = !color[id] ;
			}
		}

		vector<int> &aux2 = byEnd[pos] ;

		while( ptrEnd[pos]-1 >= 0 && R[ aux2[ ptrEnd[pos]-1 ] ] > R[id] )
		{
			int x = aux2[ ptrEnd[pos]-1 ] ;
			ptrEnd[pos]-- ;

			if( color[x] == -1 ) 
			{
				fila.push_back(x) ;
				color[x] = !color[id] ;
			}

		}

		return ;

	}

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

} 

int main()
{

	read(N) ;
	for(int i=1 ; i <= N ; i++ ) read(L[i]), read(R[i] ) ;

	//By beginning
	vector<int> toSort(N) ; iota(all(toSort), 1) ;
	sort( all(toSort) , [&](int i, int j) { return L[i] > L[j] ; } ) ;
	for(int i = 0 ; i < N ; i++ ) makeInsertion(1,1,2*N, R[ toSort[i] ], toSort[i], false ) ;

	//By end
	sort(all(toSort), [&](int i, int j) { return R[i] < R[j] ; } ) ;
	for(int i = 0 ; i < N ; i++ ) makeInsertion(1, 1, 2*N, L[ toSort[i] ], toSort[i] , true ) ;

	for(int i = 1 ; i <= N ; i++ ) color[i] = -1 ;
	int ans = 1 ;

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

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

		fila.clear() ;
		fila.push_back(i) ;
		color[i] = 0 ;
		int ini = 0 ;

		while( ini < sz(fila) )
		{			
			int x = fila[ini++] ;
			walk(1,1,2*N, x ) ;
		} 

	}

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

	for(int i  : toSort )
	{
		if( bit[color[i]].qry( R[i] ) - bit[color[i]].qry(L[i]) )
		{
			printf("0\n" ) ;
			return 0 ;
		}
		bit[ color[i] ].upd( R[i] ) ;
	}


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

}

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