Submission #333710

#	Time	Username	Problem	Language	Result	Execution time	Memory
333710		CaroLinda	Port Facility (JOI17_port_facility)	C++14	78 / 100	6067 ms	592668 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*2] , byBeginning[MAX*2] ;
int ptrEnd[MAX*2] , ptrBeginning[MAX*2] ;

void makeInsertion(int x, int id , bool isEnd )
{

	for( x += 2*N ; x > 0 ; x >>= 1 )
	{
		if(isEnd) byEnd[x].push_back(id) , ptrEnd[x]++ ;
		else byBeginning[x].push_back(id) , ptrBeginning[x]++ ;
	}

}

void lookFor(int node, int id )
{

	while( ptrBeginning[node]-1 >= 0 && L[byBeginning[node][ ptrBeginning[node]-1 ]] < L[id] )
	{
		int x = byBeginning[node][ ptrBeginning[node] - 1 ] ;
		ptrBeginning[node]-- ;

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

	}

	while( ptrEnd[node]-1 >= 0 && R[ byEnd[node][ ptrEnd[node]-1 ] ] > R[id] )
	{

		int x = byEnd[node][ ptrEnd[node]-1 ] ;
		ptrEnd[node]-- ;

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

	}

}

void walk(int id )
{
	int l = L[id] + 2*N ;
	int r = R[id] + 2*N ; //it is ok for this to be open, it is unique

	for(; l < r ; l >>= 1 , r >>= 1 )
	{
		if(l&1) lookFor(l++ , id ) ;
		if(r&1) lookFor(--r, id) ;
	}
} 

int main()
{

	read(N) ;
	for(int i=1 ; i <= N ; i++ ) 
	{
		read(L[i]), read(R[i] ) ;
		L[i]-- ;
		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(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(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(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