Submission #333685

#	Time	Username	Problem	Language	Result	Execution time	Memory
333685		CaroLinda	Port Facility (JOI17_port_facility)	C++14	78 / 100	6105 ms	758252 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 ;

struct Bit
{

	int bit[MAX] ;

	void upd(int i, int val ) { for(; i < MAX ; i += i &-i ) bit[i] += val ; }
	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] ;

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

	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 , vector<int> &fila )
{

	if( l > R[id] || r < L[id] ) return ;
	if( l >= L[id] && r <= R[id] )
	{
		vector<int> &aux1 = byBeginning[pos] ;
		
		while( !aux1.empty() && L[aux1.back() ] < L[id] )
		{
			if( color[ aux1.back() ] == -1 ) 
			{
				fila.push_back( aux1.back() );
				color[ aux1.back() ] = !color[id] ;
			}
			aux1.pop_back() ;
		}

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

		while( !aux2.empty() && R[ aux2.back() ] > R[id] )
		{
			if( color[ aux2.back() ] == -1 ) 
			{
				fila.push_back( aux2.back() ) ;
				color[ aux2.back() ] = !color[id] ;
			}

			aux2.pop_back() ;

		}

		return ;

	}

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

} 

int main()
{

	scanf("%d", &N ) ;
	for(int i=1 ; i <= N ; i++ ) scanf("%d %d", &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(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 ;

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

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

		sort(all(fila), [&](int a, int b ) { return L[a] < L[b] ; } ) ;
		
		for(auto e : fila )
		{
			if( bit[color[e] ].qry(R[e] ) - bit[ color[e] ].qry( L[e] ) )
			{
				printf("0\n" ) ;
				return 0 ;
			}
			bit[ color[e] ].upd( R[e] , 1  ) ;
		}
		for(auto e : fila ) bit[ color[e] ].upd( R[e] , -1 ) ;

	}

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

}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:89:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   89 |  scanf("%d", &N ) ;
      |  ~~~~~^~~~~~~~~~~
port_facility.cpp:90:36: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   90 |  for(int i=1 ; i <= N ; i++ ) scanf("%d %d", &L[i] , &R[i] ) ;
      |                               ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

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