Submission #251341

#	Time	Username	Problem	Language	Result	Execution time	Memory
251341		imeimi2000	Hamburg Steak (JOI20_hamburg)	C++17	15 / 100	208 ms	19908 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;
}

void flip_y(ppp &i) {
    swap(i.y1, i.y2);
    i.y1 = inf - i.y1;
    i.y2 = inf - i.y2;
}

struct get_min {
    vector<pii> V;
    void add(int p, int x) {
        V.emplace_back(p, x);
    }
    void init() {
        V.emplace_back(-5, 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) {
    // l > r and 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, rl, du;
    vector<int> cp;
    for (ppp &i : R) {
        i.x1 = max(i.x1, l);
        i.y1 = max(i.y1, d);
        i.x2 = min(i.x2, r);
        i.y2 = min(i.y2, u);
        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);
        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) {
            l1 = max(l1, i.y1);
            r2 = min(r2, i.y2);
            rl.add(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);
    }
    ld.init();
    dr.init();
    ru.init();
    ul.init();
    sort(cp.rbegin(), cp.rend());
    cp.erase(unique(cp.begin(), cp.end()), cp.end());
    vector<pii> ret;
    for (int ly : cp) {
        if (ly < l1 || l2 < ly) continue;
        int dx = min(d2, l + ld.find(ly - d));
        if (dx < d1) continue;
        int ry = min(r2, d + dr.find(r - dx));
        if (ry < r1) continue;
        if (ly > ry && ry < -rl.find(ly)) continue;
        int ux = max(u1, r - ru.find(u - ry));
        if (u2 < ux) continue;
        if (dx < ux && dx < -du.find(ux)) continue;
        if (u - ul.find(ux - l) < ly) 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) {
        for (int j = 0; j < 2; ++j) {
            vector<pii> ans = solve4(R, l, d, r, u);
            if (!ans.empty()) {
                for (pii &p : ans) {
                    if (i) p.x = inf - p.x;
                    if (j) p.y = inf - p.y;
                }
                return ans;
            }
            for (ppp &i : R) flip_y(i);
            swap(d, u);
            d = inf - d;
            u = inf - u;
        }
        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);
    if (ans.empty()) return 1;
    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: 0 / 6
• Subtask 5: 1 / 1
• Subtask 6: 3 / 3
• Subtask 7: 6 / 6
• Subtask 8: 0 / 79