제출 #1005100

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1005100		pavement	Flooding Wall (BOI24_wall)	C++17	0 / 100	1 ms	348 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ii = pair<int, int>;
using iii = tuple<int, int, int>;

#define pb push_back
#define eb emplace_back
#define mt make_tuple

int N, M, ans, x[200005], y[200005], cnt[2];
map<int, vector<ii> > vec;
vector<int> dist_x;
set<iii> s;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		cin >> x[i] >> y[i];
	}
	for (int i = 1; i <= N; i++) {
		int j = (i % N) + 1;
		if (x[i] == x[j]) {
			vec[x[i]].eb(min(y[i], y[j]), max(y[i], y[j]));
		}
		dist_x.pb(x[i]);
		if (x[i] > 0) {
			dist_x.pb(x[i] - 1);
		}
	}
	sort(dist_x.begin(), dist_x.end());
	dist_x.erase(unique(dist_x.begin(), dist_x.end()), dist_x.end());
	for (auto x : dist_x) {
		for (auto [l, r] : vec[x]) {
			vector<set<iii>::iterator> to_erase;
			vector<iii> to_insert;
			// insert (x % 2, l, r)
			auto it = s.lower_bound(mt(l, -1, -1));
			if (it != s.begin()) {
				--it;
				auto [l2, r2, p2] = *it;
				assert(l2 < l);
				if (l < r2) {
					to_erase.pb(it);
					to_insert.eb(l2, l, p2);
					to_insert.eb(l, r2, p2);
				}
			}
			it = s.lower_bound(mt(r, -1, -1));
			if (it != s.begin()) {
				--it;
				auto [l2, r2, p2] = *it;
				assert(l2 < r);
				if (r < r2) {
					to_erase.pb(it);
					to_insert.eb(l2, r, p2);
					to_insert.eb(r, r2, p2);
				}
			}
			for (auto it : to_erase) {
				cnt[get<2>(*it)]--;
				s.erase(it);
			}
			for (auto v : to_insert) {
				cnt[get<2>(v)]++;
				s.insert(v);
			}
			to_erase.clear();
			for (auto it = s.lower_bound(mt(l, -1, -1)); it != s.end() && get<1>(*it) <= r; it++) {
				auto [l2, r2, p2] = *it;
				if (p2 != (x % 2)) {
					cout << ans << '\n';
					return 0;
				}
				to_erase.pb(it);
			}
			for (auto it : to_erase) {
				cnt[get<2>(*it)]--;
				s.erase(it);
			}
			if (to_erase.empty()) {
				cnt[x % 2]++;
				s.emplace(l, r, x % 2);
			}
		}
		if (cnt[!(x % 2)] == 0) {
			ans = x;
		}
	}
	cout << ans << '\n';
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 17
• Subtask 3: 0 / 19
• Subtask 4: 0 / 14
• Subtask 5: 0 / 12
• Subtask 6: 0 / 30