Submission #373538

#	Time	Username	Problem	Language	Result	Execution time	Memory
373538		casperwang	Port Facility (JOI17_port_facility)	C++14	100 / 100	1811 ms	144280 KiB

port_facility

#include <bits/stdc++.h>
#define pb push_back
#define All(x) x.begin(), x.end()
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
#define debug(args...) kout("[ " + string(#args) + " ]", args)
void kout() { cerr << endl; }
template <class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ',kout(b...); }
template <class T> void pary(T L, T R) { while (L != R) cerr << *L << " \n"[++L==R]; }

const int MAXN = 1000000;
const int MOD = 1000000007;
int n;
vector <tuple<int,int,int>> qry;
int L[MAXN+1];
int R[MAXN+1];
stack <int> stk;
vector <int> path[MAXN+1];
int vis[MAXN+1];
bool tf = true;
int ans = 1;

void DFS(int now, int flag) {
	vis[now] = flag;
	for (int i : path[now]) {
		if (!vis[i]) {
			DFS(i, 3 - flag);
		} else {
			tf &= (flag + vis[i] == 3);
		}
	}
}

signed main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	qry.resize(n);
	for (int i = 0; i < n; i++) {
		auto &[l, r, id] = qry[i];
		cin >> l >> r;
		id = i+1;
		L[id] = l;
		R[id] = r;
	}
	sort(All(qry), [](const tuple<int,int,int> a, const tuple<int,int,int> b) {
		return get<1>(a) < get<1>(b);
	});
	for (int i = 0; i < n; i++) {
		auto [l, r, id] = qry[i];
		while (stk.size() && l < L[stk.top()])
			stk.pop();
		if (stk.size() && l < R[stk.top()]) {
			path[stk.top()].pb(id);
			path[id].pb(stk.top());
		}
		stk.push(id);
	}
	while (stk.size()) stk.pop();
	sort(All(qry), [](const tuple<int,int,int> a, const tuple<int,int,int> b) {
		return get<0>(a) > get<0>(b);
	});
	for (int i = 0; i < n; i++) {
		auto [l, r, id] = qry[i];
		while (stk.size() && r > R[stk.top()])
			stk.pop();
		if (stk.size() && r > L[stk.top()]) {
			path[stk.top()].pb(id);
			path[id].pb(stk.top());
		}
		stk.push(id);
	}
	for (int i = 1; i <= n; i++) {
		if (!vis[i]) {
			DFS(i, 1);
			ans = ans * 2 % MOD;
		}
	}
	sort(All(qry), [](const tuple<int,int,int> a, const tuple<int,int,int> b) {
		return get<1>(a) < get<1>(b);
	});
	while (stk.size()) stk.pop();
	for (int i = 0; i < n; i++) {
		auto [l, r, id] = qry[i];
		if (vis[id] == 2) continue;
		while (stk.size() && l < L[stk.top()])
			stk.pop();
		if (stk.size() && l < R[stk.top()])
			tf = false;
		stk.push(id);
	}
	while (stk.size()) stk.pop();
	for (int i = 0; i < n; i++) {
		auto [l, r, id] = qry[i];
		if (vis[id] == 1) continue;
		while (stk.size() && l < L[stk.top()])
			stk.pop();
		if (stk.size() && l < R[stk.top()])
			tf = false;
		stk.push(id);
	}
	if (tf)
		cout << ans << '\n';
	else
		cout << 0 << '\n';
	return 0;
}

Compilation message (stderr)

port_facility.cpp: In function 'int main()':
port_facility.cpp:41:9: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   41 |   auto &[l, r, id] = qry[i];
      |         ^
port_facility.cpp:51:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   51 |   auto [l, r, id] = qry[i];
      |        ^
port_facility.cpp:65:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   65 |   auto [l, r, id] = qry[i];
      |        ^
port_facility.cpp:85:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |   auto [l, r, id] = qry[i];
      |        ^
port_facility.cpp:95:8: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   95 |   auto [l, r, id] = qry[i];
      |        ^

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