Submission #671412

#	Time	Username	Problem	Language	Result	Execution time	Memory
671412		amunduzbaev	Port Facility (JOI17_port_facility)	C++17	100 / 100	3329 ms	214840 KiB

port_facility

#include "bits/stdc++.h"
using namespace std;

#define ar array
typedef long long ll;

const int N = 2e6 + 5;
const int mod = 1e9 + 7;

struct ST{
	int tree[N << 2];
	
	ST(){
		for(int i=0;i<(N<<2);i++) tree[i] = -N;
	}
	
	void set(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx){
			tree[x] = v;
			return;
		}
		
		int m = (lx + rx) >> 1;
		if(i <= m) set(i, v, lx, m, x << 1);
		else set(i, v, m + 1, rx, x << 1 | 1);
		tree[x] = max(tree[x << 1], tree[x << 1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -N;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x << 1), get(l, r, m + 1, rx, x << 1 | 1));
	}
}Min, Max;

int a[N], b[N], used[N], c[N];
int id[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin >> n;
	for(int i=0;i<n;i++){
		cin >> a[i] >> b[i];
		Min.set(b[i], -a[i]);
		Max.set(a[i], b[i]);
		id[a[i]] = id[b[i]] = i;
	}
	
	vector<int> t[2];
	function<void(int)> dfs = [&](int u){
		Max.set(a[u], -N), Min.set(b[u], -N);
		used[u] = 1;
		t[c[u]].push_back(u);
		while(true){
			int i = Max.get(a[u], b[u]);
			if(b[u] < i){
				c[id[i]] = c[u] ^ 1;
				dfs(id[i]);
				continue;
			}
			
			i = -Min.get(a[u], b[u]);
			if(i < a[u]){
				c[id[i]] = c[u] ^ 1;
				dfs(id[i]);
				continue;
			}
			
			break;
		}
	};
	
	auto check = [&](vector<int>& t){
		for(auto i : t){
			Min.set(b[i], -a[i]);
			Max.set(a[i], b[i]);
		}
		
		for(auto u : t){
			int i = Max.get(a[u], b[u]);
			if(b[u] < i){
				return true;
			}
			
			i = -Min.get(a[u], b[u]);
			if(i < a[u]){
				return true;
			}
		}
		
		for(auto i : t){
			Min.set(b[i], -N);
			Max.set(a[i], -N);
		}
		
		return false;
	};
	
	int res = 1;
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		t[0].clear(), t[1].clear();
		dfs(i);
		if(check(t[0]) || check(t[1])){
			cout<<0<<"\n";
			return 0;
		}
		
		res = res * 2ll % mod;
	}
	
	cout<<res<<"\n";
}

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