oj.uz

Submission #223846

# Submission time Handle Problem Language Result Execution time Memory
223846 2020-04-16T14:39:01 Z Minnakhmetov Hamburg Steak (JOI20_hamburg) C++14
15 / 100
 3000 ms 25648 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({0, 0});

    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 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 452 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 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 4 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 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 4 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 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Execution timed out 3042 ms 16216 KB Time limit exceeded
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 367 ms 10124 KB Output is correct
6 Correct 378 ms 10052 KB Output is correct
7 Correct 342 ms 10052 KB Output is correct
8 Correct 354 ms 10096 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 366 ms 16240 KB Output is correct
6 Correct 340 ms 16016 KB Output is correct
7 Correct 353 ms 16064 KB Output is correct
8 Correct 400 ms 19108 KB Output is correct

Subtask #7
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 452 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 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 4 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 366 ms 13376 KB Output is correct
14 Correct 358 ms 13412 KB Output is correct
15 Correct 373 ms 13460 KB Output is correct
16 Correct 394 ms 13352 KB Output is correct
17 Correct 359 ms 13324 KB Output is correct
18 Correct 377 ms 13348 KB Output is correct
19 Correct 374 ms 18248 KB Output is correct
20 Correct 420 ms 19656 KB Output is correct
21 Correct 511 ms 25648 KB Output is correct
22 Correct 345 ms 19960 KB Output is correct
23 Correct 353 ms 23572 KB Output is correct
24 Correct 365 ms 24904 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 4 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 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 3 ms 512 KB Output is correct
13 Correct 4 ms 640 KB Output is correct
14 Execution timed out 3042 ms 16216 KB Time limit exceeded
15 Halted 0 ms 0 KB -