Submission #1369798

#TimeUsernameProblemLanguageResultExecution timeMemory
1369798Jawad_Akbar_JJPort Facility (JOI17_port_facility)C++20
78 / 100
5182 ms1014224 KiB
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
const int N = 1<<20;
vector<int> nei[N<<5], adj[N], Lst[N][21], vec;
int L[N], R[N], Num[N<<5], rMx[N<<1], Par[N][21], Mx[N][21], cur = N, Ans = 1;

void Col(int u, int c){
	Num[u] = c;
	for (int i : nei[u]){
		if (!Num[i])
			Col(i, 3 - c);
		if (Num[i] != 3 - c)
			Ans = 0;
	}
}

void Add(int i, int j){
	nei[i].push_back(j);
	nei[j].push_back(i);
}

void dfs(int u, int p){
	Par[u][0] = p, Mx[u][0] = R[u];

	for (int i=0;i<20;i++){
		Par[u][i+1] = Par[Par[u][i]][i];
		Mx[u][i+1] = Mx[Par[u][i]][i];
	}

	for (int i : adj[u])
		dfs(i, u);
}

int getMx(int l, int r, int ans = 0){
	for (l += N - 1, r += N + 1; l + 1 < r; l /= 2, r /= 2){
		if (!(l & 1))
			ans = max(ans, rMx[l ^ 1]);
		if (r & 1)
			ans = max(ans, rMx[r ^ 1]);
	}
	return ans;
}

void solve(int n, int S = 0){
	set<pair<int, int>> st;

	for (int i=0;i<=n;i++)
		vec.push_back(i);
	sort(begin(vec), end(vec), [](int i, int j){return L[i] < L[j];});

	for (int i : vec){
		int l = L[i], r = R[i];

		while (st.size() > 0 and (*begin(st)).first < l)
			st.erase(begin(st));

		auto u = st.upper_bound({r, r});
		if (u != st.end())
			adj[(*u).second].push_back(i);
		st.insert({r, i});
	}

	dfs(0, 0);

	st.clear();
	for (int I : vec){
		
		while (st.size() > 0 and (*begin(st)).first < L[I])
			st.erase(begin(st));

		if (st.size() > 0 and (*begin(st)).first < R[I]){
			auto [k, x] = *prev(st.upper_bound({R[I], R[I]}));
			if (getMx(L[I], R[x]) > R[I])
				Ans = 0;
			k = (*begin(st)).second;

			for (int i=20; i+1; i--){
				if (Mx[k][i] < R[I])
					Lst[k][i].push_back(I), k = Par[k][i];
			}
		}
		st.insert({R[I], I});
	}

	for (int j=20; j + 1;j--){
		for (int i=1;i<=n;i++){
			if (Lst[i][j].size() == 0)
				continue;
			int id = (!j ? i : ++cur);

			for (int k : Lst[i][j])
				Add(id, k);
			
			if (j){
				cur++;
				Add(id, cur);
				Lst[i][j-1].push_back(cur);
				Lst[Par[i][j-1]][j-1].push_back(cur);
			}
			vector<int> ().swap(Lst[i][j]);
		}
	}
}

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL);
	int n;
	cin>>n;

	R[0] = n + n + 1;
	for (int i=1;i<=n;i++){
		cin>>L[i]>>R[i];

		for (int j=L[i]+N; j; j /= 2)
			rMx[j] = max(rMx[j], R[i]);
	}

	solve(n);

	for (int i=1;i<=n;i++){
		if (Num[i] == 0)
			Ans = (Ans + Ans) % 1000000007, Col(i, 1);
	}

	cout<<Ans<<'\n';
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...