#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
struct seg { int l, r, par; };
bool operator < (seg a, seg b) {
if (a.l == b.l) return a.r < b.r;
return a.l < b.l;
}
void add (vector<int> a, int &cnt, vector<int> &par, set<seg> &inter) {
if ((a[2] - a[1] + 1) % 2 == 1) cnt++;
par[a[0] % 2]++;
inter.insert({a[1], a[2], a[0] % 2});
}
int n, m;
int next (int i) { return (i + 1) % n; }
void solve() {
cin >> n >> m;
vector<vector<int>> a;
vector<int> x(n), y(n);
for (int i = 0; i < n; i++) cin >> x[i] >> y[i];
for (int i = 0; i < n; i++) {
if (x[next(i)] == x[i]) {
if (y[i] < y[next(i)]) a.push_back({x[i], min(y[i], y[next(i)]), max(y[i], y[next(i)]) - 1, 1});
else a.push_back({x[i], min(y[i], y[next(i)]), max(y[i], y[next(i)]) - 1, -1});
}
}
sort(a.begin(), a.end());
if (a[0][3] == -1) {
for (int i = 0; i < a.size(); i++) a[i][3] = 0 - a[i][3];
}
int prev = -1, cnt = 0, mx = 0;
vector<int> par(2);
set<seg> inter;
for (int i = 0; i < a.size(); i++) {
if (a[i][0] != prev or i == a.size() - 1) {
prev = a[i][0];
if (cnt) break;
if (par[0] == 0 or par[1] == 0) {
int curr = (par[1] ? 1 : 0);
mx = ((a[i][0] % 2 == curr) ? a[i][0] : a[i][0] - 1);
}
}
if (a[i][3] == 1) {
auto pos = inter.lower_bound({a[i][1]});
if (pos != inter.end() and pos->l == a[i][2] + 1 and pos->par == (a[i][0] % 2)) {
a[i][2] = pos->r;
if ((pos->r - pos->l + 1) % 2) cnt--;
par[pos->par]--;
pos = inter.erase(pos);
}
if (pos != inter.begin()) {
pos--;
if (pos->r == a[i][1] - 1 and pos->par == (a[i][0] % 2)) {
a[i][1] = pos->l;
if ((pos->r + pos->l + 1) % 2) cnt--;
par[pos->par]--;
inter.erase(pos);
}
}
add(a[i], cnt, par, inter);
} else {
auto pos = inter.upper_bound({a[i][2], int(1e9)});
pos--;
if ((a[i][0] % 2) != pos->par) break;
if (a[i][1] < pos->l) break;
int left = pos->l, right = a[i][1] - 1;
if (right >= left) add({pos->par, left, right}, cnt, par, inter);
left = a[i][2] + 1, right = pos->r;
if (right >= left) add({pos->par, left, right}, cnt, par, inter);
par[pos->par]--;
if ((pos->r - pos->l + 1) % 2) cnt--;
inter.erase(pos);
}
}
cout << mx;
}
int main() {
//freopen("filename.in", "r", stdin), freopen("filename.out", "w", stdout);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int t = 1; //cin >> t;
while (t--) solve();
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |