Submission #373085

#	Time	Username	Problem	Language	Result	Execution time	Memory
373085		Kevin_Zhang_TW	Port Facility (JOI17_port_facility)	C++17	10 / 100	16 ms	512 KiB

port_facility

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(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 debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 1000010, p = 1e9 + 7;

int n;
pair<int,int> sh[MAX_N];

int atpos[MAX_N];

struct sgt {
	int n;
	vector<int> mx;
	sgt (int n) : n(n) {
		mx.resize(n<<1, -1);
	}
	void modify(int i, int v) {
		i += n;
		mx[i] = v;
		for (;i>>=1;) 
			mx[i] = max(mx[i<<1], mx[i<<1|1]);
	}
	int qry(int l, int r) {
		int res = -1;
		l += n, r += n;
		for (;l < r;l>>=1, r>>=1) {
			if (l&1) chmax(res, mx[l++]);
			if (r&1) chmax(res, mx[--r]);
		}
		return res;
	}
	sgt () {}
}tree;

bool valid (int i, int j) {
	if (i > j) swap(i, j);
	return sh[i].second < sh[j].first || sh[j].second < sh[i].second;
}

bool vis[MAX_N];


ll trykill(int x) {
	vector<int> gp[2];
	queue<pair<int,int>> q;

	q.emplace(x, 0);

	while (q.size()) {
		auto [x, g] = q.front(); q.pop();

		gp[g].pb(x);

		auto [l, r] = sh[x];

		for (int j = 0;j < n;++j) if (!vis[j]) {
			if (!valid(x, j)) {
				vis[j] = true;
				q.emplace(j, g^1);
			}
		}
//		while (tree.qry(l, r) > r) {
//			int tr = tree.qry(l, r);
//			int id = atpos[tr];
//			auto [cl, cr] = sh[id];
//			q.emplace(id, g^1);
//			tree.modify(cl, -1);
//		}
	}

	auto allvalid = [&](vector<int> sid) {
		for (int u : sid) for (int v : sid) if (u != v && !valid(u, v))
			return false;
		return true;
		vector<int> stk;
		for (int u : sid) {
			auto [cl, cr] = sh[u];
			while (stk.size()) {
				auto [l, r] = sh[stk.back()];
				if (cl < r && cr > r) return false;
				if (cr < r) break;
				stk.pop_back();
			}
			stk.pb(u);
		}
		return true;
	};

//	DE(x);
//	debug(AI(gp[0]));
//	debug(AI(gp[1]));
//	cerr << endl;
//
	for (int i = 0;i < 2;++i)
		if (!allvalid(gp[i]))
			return 0;

	return 2;
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 0;i < n;++i)  {
		cin >> sh[i].first >> sh[i].second;
		--sh[i].first, --sh[i].second;
	}

	if (n > 2000) return -1;

	sort(sh, sh + n);

	tree = sgt(n * 2);

	for (int i = 0;i < n;++i) {
		auto [l, r] = sh[i];
		atpos[r] = atpos[l] = i;
		tree.modify(l, r);
	}

	ll res = 1;

	for (int i = 0;i < n;++i) {
		auto [l, r] = sh[i];
		if (vis[i]) continue;
		//if (tree.qry(l, l+1) == -1) continue;

		vis[i] = true;
		tree.modify(l, -1);

		res = res * trykill(i);
	}

	cout << res << '\n';
}

Compilation message (stderr)

port_facility.cpp: In function 'll trykill(int)':
port_facility.cpp:68:8: warning: structured binding declaration set but not used [-Wunused-but-set-variable]
   68 |   auto [l, r] = sh[x];
      |        ^~~~~~

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