Submission #23709

#	Time	Username	Problem	Language	Result	Execution time	Memory
23709		rubabredwan	Port Facility (JOI17_port_facility)	C++14	100 / 100	2916 ms	322216 KiB

port_facility

/*  Bismillahir Rahmanir Rahim  */

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

const int N = 2000005;
const int oo = 1e9;

void scanF(int &x){
	register int c = getchar_unlocked();
	x = 0;
	for(;(c<48 || c>57);c = getchar_unlocked());
	for(;c>47 && c<58;c = getchar_unlocked()) {x = (x<<1) + (x<<3) + c - 48;}
}

int n, st[N], en[N];
int lf[N], rf[N], idx[N];
int col[N], vis[N];

struct segtree{
	int n; 
	pii mn[N*4], mx[N*4];
	void build(int _n){
		n = 2 * _n;
		for(int i = 1; i <= n; i++){
			mn[i + n - 1] = {lf[i], idx[i]};
			mx[i + n - 1] = {rf[i], idx[i]};
		}
		for(int i = n - 1; i > 0; --i){ 
			mn[i] = min(mn[i << 1], mn[i << 1 | 1]);
			mx[i] = max(mx[i << 1], mx[i << 1 | 1]);
		}
	}
	void modify(int pos){
		pos = pos - 1 + n;
		mn[pos] = {+oo, +oo};
		mx[pos] = {-oo, -oo};
		while(pos > 1){
			mn[pos >> 1] = min(mn[pos], mn[pos ^ 1]);
			mx[pos >> 1] = max(mx[pos], mx[pos ^ 1]);
			pos >>= 1;
		}
	}
	pii query_max(int l, int r){;
		--l;
		pii ret = {-oo, -oo};
		for(l += n, r += n; l < r; l >>= 1, r >>= 1){
			if(l & 1) ret = max(ret, mx[l++]);
			if(r & 1) ret = max(ret, mx[--r]);
		}
		return ret;
	}
	pii query_min(int l, int r){;
		--l;
		pii ret = {+oo, +oo};
		for(l += n, r += n; l < r; l >>= 1, r >>= 1){
			if(l & 1) ret = min(ret, mn[l++]);
			if(r & 1) ret = min(ret, mn[--r]);
		}
		return ret;
	}
} tree;

void dfs(int at){
	vis[at] = 1;
	tree.modify(st[at]);
	tree.modify(en[at]);
	while(1){
		pii f = tree.query_min(st[at], en[at]);
		if(f.first >= st[at]) break;
		col[f.second] = col[at] ^ 1;
		dfs(f.second);
	}
	while(1){
		pii f = tree.query_max(st[at], en[at]);
		if(f.first <= en[at]) break;
		col[f.second] = col[at] ^ 1;
		dfs(f.second);
	}
}

vector<int>g[N];
int flag;
int t[N*4];

void update(int b, int e, int node, int pos, int val){
	if(b == e){
		t[node] ^= (1 << val);
		return;
	}
	int mid = (b + e) / 2, l = 2 * node, h = l + 1;
	if(pos <= mid) update(b, mid, l, pos, val);
	else update(mid+1, e, h, pos, val);
	t[node] = t[l] | t[h];
}

int get(int b, int e, int node, int x, int y){
	if(y < b ||e < x) return 0;
	if(b >= x && e <= y) return t[node];
	int mid = (b + e) / 2, l = 2 * node, h = l + 1;
	return get(b, mid, l, x, y) | get(mid+1, e, h, x, y);
}

bool check(){
	for(int i=1;i<=n+n;i++){
		if(st[idx[i]] == i){
			update(1, n+n, 1, st[idx[i]], col[idx[i]]);
		}
		else{
			int g1 = get(1, n+n, 1, st[idx[i]]+1, en[idx[i]]);
			int g2 = 1 << col[idx[i]];
			if(g1 & g2) return false;
			update(1, n+n, 1, st[idx[i]], col[idx[i]]);
		}
	}
	return true;
}

int main(){
	scanF(n);
	for(int i=1;i<=n;i++){
		scanF(st[i]);
		scanF(en[i]);
		lf[en[i]] = st[i];
		lf[st[i]] = +oo;
		rf[st[i]] = en[i];
		rf[en[i]] = -oo;
		idx[st[i]] = i;
		idx[en[i]] = i;
	}
	tree.build(n);
	int comp = 0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i);
			++comp;
		}
	}
	if(check() == false) printf("0\n");
	else{
		long long ret = 1LL;
		long long mod = 1e9 + 7;
		for(int i=1;i<=comp;i++){
			ret *= 2LL;
			ret %= mod;
		}
		printf("%lld\n", ret);
	}
	return 0;
}

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