oj.uz

Submission #1005100

# Submission time Handle Problem Language Result Execution time Memory
1005100 2024-06-22T07:11:48 Z pavement Flooding Wall (BOI24_wall) C++17
0 / 100
 1 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -