제출 #333746

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
333746		CaroLinda	Port Facility (JOI17_port_facility)	C++14	78 / 100	6102 ms	623724 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

#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
 
const int MAX = 2e6+5 ;
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 ;
 
}
  
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] ; } ) ;
 
	set<int> s[2] ;

	for(auto e  : toSort )
	{
		auto it = s[ color[e] ].upper_bound( R[e] ) ;
		if(it != s[color[e] ].begin() )
		{
			it-- ;
			if(*it > L[e] )
			{
				printf("0\n") ;
				return 0 ;
			}
		}
		s[color[e]].insert(R[e] ) ;
	}
 
	printf("%d\n", ans ) ;
 
}

컴파일 시 표준 에러 (stderr) 메시지

port_facility.cpp:9: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
    9 | #pragma GCC optimization ("O3")
      | 
port_facility.cpp:10: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
   10 | #pragma GCC optimization ("unroll-loops")
      |

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