Submission #559514

#	Time	Username	Problem	Language	Result	Execution time	Memory
559514		amunduzbaev	Port Facility (JOI17_port_facility)	C++17	22 / 100	1262 ms	26112 KiB

port_facility

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

#define ar array

const int N = 1e5 + 5;
const int mod = 1e9 + 7;

struct ST{
	ar<int, 2> tree[N << 2];
	void sett(int i, int v, int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = {v, v}; return; }
		int m = (lx + rx) >> 1;
		if(i <= m) sett(i, v, lx, m, x<<1);
		else sett(i, v, m+1, rx, x<<1|1);
		tree[x][0] = min(tree[x<<1][0], tree[x<<1|1][0]);
		tree[x][1] = max(tree[x<<1][1], tree[x<<1|1][1]);
	}
	
	ar<int, 2> get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return {N, -N};
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		auto L = get(l, r, lx, m, x<<1);
		auto R = get(l, r, m+1, rx, x<<1|1);
		return {min(L[0], R[0]), max(L[1], R[1])};
	}
}tree;

vector<int> edges[N], sub[N];
int l[N], r[N], id[N], used[N];
int c[N], par[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	vector<int> cmp;
	for(int i=0;i<n;i++){
		cin>>l[i]>>r[i];
		tree.sett(l[i], r[i]);
		tree.sett(r[i], l[i]);
		id[l[i]] = id[r[i]] = i;
		par[i] = i, cmp.push_back(i);
		sub[i].push_back(i);
	}
	
	//~ function<int(int)> f = [&](int x){
		//~ return (par[x] == x ? x : par[x] = f(par[x]));
	//~ };
	for(int T=0;T<17;T++){
		vector<ar<int, 2>> merge;
		for(auto i : cmp){
			for(auto x : sub[i]){
				tree.sett(l[x], l[x]);
				tree.sett(r[x], r[x]);
			}
			
			for(auto x : sub[i]){
				auto m = tree.get(l[x], r[x]);
				if(m[0] < l[x]){
					merge.push_back({x, id[m[0]]});
					break;
				} if(r[x] < m[1]){
					merge.push_back({x, id[m[1]]});
					break;
				}
			}
			
			for(auto x : sub[i]){
				tree.sett(l[x], r[x]);
				tree.sett(r[x], l[x]);
			}
		}
		
		for(auto x : merge){
			int a = par[x[0]], b = par[x[1]];
			if(a == b) continue;
			edges[x[0]].push_back(x[1]);
			edges[x[1]].push_back(x[0]);
			if(sub[a].size() < sub[b].size()) swap(a, b);
			for(auto x : sub[b]) par[x] = a, sub[a].push_back(x);
			sub[b].clear();
		}
		
		cmp.clear();
		for(int i=0;i<n;i++){
			if(i == par[i]) cmp.push_back(i);
		}
		
		//~ assert((int)cmp.size() * 2 <= last + 1);
	}
	
	for(int i=0;i<n;i++) tree.sett(l[i], l[i]), tree.sett(r[i], r[i]);
	
	vector<int> tt[2];
	function<void(int)> dfs = [&](int u){
		used[u] = 1;
		tt[c[u]].push_back(u);
		for(auto x : edges[u]){
			if(used[x]){
				continue;
			} else {
				c[x] = c[u] ^ 1;
				dfs(x);
			}
		}
	};
	
	int c=0;
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		dfs(i);
		for(int t=0;t<2;t++){
			for(auto x : tt[t]){
				tree.sett(l[x], r[x]);
				tree.sett(r[x], l[x]);
			}
			
			for(auto x : tt[t]){
				auto m = tree.get(l[x], r[x]);
				if(m[0] < l[x] || r[x] < m[1]){
					cout<<0<<"\n";
					return 0;
				}
			}
			
			for(auto x : tt[t]){
				tree.sett(l[x], l[x]);
				tree.sett(r[x], r[x]);
			}
		} c++;
	}
	
	int res = 1;
	while(c--){
		res = res * 2ll % mod;
	}
	
	cout<<res<<"\n";
}

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