Submission #335451

#	Time	Username	Problem	Language	Result	Execution time	Memory
335451		CaroLinda	Port Facility (JOI17_port_facility)	C++14	78 / 100	6054 ms	495256 KiB

port_facility

#include <bits/stdc++.h>

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

using namespace std ;

int N , begQueue, endQueue ;
int color[MAXN] , q[MAXN] , idx[MAXN] ;
int K[2][MAXN] , untitled[MAXN] ;

struct Seg
{

	int cur, typeSeg ;
	int seg[MAX] ;	
	int ptrBeg[MAXN*4], ptrEnd[MAXN*4] ;

	int m(int l, int r ) { return (l+r)>>1 ; }
	
	bool isLess(int x, int y )
	{ return typeSeg ? ( K[1][x] < K[1][y] ) : ( K[0][y] < K[0][x] ) ; }

	
	void build(int pos, int l, int r )
	{ 

		if( l == r )
		{
			ptrBeg[pos] = ptrEnd[pos] = ++cur ;
			seg[ ptrBeg[pos] ] =	untitled[l] ;
			return ;
		}

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

		ptrBeg[pos] = cur+1 ;

		int ptrLef = ptrBeg[pos<<1] ;
		int ptrRig = ptrBeg[pos<<1|1] ;

		while( ptrLef <= ptrEnd[pos<<1] || ptrRig <= ptrEnd[pos<<1|1] )
		{
			if( ptrLef == ptrEnd[pos<<1]+1 ) seg[ ++cur ] = seg[ ptrRig++ ] ;
			else if( ptrRig == ptrEnd[pos<<1|1]+1 ) seg[ ++cur ] = seg[ ptrLef++ ] ;
			else 
			{
				if( isLess( seg[ptrLef], seg[ptrRig] )  ) seg[ ++cur ] = seg[ptrLef++ ] ;
				else seg[++cur] = seg[ ptrRig++ ] ;
			}


		}

		ptrEnd[pos] = cur ;

		/*printf("%d %d:\n", l,r ) ;
		for(int i = ptrBeg[pos] ; i <= ptrEnd[pos] ; i++ ) printf("%d ", seg[i] ) ;
		printf("\n") ; */

	}

	void walk(int pos, int l, int r, int x )
	{

		if( l > K[1][x] || r < K[0][x] ) return ;
		if( l >= K[0][x] && r <= K[1][x] )
		{
			while( ptrEnd[pos] >= ptrBeg[pos] )
			{
				if(typeSeg && K[1][ seg[ptrEnd[pos] ] ] < K[1][x]) break ;
				else if(!typeSeg && K[0][ seg[ptrEnd[pos] ] ] > K[0][x] ) break ;

				if( seg[ptrEnd[pos] ] != 0 && color[ seg[ptrEnd[pos] ] ] == -1 ) 
				{
					color[ seg[ptrEnd[pos] ] ] = !color[x] ;
					q[ endQueue ] = seg[ ptrEnd[pos] ] ;
					endQueue++ ;
				}

				ptrEnd[pos]-- ;

			}

			return ;

		}

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

	}

} seg[2] ;

int main()
{

	scanf("%d", &N) ;
	for(int i = 1 ; i <= N ; i++ ) scanf("%d %d", &K[0][i] , &K[1][i] ) ;

	K[0][0] = 2*N+1 ;
	K[1][0] = -1 ;

	seg[0].typeSeg = 0 ;
	seg[1].typeSeg = 1 ;
	
	for(int i = 1 ; i <= N ; i++ ) untitled[ K[1][i] ] = i ;
	seg[0].build(1,1,2*N) ;

	for(int i = 1 ; i <= N ; i++ ) 
	{
		untitled[ K[1][i] ] = 0 ;
		untitled[ K[0][i] ] = i ;
	}
	seg[1].build(1,1,2*N) ;

	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 ;

		color[i] = 0 ;
		begQueue = 0 ;
		endQueue = 1 ;

		q[begQueue] = i ;

		while( begQueue < endQueue )
		{
			int x = q[begQueue] ; begQueue++ ;

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

		}
	}

	iota(idx+1, idx+1+N, 1 ) ;
	sort(idx+1, idx+1+N , [&](int i, int j) { return K[0][i] < K[0][j] ; } ) ;	

	set<int> s[2] ;

	for(int i = 1 ; i <= N ; i++ )
	{
		int x = idx[i] ;

		auto it = s[ color[x] ].upper_bound(K[0][x] ) ;

		if(it != s[color[x]].end() && *it < K[1][x] )
		{
			printf("0\n") ;
			return 0 ;
		}

		s[ color[x] ].insert( K[1][x] ) ;
	}

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

}

Compilation message (stderr)

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

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