Submission #197259

#	Time	Username	Problem	Language	Result	Execution time	Memory
197259		Malomalomalomalo	Port Facility (JOI17_port_facility)	C++14	100 / 100	1770 ms	136180 KiB

port_facility

#include <bits/stdc++.h>
#define gmin(x,y) x=min(x,y)
using namespace std;

typedef pair<int,int> pii;
const int N = 1e6 + 5;
const int MOD = 1e9 + 7;

int o[2*N], id[2*N];
vector<int> g[N];

void adde(int x,int y){
	g[x].push_back(y);
	g[y].push_back(x);
}

int col[N];

void color(int u, int c = 2){
	if(col[u])return;	
	col[u] = c;
	for(int v:g[u]){
		color(v,c^1);
	}
}

const int inf = 1e9;

struct seg {
	int t[4*N];
	int n;
	void init(int x){
		n = x;	
		fill(t,t+4*N,inf);
	}
	void edit(int x,int val){
		x+=n;
		t[x] = val;	
		while(x > 1){
			x/=2;
			t[x] = min(t[2*x], t[2*x+1]);
		}
	}
	int query(int l,int r){
		int res = inf;
		for(l+=n,r+=n;l < r; l/=2, r/=2){
			if(l&1)gmin(res, t[l++]);
			if(r&1)gmin(res, t[--r]);
		}
		return res;
	}
} tree;

int main(){
	cin.tie(0);
	cout.tie(0);
	ios_base::sync_with_stdio(0);
	int n;
	cin >> n;
	for(int i = 0;i < n; ++i){
		int x,y;
		cin >> x >> y;
		o[x] = y;
		o[y] = x;
		id[x] = id[y] = i;
	}
	stack<int> s;
	tree.init(2*n+1);
	for(int i = 1; i <= 2*n; ++i){
		if(o[i] > i){ // is an x
			while(s.size() && o[i] > s.top()){
				int y = s.top();
				s.pop();
				adde(id[i], id[y]);
			}
			if(s.size()){
				int y = tree.query(0, o[s.top()] + 1);
				assert(y != 0);
				if(y < o[i]){
					adde(id[i], id[y]);	
				}
			}
			s.push(o[i]);
			tree.edit(i, o[i]);
		}
		else{
			tree.edit(o[i], inf);
			if(s.size() && s.top() == i){
				s.pop();	
			}
		}
	}
	int cnt = 0;
	for(int i = 0;i < n; ++i){
		if(col[i] == 0){
			color(i);
			++cnt;
		}
	}
	bool valid = true;
	stack<int> a[2];
	for(int i = 1;i <= 2*n; ++i){
		if(o[i] > i){
			a[col[id[i]]^2].push(o[i]);
		}
		else{
			if(a[col[id[i]]^2].top() != i){
				valid = false;
				break;
			}
			else{
				a[col[id[i]]^2].pop();
			}
		}
	}
	if(valid){
		int ans = 1;	
		while(cnt--){
			ans = (2 * ans) % MOD;
		}
		cout << ans << '\n';
	}
	else{
		cout << 0 << '\n';
	}
}

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