제출 #559488

#제출 시각아이디문제언어결과실행 시간메모리
559488amunduzbaevPort Facility (JOI17_port_facility)C++17
22 / 100
42 ms32744 KiB
#include "bits/stdc++.h"
using namespace std;

#define ar array
#define int long long

//~ struct ST{
	
//~ };

const int N = 2e3 + 5;
const int mod = 1e9 + 7;
vector<int> edges[N];
int l[N], r[N], id[N], used[N];
int c[N];

void dfs(int u){
	used[u] = 1;
	for(auto x : edges[u]){
		if(used[x]){
			if(c[x] == c[u]){
				cout<<0<<"\n";
				exit(0);
			} 
		} else {
			c[x] = c[u] ^ 1;
			dfs(x);
		}
	}
}

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=0;i<n;i++){
		cin>>l[i]>>r[i];
	}
	
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			if((l[i] < l[j] && r[i] < r[j] && l[j] < r[i]) || (l[j] < l[i] && r[j] < r[i] && l[i] < r[j])){
				edges[i].push_back(j);
				edges[j].push_back(i);
			}
		}
	}
	
	int c = 0;
	for(int i=0;i<n;i++){
		if(used[i]) continue;
		dfs(i); c++;
	}
	
	int res = 1;
	while(c--){
		res = res * 2ll % mod;
	}
	
	cout<<res<<"\n";
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...