Submission #223862

#	Time	Username	Problem	Language	Result	Execution time	Memory
223862		Minnakhmetov	Hamburg Steak (JOI20_hamburg)	C++14	100 / 100	661 ms	34296 KiB

hamburg

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(aaa) aaa.begin(), aaa.end()

const int N = 4e5 + 5, INF = 1e9 + 5;

struct R {
    int xl, yl, xr, yr;

    bool contains(int x, int y) const {
        return x >= xl && x <= xr && y >= yl && y <= yr;
    }
    bool intersects_hor(int y) const {
        return y >= yl && y <= yr;
    }
    bool intersects_ver(int x) const {
        return x >= xl && x <= xr;
    }
};

vector<R> rcs;
vector<int> vx, vy;
vector<pair<int, int>> ans;
pair<int, int> suf_hor[N], pref_ver[N], suf_ver[N];
int pref[N], suf[N], suf_lt[N], suf_rt[N];

pair<int, int> intersection(pair<int, int> a, pair<int, int> b) {
    return {max(a.first, b.first), min(a.second, b.second)};
}

bool solve_for_line(vector<pair<int, int>> v, int k, bool hor, int x) {
    sort(all(v));
    int last = N;
    vector<int> w;
    for (int i = (int)v.size() - 1; i >= 0; i--) {
        if (v[i].second < last) {
            if (k == 0)
                return false;
            k--;
            last = v[i].first;
            w.push_back(last);
        }
    }
    for (int y : w) {
        ans.push_back(hor ? make_pair(y, x) : make_pair(x, y));
    }
    return true;
}

vector<R> remove_covered(vector<R> v, int x, int y) {
    vector<R> nv;
    for (const R &rc : v) {
        if (!rc.contains(x, y)) {
            nv.push_back(rc);
        }
    }
    return nv;
}

