Submission #1069180

#TimeUsernameProblemLanguageResultExecution timeMemory
10691800npataTiles (BOI24_tiles)C++17
4 / 100
92 ms43604 KiB
#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(1005); 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; } if(false) { 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 (stderr)

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++) {
      |                 ~^~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...