제출 #1166956

#제출 시각아이디문제언어결과실행 시간메모리
1166956IskachunTiles (BOI24_tiles)C++20
100 / 100
89 ms13556 KiB
#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 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...