Submission #889055

#	Time	Username	Problem	Language	Result	Execution time	Memory
889055		vjudge1	Port Facility (JOI17_port_facility)	C++17	100 / 100	2729 ms	223408 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