Submission #1005126

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005126		pavement	Tiles (BOI24_tiles)	C++17	100 / 100	270 ms	27896 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, odd_len, 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) {
		if (cnt[!(x % 2)] == 0) {
			ans = 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);
				}
			}
			for (auto it : to_erase) {
				if (s.find(*it) == s.end()) {
					continue;
				}
				cnt[get<2>(*it)]--;
				if ((get<1>(*it) - get<0>(*it)) % 2 == 1) {
					odd_len--;
				}
				s.erase(it);
			}
			for (auto v : to_insert) {
				cnt[get<2>(v)]++;
				if ((get<1>(v) - get<0>(v)) % 2 == 1) {
					odd_len++;
				}
				s.insert(v);
			}
			to_erase.clear();
			to_insert.clear();
			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) {
				if (s.find(*it) == s.end()) {
					continue;
				}
				cnt[get<2>(*it)]--;
				if ((get<1>(*it) - get<0>(*it)) % 2 == 1) {
					odd_len--;
				}
				s.erase(it);
			}
			for (auto v : to_insert) {
				cnt[get<2>(v)]++;
				if ((get<1>(v) - get<0>(v)) % 2 == 1) {
					odd_len++;
				}
				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) {
				if (s.find(*it) == s.end()) {
					continue;
				}
				cnt[get<2>(*it)]--;
				if ((get<1>(*it) - get<0>(*it)) % 2 == 1) {
					odd_len--;
				}
				s.erase(it);
			}
			bool should_insert = to_erase.empty();
			if (should_insert) {
				to_erase.clear();
				int lef = l, rig = r;
				it = s.lower_bound(mt(l, -1, -1));
				if (it != s.begin()) {
					--it;
					auto [l2, r2, p2] = *it;
					if (l == r2 && (x % 2) == p2) {
						to_erase.pb(it);
						lef = l2;
					}
				}
				it = s.lower_bound(mt(r, -1, -1));
				if (it != s.end()) {
					auto [l2, r2, p2] = *it;
					if (r == l2 && (x % 2) == p2) {
						to_erase.pb(it);
						rig = r2;
					}
				}
				for (auto it : to_erase) {
					if (s.find(*it) == s.end()) {
						continue;
					}
					cnt[get<2>(*it)]--;
					if ((get<1>(*it) - get<0>(*it)) % 2 == 1) {
						odd_len--;
					}
					s.erase(it);
				}
				cnt[x % 2]++;
				if ((rig - lef) % 2 == 1) {
					odd_len++;
				}
				s.emplace(lef, rig, x % 2);
			}
		}
		if (odd_len) {
			cout << ans << '\n';
			return 0;
		}
	}
	cout << ans << '\n';
}

• Subtask 1: 4 / 4
• Subtask 2: 9 / 9
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 22 / 22
• Subtask 6: 25 / 25
• Subtask 7: 10 / 10