Submission #427180

#TimeUsernameProblemLanguageResultExecution timeMemory
427180oolimryPort Facility (JOI17_port_facility)C++17
0 / 100
135 ms244176 KiB
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int) (x).size()
#define all(x) (x).begin(), (x).end()
#define show(x) cerr << #x << " is " << x << endl;
#define show2(x,y) cerr << #x << " is " << x << " " << #y << " is " << y << endl;
#define show3(x,y,z) cerr << #x << " is " << x << " " << #y << " is " << y << " " << #z << " is " << z << endl;
#define tern(cond, a, b) (cond ? a : b)
#define l first
#define r second
typedef long long lint;
typedef pair<int,int> ii;

const lint mod = 1000000007;

int p[2000005];
int ans;

int findSet(int u){
	if(p[u] == u) return u;
	else return p[u] = findSet(p[u]);
}

inline bool unionSet(int u, int v){
	u = findSet(u), v = findSet(v);
	if(u == v) return false;
	if(rand()&1) swap(u,v);
	p[u] = v;
	ans--;
	return true;
}


ii arr[1000005];

const int N = 1<<21;
map<int,int> tree[2*N];

inline map<int,int> merge(map<int,int> A, map<int,int> B){
	if(sz(A) > sz(B)) swap(A,B);
	for(ii x : A) B[x.first] += x.second;
	return B;
}

inline void update(int u, int h, int v){
	//show3(u,h,v);
	int i = arr[u].r + N;
	for(;i > 0;i >>= 1){
		if(v == 1){
			auto it = tree[i].find(h);
			if(it == tree[i].end()) tree[i][h] = v;
			else it->second += v;
		}
		else{
			auto it = tree[i].find(h);
			if(it != tree[i].end()) tree[i].erase(it);
			
			it = tree[i].find(h^1);
			if(it != tree[i].end()) tree[i].erase(it);
		}
	}
}

inline map<int,int> query(int l, int r){
	map<int,int> res;
	for(l += N, r += N;l < r;l >>= 1, r >>= 1){
		if(l&1) res = merge(res, tree[l++]);
		if(r&1) res = merge(res, tree[--r]);
	}
	return res;
}

vector<int> belongsto[1000005];
vector<int> adj[1000005];
int color[1000005];

inline int strip(int x){
	return (x|1)^1;
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(0);
	
	int n; cin >> n;
	ans = n;
	for(int i = 0;i < n;i++) cin >> arr[i].l >> arr[i].r;
	sort(arr,arr+n);
	for(int i = 0;i < n;i++){
		p[i] = i;
		belongsto[i].push_back(i);
	}
			
	for(int u = 0;u < n;u++){
		vector<int> stuffs = {};
		auto M = query(arr[u].l, arr[u].r);
		for(ii x : M) stuffs.push_back(x.first);
		
		//for(int i = 0;i < sz(stuffs);i++) cerr << stuffs[i] << " "; cerr << endl;
		if(sz(stuffs) == 0){
			update(u, 2*u, 1);
			continue;
		}
		
		sort(all(stuffs));
		for(int i = 0;i < sz(stuffs);i++) unionSet(u, stuffs[i]/2);
		
		for(int i = 1;i < sz(stuffs);i++){
			if((stuffs[i-1] | 1) == stuffs[i]){
				cout << 0;
				return 0;
			}
		}
		
		int newhead = findSet(u);
		int besthead = stuffs[0];
		if((newhead&1) != (besthead&1)) newhead ^= 1;
		
		
		for(int x : stuffs){
			if(sz(belongsto[x/2]) > sz(belongsto[besthead/2])){
				besthead = x;
			}
		}
		
		besthead = newhead;
		
		for(int h : stuffs){
			if(h == besthead) continue;
			for(int x : belongsto[h/2]){
				update(x, strip(h) + color[x], -1);
				
				if(color[h/2] != color[besthead/2]) color[x] ^= 1;
				
				update(x, strip(newhead) + color[x], 1);
				
				belongsto[besthead/2].push_back(x);
			}
		}
		belongsto[besthead/2].push_back(u);
		color[u] = color[besthead/2]^1;
		
		swap(belongsto[newhead/2], belongsto[besthead/2]);
		update(u, strip(newhead) + color[u], 1);
	}
	
	
	lint actlans = 1;
	for(int i = 0;i < ans;i++){
		actlans *= 2;
		if(actlans >= mod) actlans -= mod;
	}
	cout << actlans;
}

#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...