Submission #1369814

#TimeUsernameProblemLanguageResultExecution timeMemory
1369814Jawad_Akbar_JJPort Facility (JOI17_port_facility)C++20
100 / 100
3091 ms295356 KiB
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>

using namespace std;
const int N = 1<<20, M = 1<<21;
vector<int> nei[M], adj[N], vec;
int L[N], R[N], Num[M], Up[N], rMx[M<<1], 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);
}

int getMx(int l, int r, int ans = 0){
	for (l += M - 1, r += M + 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] > R[u]){
			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++)
		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});
	}

	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;
			Add(I, k);

			Up[k] = max(Up[k], R[I]);
		}
		st.insert({R[I], I});
	}

	dfs2(0);
}


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]+M; 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);
	}

	if (cur > N * 8)
		cout<<1 / 0;

	cout<<Ans<<'\n';
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:110:25: warning: division by zero [-Wdiv-by-zero]
  110 |                 cout<<1 / 0;
      |                       ~~^~~
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...