제출 #1369825

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

using namespace std;
const int N = 1<<21;
vector<int> nei[N], adj[N];
vector<pair<int, int>> A;
int Num[N], Up[N], rMx[N<<1], cur = N>>1, 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);
}

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 dfs2(int u){
	for (int i : adj[u]){
		dfs2(i);
		Up[u] = max(Up[u], Up[i]);

		if (Up[i] > A[u].second){
			Add(i, ++cur);
			Add(cur, u);
		}
	}
}

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

	for (int i=0;i<=n;i++){
		auto [l, r] = A[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});
	}

	st.clear();
	for (int i=0;i<=n;i++){
		auto [l, r] = A[i];

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

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

			Add(i, k);

			Up[k] = max(Up[k], r);
		}
		st.insert({r, i});
	}

	dfs2(0);
}


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

	A.resize(n);
	for (auto &[l, r] : A){
		cin>>l>>r;

		for (int j=l+N; j; j /= 2)
			rMx[j] = max(rMx[j], r);
	}
	A.push_back({0, n+n+1});
	sort(begin(A), end(A));

	solve(n);

	for (int i=1;i<=n;i++){
		if (Num[i] == 0)
			Ans = (Ans + Ans) % 1000000007, Col(i, 1);
	}
	cout<<Ans<<'\n';
}
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…
#결과 실행 시간메모리채점기 출력
결과를 불러오는 중입니다…