제출 #1166956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1166956		Iskachun	Tiles (BOI24_tiles)	C++20	100 / 100	89 ms	13556 KiB

Main

#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();
}

• Subtask 1: 4 / 4
• Subtask 2: 9 / 9
• Subtask 3: 11 / 11
• Subtask 4: 19 / 19
• Subtask 5: 22 / 22
• Subtask 6: 25 / 25
• Subtask 7: 10 / 10