Submission #21026

#	Time	Username	Problem	Language	Result	Execution time	Memory
21026		ainta	Port Facility (JOI17_port_facility)	C++14	100 / 100	2783 ms	156568 KiB

port_facility

#include <cstdio>
#include <algorithm>
#define SZ 2097152
#define pii pair<int,int>
using namespace std;
int n, chk[1010000];
int P[2010000];
pii IT[SZ+SZ][2];
struct point{
	int b, e;
}w[1010000];
void Ins(int ck, int a, pii b){
	a += SZ;
	IT[a][ck] = b;
	while(a!=1){
		a>>=1;
		if(ck) IT[a][ck] =  min(IT[a+a][ck], IT[a+a+1][ck]);
		else IT[a][ck] =  max(IT[a+a][ck], IT[a+a+1][ck]);
	}
}
pii Get(int ck, int b, int e){
	b += SZ, e += SZ;
	pii r;
	if(ck) r = pii(n+n+1,0);
	else r = pii(0,0);
	while(b<=e){
		if(ck) r = min(r, min(IT[b][ck], IT[e][ck]));
		else r = max(r, max(IT[b][ck],IT[e][ck]));
		b=(b+1)>>1,e=(e-1)>>1;
	}
	return r;
}
void DFS(int a, int col){
	chk[a] = col;
	int b = w[a].b, e = w[a].e;
	Ins(0, b, pii(0,0));
	Ins(1, e, pii(n+n+1,0));
	while(1){
		pii tp = Get(0, b+1, e-1);
		if(tp.first < e)break;
		DFS(tp.second, 3-col);
	}
	while(1){
		pii tp = Get(1, b+1, e-1);
		if(tp.first > b)break;
		DFS(tp.second, 3-col);
	}
}
int st[2010000];
bool Check(int a){
	int i, top = 0;
	for(i=1;i<=n+n;i++)P[i]=0;
	for(i=1;i<=n;i++){
		if(chk[i] == a)P[w[i].b] = i, P[w[i].e] = i;
	}
	for(i=1;i<=n+n;i++){
		if(!P[i])continue;
		if(top && st[top] == P[i])top--;
		else st[++top] = P[i];
	}
	if(!top)return true;
	return false;
}
int main(){
	int i, res = 1;
	scanf("%d",&n);
	for(i=1;i<SZ+SZ;i++){
		IT[i][0] = pii(0,0);
		IT[i][1] = pii(n+n+1,0);
	}
	for(i=1;i<=n;i++){
		scanf("%d%d",&w[i].b,&w[i].e);
		Ins(0, w[i].b, pii(w[i].e, i));
		Ins(1, w[i].e, pii(w[i].b, i));
	}
	for(i=1;i<=n;i++){
		if(!chk[i]){
			DFS(i,1);
			res = res * 2 % 1000000007;
		}
	}
	if(Check(1) && Check(2)){
		printf("%d\n",res);
	}
	else printf("0\n");
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:66:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
port_facility.cpp:72:32: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&w[i].b,&w[i].e);
                                ^

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