Submission #671403

#	Time	Username	Problem	Language	Result	Execution time	Memory
671403		amunduzbaev	Port Facility (JOI17_port_facility)	C++17	0 / 100	0 ms	340 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;
int a[N], b[N], used[N], c[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];
	}
	
	auto is = [&](int i, int j){
		if(a[j] < a[i] && a[i] < b[j] && b[j] < b[i]){
			return true;
		} swap(j, i);
		if(a[j] < a[i] && a[i] < b[j] && b[j] < b[i]){
			return true;
		} return false;
	};
	
	vector<int> t[2];
	set<ar<int, 2>> inuse;
	function<void(int)> dfs = [&](int u){
		used[u] = 1;
		t[c[u]].push_back(u);
		for(int i=0;i<n;i++){
			if(used[i]) continue;
			if(is(u, i)){
				inuse.insert({u, i});
				c[i] = c[u] ^ 1;
				dfs(i);
			}
		}
	};
	
	int res = 1;
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		inuse.clear();
		t[0].clear(), t[1].clear();
		dfs(i);
		for(auto x : t[0]){
			for(auto y : t[1]){
				if(is(x, y) && !inuse.count({x, y}) && !inuse.count({y, x})){
					cout<<0<<"\n";
					return 0;
				}
			}
		}
		
		res = res * 2ll % mod;
	}
	
	cout<<res<<"\n";
}

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