Submission #1299330

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299330		Jawad_Akbar_JJ	Port Facility (JOI17_port_facility)	C++20	0 / 100	15 ms	8732 KiB

port_facility

#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], lst[N], cr;

int root(int v, int k){
	if (lst[v] == cr)
		return v;
	lst[v] = cr;
	return (Par[v] == v ? v : Par[v] = root(Par[v], k));
}
int root(int v){
	cr++;
	return root(v, 1);
}

void change(int id, int vl){
	if (cnt[id] == 0)
		pr[id] = 0;
	if (pr[id]){
		int rt = root(pr[id]);
		if (rt != vl)
			Par[rt] = 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(){
	for (int i=1;i<N;i++)
		Par[i] = i;
	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';
}

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