Submission #23706

#	Time	Username	Problem	Language	Result	Execution time	Memory
23706		rubabredwan	Port Facility (JOI17_port_facility)	C++14	22 / 100	3500 ms	246536 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;

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;

void bfs(int at){
	vis[at] = 1;
	for(auto u : g[at]){
		if(!vis[u]){
			col[u] = col[at] ^ 1;
			bfs(u);
		}
		if(col[u] == col[at]) flag = 1;
	}
}

bool brute(){
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			if(st[j] < st[i] && st[i] < en[j] && en[i] > en[j]){
				g[i].push_back(j);
				g[j].push_back(i);
			}
		}
	}
	memset(vis, 0, sizeof(vis));
	memset(col, 0, sizeof(col));
	for(int i=1;i<=n;i++){
		if(vis[i]) continue;
		col[i] = 0;
		bfs(i);
	}
	if(flag) return false;
	else 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(1, n+n, 1);
	int comp = 0;
	for(int i=1;i<=n;i++){
		if(!vis[i]){
			dfs(i);
			++comp;
		}
	}
	if(!brute()) 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:110:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
port_facility.cpp:112: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: 0 / 56
• Subtask 4: 0 / 22