#include<bits/stdc++.h>
using namespace std;
#define int long long
#define vec vector
#define arr array
const int INF = 1e17;
struct SegNode {
int size = 0;
int cnt_one = 0;
arr<int, 2> pref_cnt{0, 0};
arr<int, 2> suf_cnt{0, 0};
bool valid = true;
bool valid_all() {
return valid && ((pref_cnt[0] % 2) + (pref_cnt[1] % 2) + (suf_cnt[0] % 2) + (suf_cnt[1] % 2) == 0);
}
void debug() {
//cerr << size << ' ' << cnt_one << ' ' << pref_cnt[0] << ' ' << pref_cnt[1] <<' ' << valid << '\n';
}
SegNode merge(SegNode other) {
arr<int, 2> pref_cnt_n;
arr<int, 2> suf_cnt_n;
bool valid_n = valid & other.valid;
assert(pref_cnt[0] == 0 || pref_cnt[1] == 0);
assert(suf_cnt[0] == 0 || suf_cnt[1] == 0);
if(size+other.size == cnt_one+other.cnt_one || 0 == cnt_one+other.cnt_one) {
pref_cnt_n = {pref_cnt[0]+other.pref_cnt[0], pref_cnt[1]+other.pref_cnt[1]};
suf_cnt_n = pref_cnt_n;
}
else {
pref_cnt_n = pref_cnt;
suf_cnt_n = other.suf_cnt;
arr<int, 2> mid_cnt = {suf_cnt[0]+other.pref_cnt[0], suf_cnt[1]+other.pref_cnt[1]};
valid &= (mid_cnt[0] % 2 == 0) & (mid_cnt[1] % 2 == 0);
}
return {size + other.size, cnt_one+other.cnt_one, pref_cnt_n, suf_cnt_n, valid_n};
}
SegNode invert() {
return {size, size-cnt_one, {pref_cnt[1], pref_cnt[0]}, {suf_cnt[1], suf_cnt[0]}, valid};
}
};
struct SegTree {
int n;
vec<SegNode> data;
vec<bool> lazy;
SegTree(int n_i) {
n = 1;
while(n < n_i) n*= 2;
data = vec<SegNode>(n*2);
for(int i = n; i<n*2; i++) {
data[i].size = 1;
data[i].pref_cnt = {1, 0};
data[i].suf_cnt = {1, 0};
}
for(int i = n-1; i>=1; i--) {
data[i] = data[i*2].merge(data[i*2+1]);
}
lazy = vec<bool>(n*2);
}
void push(int i) {
if(!lazy[i]) {
return;
}
lazy[i] = false;
data[i] = data[i].invert();
if(i*2 > n*2) {
return;
}
lazy[i*2] = !lazy[i*2];
lazy[i*2+1] = !lazy[i*2+1];
}
SegNode _query(int l, int r, int ti, int tl, int tr) {
push(ti);
if(tl >= r || tr <= l) {
return {};
}
if(tl >= l && tr <= r) {
return data[ti];
}
int tm = (tl+tr)/2;
return _query(l, r, ti*2, tl, tm).merge(_query(l, r, ti*2+1, tm, tr));
}
SegNode query(int l, int r) {
return _query(l, r, 1, 0, n);
}
void _invert(int l, int r, int ti, int tl, int tr) {
push(ti);
if(tl >= r || tr <= l) {
return;
}
if(l <= tl && r >= tr) {
lazy[ti] = true;
push(ti);
return;
}
int tm = (tl+tr)/2;
_invert(l, r, ti*2, tl, tm);
_invert(l, r, ti*2+1, tm, tr);
data[ti] = data[ti*2].merge(data[ti*2+1]);
}
void invert(int l, int r) {
_invert(l, r, 1, 0, n);
}
};
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N, M;
cin >> N >> M;
vec<pair<int, int>> ps(N);
vec<int> ys(N);
for(int i = 0; i<N; i++) {
cin >> ps[i].first >> ps[i].second;
ys[i] = ps[i].second;
}
SegTree st(N*3);
sort(ys.begin(), ys.end());
map<int, int> ycompr;
int sub = ys[0];
for(int i = 0; i<ys.size(); i++) {
if(i>0) {
int diff = ys[i]-ys[i-1];
if(diff > 0) {
sub += diff;
sub -= 2;
sub += diff%2;
}
}
ycompr[ys[i]] = ys[i]-sub;
ys[i] -= sub;
}
for(int i = 0; i<N; i++) ps[i].second = ycompr[ps[i].second];
map<int, vec<pair<int, int>>> versegs;
for(int i = 0; i<N; i++) {
if(ps[i].first == ps[(i+1)%N].first) {
versegs[ps[i].first].push_back({min(ps[i].second, ps[(i+1)%N].second), max(ps[i].second, ps[(i+1)%N].second)});
}
}
int ans = M;
map<int, pair<int, int>> actsegs;
auto handlerectangle = [&](int l, int r, int u, int d) {
if(r-l == 0) return;
auto node = st.query(d, u);
node.debug();
if(!node.valid_all()) {
ans = min(ans, l - (node.cnt_one > 0));
}
else {
assert((u-d) % 2 == 0);
}
if((r-l) % 2) st.invert(d, u);
};
for(auto [x, versegs_x] : versegs) {
for(auto verseg : versegs_x) {
auto actseg_u_it = actsegs.upper_bound(verseg.first);
if(actseg_u_it != actsegs.begin()) {
auto actseg_d_it = actseg_u_it;
actseg_d_it--;
auto actseg_d = *actseg_d_it;
if(actseg_d.first <= verseg.first && actseg_d.second.first > verseg.first) {
assert(actseg_d.second.first >= verseg.second);
// removal
actsegs.erase(actseg_d.first);
if(verseg.first > actseg_d.first) {
actsegs.insert({actseg_d.first, {verseg.first, x}});
}
if(verseg.second < actseg_d.second.first) {
actsegs.insert({verseg.second, {actseg_d.second.first, x}});
}
handlerectangle(actseg_d.second.second, x, actseg_d.second.first, actseg_d.first);
if(st.query(verseg.first, verseg.second).cnt_one != 0) {
ans = min(ans, x-1);
}
continue;
}
}
// we haven't removed anything, maybe we are touchign tho
actseg_u_it = actsegs.upper_bound(verseg.first);
if(actseg_u_it != actsegs.end()) {
auto actseg_u = *actseg_u_it;
assert(actseg_u.first >= verseg.second);
if(actseg_u.first == verseg.second) {
actsegs.erase(actseg_u.first);
handlerectangle(actseg_u.second.second, x, actseg_u.second.first, actseg_u.first);
verseg.second = actseg_u.second.first;
}
}
actseg_u_it = actsegs.upper_bound(verseg.first);
if(actseg_u_it != actsegs.begin()) {
auto actseg_d_it = actseg_u_it;
actseg_d_it--;
auto actseg_d = *actseg_d_it;
assert(actseg_d.second.first <= verseg.first);
if(actseg_d.second.first == verseg.first) {
actsegs.erase(actseg_d.first);
handlerectangle(actseg_d.second.second, x, actseg_d.second.first, actseg_d.first);
verseg.first = actseg_d.first;
}
}
actsegs.insert({verseg.first, {verseg.second, x}});
}
}
cout << ans << '\n';
}
Compilation message
Main.cpp: In function 'int32_t main()':
Main.cpp:147:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
147 | for(int i = 0; i<ys.size(); i++) {
| ~^~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
3 ms |
2652 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Runtime error |
2 ms |
2652 KB |
Execution killed with signal 6 |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
241 ms |
277072 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
