Submission #23710

#	Time	Username	Problem	Language	Result	Execution time	Memory
23710		rubabredwan	Port Facility (JOI17_port_facility)	C++14	100 / 100	3003 ms	197216 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[2*N], mx[2*N];
	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);
	}
}

int t[2*N], nn;

void modify(int pos, int val){
	pos = pos - 1 + nn;
	t[pos] ^= (1 << val);
	while(pos > 1){
		t[pos >> 1] = t[pos] | t[pos ^ 1];
		pos >>= 1;
	}
}

int get(int l, int r){;
	--l;
	int ret = 0;
	for(l += nn, r += nn; l < r; l >>= 1, r >>= 1){
		if(l & 1) ret |= t[l++];
		if(r & 1) ret |= t[--r];
	}
	return ret;
}

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

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		scanf("%d %d", &st[i], &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);
	nn = n + 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;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:120:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
port_facility.cpp:122:33: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &st[i], &en[i]);
                                 ^

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