oj.uz

Submission #223861

# Submission time Handle Problem Language Result Execution time Memory
223861 2020-04-16T15:07:13 Z Minnakhmetov Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 386 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);

            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, 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 = 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:183:17: warning: unused variable 'mx_rt' [-Wunused-variable]
  183 |                 mx_rt = suf[i + 1];
      |                 ^~~~~
hamburg.cpp:220:17: warning: unused variable 'mx_lt' [-Wunused-variable]
  220 |             int mx_lt = pref[i - 1],
      |                 ^~~~~
hamburg.cpp: In function 'int main()':
hamburg.cpp:297: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]
  297 |     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 2 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 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 #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 4 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 3 ms 512 KB Output is correct
6 Correct 3 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 3 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 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 4 ms 512 KB Output is correct
6 Correct 3 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 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Incorrect 18 ms 16196 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 2 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 324 ms 10000 KB Output is correct
6 Correct 354 ms 10052 KB Output is correct
7 Correct 322 ms 10060 KB Output is correct
8 Correct 320 ms 10052 KB Output is correct

Subtask #6
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 512 KB Output is correct
5 Correct 342 ms 16156 KB Output is correct
6 Correct 360 ms 15964 KB Output is correct
7 Correct 359 ms 16148 KB Output is correct
8 Correct 345 ms 19092 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 4 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 3 ms 512 KB Output is correct
6 Correct 3 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 3 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 356 ms 13384 KB Output is correct
14 Correct 344 ms 13380 KB Output is correct
15 Correct 343 ms 13340 KB Output is correct
16 Correct 346 ms 13380 KB Output is correct
17 Correct 362 ms 13380 KB Output is correct
18 Correct 367 ms 13332 KB Output is correct
19 Correct 354 ms 18244 KB Output is correct
20 Correct 350 ms 19612 KB Output is correct
21 Correct 386 ms 25632 KB Output is correct
22 Correct 367 ms 19884 KB Output is correct
23 Correct 376 ms 23576 KB Output is correct
24 Correct 373 ms 24876 KB Output is correct

Subtask #8
0 / 79.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 4 ms 512 KB Output is correct
6 Correct 3 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 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 4 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 5 ms 640 KB Output is correct
14 Incorrect 18 ms 16196 KB Output isn't correct
15 Halted 0 ms 0 KB -