bool solve(vector<R> v, int k) {
    int mn_xr = N, mx_xl = -1, mn_yr = N, mx_yl = -1;

    for (R &rc : v) {
        mn_xr = min(mn_xr, rc.xr);
        mn_yr = min(mn_yr, rc.yr);
        mx_xl = max(mx_xl, rc.xl);
        mx_yl = max(mx_yl, rc.yl);
    }

    if (mn_xr >= mx_xl && mn_yr >= mx_yl) {
        ans.push_back({mn_xr, mn_yr});
        return true;
    }
    else if (mn_xr >= mx_xl) {
        vector<pair<int, int>> sgs;
        for (R &rc : v) {
            sgs.push_back({rc.yl, rc.yr});
        }
        if (solve_for_line(sgs, k, false, mn_xr))
            return true;
        return false;
    }
    else if (mn_yr >= mx_yl) {
        vector<pair<int, int>> sgs;
        for (R &rc : v) {
            sgs.push_back({rc.xl, rc.xr});
        }
        if (solve_for_line(sgs, k, true, mn_yr))
            return true;
        return false;
    }
    else if (k == 2) {
        for (int y : {mn_yr, mx_yl}) {
            if (solve(remove_covered(v, mn_xr, y), k - 1)) {
                ans.push_back({mn_xr, y});
                return true;
            }
        }
        return false;
    }
    else if (k >= 2) {
        for (int x : {mn_xr, mx_xl}) {
            for (int y : {mn_yr, mx_yl}) {
                if (solve(remove_covered(v, x, y), k - 1)) {
                    ans.push_back({x, y});
                    return true;
                }
            }
        }
        if (k == 3)
            return false;

        pair<int, int> up, rt, lt, dn;
        dn = up = {1, vx.size() - 2};
        lt = rt = {1, vy.size() - 2};

        fill(suf_hor, suf_hor + N, make_pair(1, vy.size() - 2));
        fill(pref_ver, pref_ver + N, make_pair(1, vx.size() - 2));
        fill(suf_ver, suf_ver + N, make_pair(1, vx.size() - 2));
        fill(pref, pref + N, vy.size() - 2);
        fill(suf, suf + N, vy.size() - 2);
        fill(suf_lt, suf_lt + N, vx.size() - 2);
        fill(suf_rt, suf_rt + N, 1);

        for (const R &rc : v) {
            bool d = rc.intersects_hor(mn_yr),
                u = rc.intersects_hor(mx_yl),
                l = rc.intersects_ver(mn_xr),
                r = rc.intersects_ver(mx_xl);

            int ct = d + u + l + r;
            if (ct == 1) {
                if (l)
                    lt = intersection(lt, {rc.yl, rc.yr});
                else if (r)
                    rt = intersection(rt, {rc.yl, rc.yr});
                else if (u)
                    up = intersection(up, {rc.xl, rc.xr});
                else
                    dn = intersection(dn, {rc.xl, rc.xr});
            }
            else if (ct == 2) {
                if (l && r) {
                    suf_hor[rc.yl] = intersection(suf_hor[rc.yl], 
                        make_pair(rc.yl, rc.yr));
                }
                else if (d && l) {
                    pref[rc.xr] = min(pref[rc.xr], rc.yr);
                }
                else if (d && r) {
                    suf[rc.xl] = min(suf[rc.xl], rc.yr);
                }
                else if (l && u) {
                    suf_lt[rc.yl] = min(rc.xr, suf_lt[rc.yl]);
                }
                else if (r && u) {
                    suf_rt[rc.yl] = max(rc.xl, suf_rt[rc.yl]);
                }
                else {
                    pref_ver[rc.xr] = intersection(pref_ver[rc.xr], {rc.xl, rc.xr});
                    suf_ver[rc.xl] = intersection(suf_ver[rc.xl], {rc.xl, rc.xr});
                }
            }
        }

        for (int i = N - 2; i >= 0; i--) {
            suf_hor[i] = intersection(suf_hor[i], suf_hor[i + 1]);
            suf_lt[i] = min(suf_lt[i], suf_lt[i + 1]);
            suf_rt[i] = max(suf_rt[i], suf_rt[i + 1]);
            suf_ver[i] = intersection(suf_ver[i], suf_ver[i + 1]);
            suf[i] = min(suf[i], suf[i + 1]);
        }

        for (int i = 1; i < N; i++) {
            pref_ver[i] = intersection(pref_ver[i], pref_ver[i - 1]);
            pref[i] = min(pref[i], pref[i - 1]);
        }

        for (int i = dn.first; i <= dn.second; i++) {
            int mx_lt = pref[i - 1],
                mx_rt = suf[i + 1];

            pair<int, int> nup = intersection(up, 
                intersection(pref_ver[i - 1], suf_ver[i + 1]));

            if (nup.first > nup.second) {
                continue;
            }

            int y_lt = min(mx_lt, suf_hor[0].second);
            y_lt = min(y_lt, lt.second);
            if (y_lt < lt.first) {
                continue;
            }

            pair<int, int> nrt = intersection(rt, suf_hor[y_lt + 1]);
            if (nrt.first > nrt.second) {
                continue;
            }

            int y_rt = min(mx_rt, nrt.second);

            if (y_rt < nrt.first)
                continue;

            nup = intersection(nup, make_pair(suf_rt[y_rt + 1], suf_lt[y_lt + 1]));

            if (nup.first > nup.second) {
                continue;
            }

            ans.push_back({i, mn_yr});
            ans.push_back({mn_xr, y_lt});
            ans.push_back({mx_xl, y_rt});
            ans.push_back({nup.first, mx_yl});

            return true;
        }

        for (int i = dn.first; i <= dn.second; i++) {
            int mx_lt = pref[i - 1],
                mx_rt = suf[i + 1];

            pair<int, int> nup = intersection(up, 
                intersection(pref_ver[i - 1], suf_ver[i + 1]));

            if (nup.first > nup.second) {
                continue;
            }

            int y_rt = min(mx_rt, suf_hor[0].second);
            y_rt = min(y_rt, rt.second);
            if (y_rt < rt.first) {
                continue;
            }

            pair<int, int> nlt = intersection(lt, suf_hor[y_rt + 1]);
            if (nlt.first > nlt.second) {
                continue;
            }

            int y_lt = min(mx_lt, nlt.second);

            if (y_lt < nlt.first)
                continue;

            nup = intersection(nup, make_pair(suf_rt[y_rt + 1], suf_lt[y_lt + 1]));

            if (nup.first > nup.second) {
                continue;
            }

            ans.push_back({i, mn_yr});
            ans.push_back({mn_xr, y_lt});
            ans.push_back({mx_xl, y_rt});
            ans.push_back({nup.first, mx_yl});

            return true;
        }
    }
    return false;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n, k;
    cin >> n >> k;

    for (int i = 0; i < n; i++) {
        R r;
        cin >> r.xl >> r.yl >> r.xr >> r.yr;
        vx.push_back(r.xl);
        vx.push_back(r.xr);
        vy.push_back(r.yl);
        vy.push_back(r.yr);
        rcs.push_back(r);
    }

    vx.push_back(-1);
    vx.push_back(INF);

    vy.push_back(-1);
    vy.push_back(INF);

    sort(all(vx));
    vx.erase(unique(all(vx)), vx.end());
    sort(all(vy));
    vy.erase(unique(all(vy)), vy.end());

    for (int i = 0; i < n; i++) {
        rcs[i].xl = lower_bound(all(vx), rcs[i].xl) - vx.begin();
        rcs[i].xr = lower_bound(all(vx), rcs[i].xr) - vx.begin();
        rcs[i].yl = lower_bound(all(vy), rcs[i].yl) - vy.begin();
        rcs[i].yr = lower_bound(all(vy), rcs[i].yr) - vy.begin();
    }

    solve(rcs, k);

    while (ans.size() < k)
        ans.push_back({1, 1});

    for (auto p : ans) {
        cout << vx[p.first] << " " << vy[p.second] << "\n";
    }

    return 0;
}       

Compilation message (stderr)

hamburg.cpp: In function 'int main()':
hamburg.cpp:303:23: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  303 |     while (ans.size() < k)
      |            ~~~~~~~~~~~^~~

• 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