Submission #889056

#	Time	Username	Problem	Language	Result	Execution time	Memory
889056		vjudge1	Port Facility (JOI17_port_facility)	C++17	78 / 100	6103 ms	240596 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];
     
    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);
    	}
    	
    	while(true){
    		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();
    		}
    		int last = cmp.size();
    		cmp.clear();
    		for(int i=0;i<n;i++){
    			if(i == par[i]) cmp.push_back(i);
    		}
    		
    		if((int)cmp.size() == 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: 0 / 22