Submission #559530

#	Time	Username	Problem	Language	Result	Execution time	Memory
559530		amunduzbaev	Port Facility (JOI17_port_facility)	C++17	100 / 100	4032 ms	330044 KiB

port_facility

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

#define ar array

const int N = 2e6 + 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]; //, cmp[N];
//~ ar<int, 2> mm[N];

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	//~ int sz = 0, ss = 0;
	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[sz++] = i;
		//~ sub[i].push_back(i);
	}
	
	function<void(int)> dfs2 = [&](int u){
		tree.sett(l[u], l[u]);
		tree.sett(r[u], r[u]);
		used[u] = 1;
		while(true){
			auto m = tree.get(l[u], r[u]);
			if(m[0] < l[u]){
				int x = id[m[0]];
				edges[u].push_back(x);
				edges[x].push_back(u);
				dfs2(x);
			} else if(r[u] < m[1]){
				int x = id[m[1]];
				edges[u].push_back(x);
				edges[x].push_back(u);
				dfs2(x);
			} else break;
		}
	};
	
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		dfs2(i);
	}
	
	memset(used, 0, sizeof used);
	
	//~ while(true){
		//~ ss = 0;
		//~ for(int j=0;j<sz;j++){ int i = cmp[j];
			//~ 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]){
					//~ mm[ss++] = {x, id[m[0]]};
					//~ break;
				//~ } if(r[x] < m[1]){
					//~ mm[ss++] = {x, id[m[1]]};
					//~ break;
				//~ }
			//~ }
			
			//~ for(auto x : sub[i]){
				//~ tree.sett(l[x], r[x]);
				//~ tree.sett(r[x], l[x]);
			//~ }
		//~ }
		
		//~ for(int j=0;j<ss;j++){ auto& x = mm[j];
			//~ 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();
		//~ }
		//~ int last = sz; sz = 0;
		//~ for(int i=0;i<n;i++){
			//~ if(i == par[i]) cmp[sz++] = i;
		//~ }
		
		//~ if(sz == last) break;
	//~ }
	
	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]){
				c[x] = c[u] ^ 1;
				dfs(x);
			}
		}
	};
	
	int cnt=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]);
			} tt[t].clear();
		} cnt++;
	}
	
	int res = 1;
	while(cnt--){
		res = res * 2ll % mod;
	}
	
	cout<<res<<"\n";
}

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