oj.uz

Submission #223849

# Submission time Handle Problem Language Result Execution time Memory
223849 2020-04-16T14:43:11 Z Minnakhmetov Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 384 ms 25632 KB 
#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);

            // cout << mn_yr << " " << rc.yl << " " << rc.yr << "\n";

            // cout << d << " " << u << " " << l << " " << r << "\n";

            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 = nrt.second;

            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, lt.second);
            if (y_rt < lt.first) {
                continue;
            }

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

            int y_lt = nlt.second;

            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

hamburg.cpp: In function 'bool solve(std::vector<R>, int)':
hamburg.cpp:187:17: warning: unused variable 'mx_rt' [-Wunused-variable]
  187 |                 mx_rt = suf[i + 1];
      |                 ^~~~~
hamburg.cpp:224:17: warning: unused variable 'mx_lt' [-Wunused-variable]
  224 |             int mx_lt = pref[i - 1],
      |                 ^~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:301: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]
  301 |     while (ans.size() < k)
      |            ~~~~~~~~~~~^~~

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct

Subtask #2
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 508 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Incorrect 18 ms 16216 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 315 ms 10004 KB Output is correct
6 Correct 346 ms 10012 KB Output is correct
7 Correct 332 ms 9964 KB Output is correct
8 Correct 335 ms 10028 KB Output is correct

Subtask #6
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 331 ms 16192 KB Output is correct
6 Correct 347 ms 15996 KB Output is correct
7 Correct 353 ms 16068 KB Output is correct
8 Correct 364 ms 19104 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 3 ms 508 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 5 ms 512 KB Output is correct
7 Correct 3 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 363 ms 13336 KB Output is correct
14 Correct 373 ms 13392 KB Output is correct
15 Correct 363 ms 13396 KB Output is correct
16 Correct 349 ms 13424 KB Output is correct
17 Correct 358 ms 13416 KB Output is correct
18 Correct 378 ms 13376 KB Output is correct
19 Correct 322 ms 18328 KB Output is correct
20 Correct 330 ms 19652 KB Output is correct
21 Correct 384 ms 25632 KB Output is correct
22 Correct 343 ms 19884 KB Output is correct
23 Correct 361 ms 23628 KB Output is correct
24 Correct 364 ms 24900 KB Output is correct

Subtask #8
0 / 79.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 3 ms 512 KB Output is correct
4 Correct 4 ms 512 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 4 ms 512 KB Output is correct
8 Correct 3 ms 512 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 4 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 4 ms 512 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Incorrect 18 ms 16216 KB Output isn't correct
15 Halted 0 ms 0 KB -