Submission #23708

#	Time	Username	Problem	Language	Result	Execution time	Memory
23708		rubabredwan	Port Facility (JOI17_port_facility)	C++14	78 / 100	3500 ms	286316 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 b, int e, int node){
		if(b == e){
			mn[node] = {lf[b], idx[b]};
			mx[node] = {rf[b], idx[b]};
			return;
		}
		int mid = (b + e) / 2, l = 2 * node, h = l + 1;
		build(b, mid, l);
		build(mid+1, e, h);
		mn[node] = min(mn[l], mn[h]);
		mx[node] = max(mx[l], mx[h]);
	}
	void update(int b, int e, int node, int pos){
		if(b == e){
			mx[node] = {-oo, -oo};
			mn[node] = {+oo, +oo};
			return;
		}
		int mid = (b + e) / 2, l = 2 * node, h = l + 1;
		if(pos <= mid) update(b, mid, l, pos);
		else update(mid+1, e, h, pos);
		mn[node] = min(mn[l], mn[h]);
		mx[node] = max(mx[l], mx[h]);
	}
	pii query_max(int b, int e, int node, int x, int y){
		if(y < b || e < x) return {-oo, -oo};
		if(b >= x && e <= y) return mx[node];
		int mid = (b + e) / 2, l = 2 * node, h = l + 1;
		return max(query_max(b, mid, l, x, y), query_max(mid+1, e, h, x, y));
	}
	pii query_min(int b, int e, int node, int x, int y){
		if(y < b || e < x) return {+oo, +oo};
		if(b >= x && e <= y) return mn[node];
		int mid = (b + e) / 2, l = 2 * node, h = l + 1;
		return min(query_min(b, mid, l, x, y), query_min(mid+1, e, h, x, y));
	}
} tree;

void dfs(int at){
	vis[at] = 1;
	tree.update(1, n+n, 1, st[at]);
	tree.update(1, n+n, 1, en[at]);
	while(1){
		pii f = tree.query_min(1, n+n, 1, 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(1, n+n, 1, 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(1, n+n, 1);
	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: 0 / 22