Submission #251347

#	Time	Username	Problem	Language	Result	Execution time	Memory
251347		imeimi2000	Hamburg Steak (JOI20_hamburg)	C++17	100 / 100	526 ms	28128 KiB

hamburg

#include <bits/stdc++.h>
#define x first
#define y second
#define x1 x.x
#define y1 x.y
#define x2 y.x
#define y2 y.y

using namespace std;
typedef pair<int, int> pii;
typedef pair<pii, pii> ppp;

const int inf = 1e9 + 5;

void flip_x(ppp &i) {
    swap(i.x1, i.x2);
    i.x1 = inf - i.x1;
    i.x2 = inf - i.x2;
}

struct get_min {
    vector<pii> V;
    void add(int p, int x) {
        V.emplace_back(p, x);
    }
    void init() {
        V.emplace_back(-inf, inf);
        sort(V.begin(), V.end());
        int mn = inf;
        for (pii &i : V) {
            mn = min(mn, i.y);
            i.y = mn;
        }
    }
    int find(int x) const {
        return (lower_bound(V.begin(), V.end(), pii(x, -inf)) - 1)->y;
    }
};

vector<pii> solve4(vector<ppp> R, int l, int d, int r, int u) {
    // u > d
    int l1 = d, l2 = u;
    int d1 = l, d2 = r;
    int r1 = d, r2 = u;
    int u1 = l, u2 = r;
    get_min ld, dr, ru, ul, du;
    vector<int> cp;
    multiset<int> Ls, Rs;
    Ls.insert(-inf);
    Rs.insert(inf);
    vector<pii> M;
    for (ppp i : R) {
        int in_l = i.x1 <= l, in_d = d >= i.y1;
        int in_r = i.x2 >= r, in_u = u <= i.y2;
        int cnt = in_l + in_d + in_r + in_u;
        if (in_l) cp.push_back(i.y1), cp.push_back(i.y2);
        assert(cnt > 0);
        if (cnt > 2) continue;
        if (cnt == 1) {
            if (in_l) {
                l1 = max(l1, i.y1);
                l2 = min(l2, i.y2);
            }
            if (in_d) {
                d1 = max(d1, i.x1);
                d2 = min(d2, i.x2);
            }
            if (in_r) {
                r1 = max(r1, i.y1);
                r2 = min(r2, i.y2);
            }
            if (in_u) {
                u1 = max(u1, i.x1);
                u2 = min(u2, i.x2);
            }
            continue;
        }
        if (in_l && in_r) {
            Ls.insert(i.y1);
            Rs.insert(i.y2);
            M.emplace_back(i.y1, i.y2);
            M.emplace_back(i.y2, -i.y1);
            continue;
        }
        if (in_d && in_u) {
            u1 = max(u1, i.x1);
            d2 = min(d2, i.x2);
            du.add(i.x2, -i.x1);
            continue;
        }
        if (in_l && in_d) ld.add(i.y2 - d, i.x2 - l);
        if (in_d && in_r) dr.add(r - i.x1, i.y2 - d);
        if (in_r && in_u) ru.add(u - i.y1, r - i.x1);
        if (in_u && in_l) ul.add(i.x2 - l, u - i.y1);
    }
    vector<pii> ret;
    if (l1 > l2 || d1 > d2 || r1 > r2 || u1 > u2) return ret;
    sort(M.rbegin(), M.rend());
    du.init();
    if (d2 < u1 && d2 < -du.find(u1)) return ret;
    ld.init();
    dr.init();
    ru.init();
    ul.init();
    sort(cp.begin(), cp.end());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    for (int ly : cp) {
        if (ly < l1 || l2 < ly) continue;
        while (!M.empty() && M.back().x <= ly) {
            auto [x, y] = M.back();
            M.pop_back();
            if (y < 0) {
                Ls.insert(-y);
                Rs.insert(x);
            }
            else {
                Ls.erase(Ls.find(x));
                Rs.erase(Rs.find(y));
            }
        }
        int dx = min(d2, l + ld.find(ly - d));
        if (dx < d1) continue;
        int ry = min({ r2, d + dr.find(r - dx), *Rs.begin() });
        if (ry < r1 || ry < *Ls.rbegin()) continue;
        int ux = max(u1, r - ru.find(u - ry));
        if (u2 < ux) continue;
        if (dx < ux && dx < -du.find(ux)) continue;
        if (ly < u - ul.find(ux - l)) continue;
        ret.emplace_back(l, ly);
        ret.emplace_back(dx, d);
        ret.emplace_back(r, ry);
        ret.emplace_back(ux, u);
        break;
    }
    return ret;
}

vector<pii> solve(vector<ppp> R, int k) {
    if (R.empty()) return vector<pii>(k, pii(1, 1));
    int l = inf, d = inf, r = 0, u = 0;
    for (ppp i : R) {
        l = min(l, i.x2);
        d = min(d, i.y2);
        r = max(r, i.x1);
        u = max(u, i.y1);
    }
    if (k == 1) {
        vector<pii> ret;
        if (r <= l && u <= d) ret.emplace_back(l, d);
        return ret;
    }
    for (int x : { l, r }) for (int y : { d, u }) {
        vector<ppp> nxt;
        for (ppp i : R) {
            if (i.x1 <= x && x <= i.x2 && i.y1 <= y && y <= i.y2) continue;
            nxt.push_back(i);
        }
        vector<pii> ret = solve(nxt, k - 1);
        if (ret.empty()) continue;
        ret.emplace_back(x, y);
        return ret;
    }
    if (k <= 3) return vector<pii>();
    assert(l < r && d < u);
    for (int i = 0; i < 2; ++i) {
        vector<pii> ans = solve4(R, l, d, r, u);
        if (!ans.empty()) {
            for (pii &p : ans) if (i) p.x = inf - p.x;
            return ans;
        }
        for (ppp &i : R) flip_x(i);
        swap(l, r);
        l = inf - l;
        r = inf - r;
    }
    return vector<pii>();
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, k;
    cin >> n >> k;
    vector<ppp> R(n);
    for (int i = 0; i < n; ++i) {
        cin >> R[i].x1 >> R[i].y1 >> R[i].x2 >> R[i].y2;
    }
    vector<pii> ans = solve(R, k);
    assert(!ans.empty());
    for (pii i : ans) printf("%d %d\n", i.x, i.y);
    return 0;
}

• Subtask 1: 1 / 1
• Subtask 2: 1 / 1
• Subtask 3: 3 / 3
• Subtask 4: 6 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 79 / 79