제출 #1299325

#제출 시각아이디문제언어결과실행 시간메모리
1299325Jawad_Akbar_JJPort Facility (JOI17_port_facility)C++20
0 / 100
724 ms1114112 KiB
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
const int N = (1<<21) + 1;
int pr[N<<1], cnt[N<<1], Seen[N], Par[N];

int root(int v){
	return (Par[v] == 0 or Par[v] == v ? v : Par[v] = root(Par[v]));
}

void change(int id, int vl){
	if (cnt[id] == 0)
		pr[id] = 0;
	if (pr[id])
		Par[root(pr[id])] = vl;
	pr[id] = vl;
}

void push(int cur, int lc, int rc){
	change(lc, pr[cur]);
	change(rc, pr[cur]);
	pr[cur] = 0;
}

void insert(int l, int r, int cur = 1, int st = 1, int en = N){
	// cout<<cur<<" "<<st<<" "<<en<<endl;
	if (l >= en or r <= st)
		return;
	if (l <= st and r >= en){
		change(cur, r);
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	if (pr[cur])
		push(cur, lc, rc);
	insert(l, r, lc, st, mid);
	insert(l, r, rc, mid, en);
}

void Add(int i, int cur = 1, int st = 1, int en = N){
	if (i >= en or i < st)
		return;
	cnt[cur]++;
	if (en - st == 1){
		pr[cur] = i;
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	if (pr[cur])
		push(cur, lc, rc);
	Add(i, lc, st, mid);
	Add(i, rc, mid, en);
}

void process(int cur = 1, int st = 1, int en = N){
	if (en - st == 1){
		return;
	}
	int lc = cur + cur, rc = lc + 1, mid = (st + en) / 2;
	if (pr[cur])
		push(cur, lc, rc);
	process(lc, st, mid);
	process(rc, mid, en);
}

int main(){
	int n, Ans = 1, mod = 1e9 + 7;
	cin>>n;

	vector<pair<int, int>> vec;
	for (int i=1, a, b;i<=n;i++){
		cin>>a>>b;
		vec.push_back({a, b});
	}
	sort(begin(vec), end(vec));

	for (auto [l, r] : vec){
		insert(l, r);
		Add(r);
	}
	process();
	
	set<int> A = {0}, B = {0};
	for (auto [l, r] : vec){
		if (*prev(A.upper_bound(r)) <= l)
			A.insert(r);
		else if (*prev(B.upper_bound(r)) <= l)
			B.insert(r);
		else
			Ans = 0;
		Seen[root(r)] = 1;
	}
	for (int i=1;i<N;i++){
		Ans = Ans + Ans * Seen[i];
		if (Ans >= mod)
			Ans -= mod;
	}
	cout<<Ans<<'\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...