Submission #1137731

#	Time	Username	Problem	Language	Result	Execution time	Memory
1137731		RaresFelix	Hamburg Steak (JOI20_hamburg)	C++20	100 / 100	1602 ms	153620 KiB

hamburg

#include <bits/stdc++.h>
//#pragma GCC optimize("O3")
//#pragma GCC target("avx,avx2,fma")

using namespace std;

#define int ll

using ll = long long;
using vi = vector<int>;
using ii = pair<int, int>;
using vll = vector<ll>;

const int INF = 1e9;

struct steak {
    ii h, v;
    bool inside(ii pct) {
        return h.first <= pct.first && pct.first <= h.second
            && v.first <= pct.second && pct.second <= v.second;
    }
};

tuple<int, int, int, int> get_steak_extremums(vector<steak> S) {
    auto seg_extremums = [&](vector<ii> V) {
        int l = -INF, r = INF;
        for(auto [s, d] : V) {
            l = max(l, s);
            r = min(r, d);
        }
        return ii{l, r};
    };
    vector<ii> H, V;
    for(auto [h, v] : S) {
        H.push_back(h); V.push_back(v);
    }
    auto [lh, rh] = seg_extremums(H);
    auto [lv, rv] = seg_extremums(V);
    return {lh, rh, lv, rv};
}

vector<ii> sol_k1(vector<steak> S) {
    auto [lh, rh, lv, rv] = get_steak_extremums(S);
    if(lh <= rh && lv <= rv) return vector<ii>{ii{lh, lv}};
    return vector<ii>();
}

vector<ii> sol_k2(vector<steak> S) {
    ///will return the solution if it satisfies everyone
    auto [lh, rh, lv, rv] = get_steak_extremums(S);

    vector<ii> re;
    auto check_sol = [&](ii p1, ii p2) -> bool{
        bool ok = true;
        for(auto it : S) {
            ok &= it.inside(p1) || it.inside(p2);
            if(!ok) break;
        }
        if(ok) {
            re = vector<ii>{p1, p2};
        }
        return ok;
    };
    check_sol(ii{lh, lv}, ii{rh, rv});
    check_sol(ii{lh, rv}, ii{rh, lv});
    return re;
}

vector<ii> sol_k3(vector<steak> S) {
    ///will return the solution if it satisfies everyone
    auto [lh, rh, lv, rv] = get_steak_extremums(S);

    vector<ii> Re;
    auto check_rest = [&](ii p) {
        vector<steak> LeftOver;
        for(auto it : S)
            if(!it.inside(p)) LeftOver.push_back(it);
        auto Cur = sol_k2(LeftOver);
        if(!Cur.empty()) {
            Cur.push_back(p);
            Re = Cur;
        }
    };
    vector<ii> Corners = { {lh, lv}, {lh, rv}, {rh, lv}, {rh, rv}, };
    for(auto it : Corners) check_rest(it);
    return Re;
}

vector<pair<int, ii> > get_intersect(steak x, vector<ii> &Corners) {
    ///returns a vector of (edge id, (min max allowed))
    auto get_overlap0 = [&](ii seg, int l, int r) {
        if(l > r) swap(l, r);
        return ii{max(l, seg.first), min(r, seg.second)};
    };
    auto inside_seg = [&](int p, ii seg) { return seg.first <= p && p <= seg.second; };
    auto get_overlap = [&](ii p1, ii p2) {
        if(p1.first == p2.first) {
            if(inside_seg(p1.first, x.h))
                return get_overlap0(x.v, p1.second, p2.second);
            else return ii{1, 0};
        } else {
            if(inside_seg(p1.second, x.v))
                return get_overlap0(x.h, p1.first, p2.first);
            else
                return ii{1, 0};
        }
    };
    vector<pair<int, ii> > Re;
    for(int i = 0; i < 4; ++i) {
        auto re = get_overlap(Corners[i], Corners[(i + 1) % 4]);
        if(re.first <= re.second) Re.push_back({i, re});
    }
    return Re;
}

ii intersect(ii a, ii b) {
    return {max(a.first, b.first), min(a.second, b.second)};
}

struct RestrictionDS {
    int n;
    ii re;
    vector<ii> Re;
    vector<pair<ii, ii> > V;

    void add(ii x1, ii x2) {
        ///if a in x1 -> b in x2
        V.push_back({x1, x2});
    }

    void init(int N) {
        n = N;
        Re.resize(n, {-INF, INF});

        vector<vector<ii> > Add(n), Rem(n);
        for(auto [x1, x2] : V) {
            auto [s, d] = x1;
            Add[s].push_back(x2);
            Rem[d].push_back(x2);
        }
        multiset<int> Low, High;
        for(int i = 0; i < n; ++i) {
            for(auto [l, r] : Add[i]) {
                Low.insert(l);
                High.insert(r);
            }
            int st = -INF, dr = INF;
            if(!Low.empty()) st = *Low.rbegin();
            if(!High.empty()) dr = *High.begin();
            Re[i] = {st, dr};
            for(auto [l, r] : Rem[i]) {
                Low.erase(Low.find(l));
                High.erase(High.find(r));
            }
        }
    }

    ii eval(int p) {
        return Re[p];
    }
};

vector<ii> sol_k4_special(vector<steak> S) {
    vi X_posib, Y_posib;
    for(auto [h, v] : S) {
        X_posib.push_back(h.first); X_posib.push_back(h.second);
        Y_posib.push_back(v.first); Y_posib.push_back(v.second);
    }

    auto norm_vec = [&](vi &V) -> pair<int, map<int, int> > {
        sort(V.begin(), V.end());
        V.resize(unique(V.begin(), V.end()) - V.begin());
        int len = (int)V.size();
        map<int, int> vti;
        for(int i = 0; i < len; ++i) {
            vti[V[i]] = i;
        }
        return {len, vti};
    };

    auto [len_x, vti_x] = norm_vec(X_posib);
    auto [len_y, vti_y] = norm_vec(Y_posib);

    for(auto &[h, v] : S) {
        h.first = vti_x[h.first]; h.second = vti_x[h.second];
        v.first = vti_y[v.first]; v.second = vti_y[v.second];
    }

    auto [lh, rh, lv, rv] = get_steak_extremums(S);

    vector<ii> Corners = { {rh, rv}, {rh, lv}, {lh, lv}, {lh, rv}, };
    vector<ii> FullSeg = { {rv, lv}, {rh, lh}, {rv, lv}, {rh, lh}, }; /// for negations

    auto negate = [&](ii seg, ii full) {
        assert(seg.first <= seg.second);
        vector<ii> Rez;
        if(seg.second < full.second) Rez.push_back({seg.second + 1, full.second});
        if(full.first < seg.first) Rez.push_back({full.first,  seg.first - 1});
        return Rez;
    };

    vector<ii> RestrictiiInit;
    for(int i = 0; i < 4; ++i) {
        RestrictiiInit.push_back(FullSeg[i]);
    }

    array<array<RestrictionDS, 4>, 4> Forbid;
    vi Order = {0, 3, 1, 2}, RankOrd = {0, 2, 3, 1};

    for(auto x : S) {
        int nrc = 0;
        for(auto p : Corners) nrc += x.inside(p);
        if(nrc > 1) { /// contains one whole edge; is surely covered
            continue;
        }
        auto Inter = get_intersect(x, Corners);
        assert(0 < Inter.size() && Inter.size() <= 2);
        if(Inter.size() == 1) { ///simple restriction
            ///Basic[Inter[0].first].add(ii{0, 0}, Inter[0].second);
            RestrictiiInit[Inter[0].first] = intersect(RestrictiiInit[Inter[0].first], Inter[0].second);
        } else {
            if(RankOrd[Inter[0].first] > RankOrd[Inter[1].first]) swap(Inter[0], Inter[1]);
            auto [id0, seg0] = Inter[0]; auto [id1, seg1] = Inter[1];
            for(auto it : negate(seg0, FullSeg[id0]))
                Forbid[id0][id1].add(it, seg1);
            if(id0 % 2 == id1 % 2 && id0 == 3) { /// grava
                RestrictiiInit[id0] = intersect(RestrictiiInit[id0], {rh, seg1.second});
                RestrictiiInit[id1] = intersect(RestrictiiInit[id1], {seg1.first, lh});
//                Basic[id0].add({0, 0}, {rh, seg1.second}); 
 //               Basic[id1].add({0, 0}, {seg1.first, lh});
            }
        }
    }

    


    for(int i = 0; i < 4; ++i) {
        for(int j = i + 1; j < 4; ++j) {
            ///Forbid[Ord[i]][Ord[j]]
            if(Order[i] % 2 == 1) {
                Forbid[Order[i]][Order[j]].init(len_x);
            } else {
                Forbid[Order[i]][Order[j]].init(len_y);
            }
        }
    }

    for(int x0 = 0; x0 < len_y; ++x0) {
        ///now choose the others greedly
        vector<ii> Rest = RestrictiiInit;
        vi X(4, 0);
        X[0] = x0;

        bool ok = true;
        for(int i = 1; i < 4; ++i) {
            for(int j = i; j < 4; ++j) { /// process what Order[i - 1] did for everyone
                ii new_rest = Forbid[Order[i - 1]][Order[j]].eval(X[Order[i - 1]]);
                Rest[Order[j]] = intersect(Rest[Order[j]], new_rest); 
            }
            if(Rest[Order[i]].first > Rest[Order[i]].second) {
                ok = false;
                break;
            }
            X[Order[i]] = Rest[Order[i]].second;
        }
        if(!ok) continue;
        for(int i = 0; i < 4; ++i)
            ok &= Rest[i].first <= X[i] && X[i] <= Rest[i].second;
        if(ok) {
            ///avem o solutie
            vector<ii> Re = {{rh, X[0]}, {X[1], lv}, {lh, X[2]}, {X[3], rv}};
            for(auto &[x, y] : Re) {
                x = X_posib[x]; y = Y_posib[y];
            }
            return Re;
        }
    }
    return vector<ii>();
}

vector<ii> sol_k4(vector<steak> S) {
    ///will return the solution if it satisfies everyone
    auto [lh, rh, lv, rv] = get_steak_extremums(S);

    vector<ii> Re;
    auto check_rest = [&](ii p) {
        vector<steak> LeftOver;
        for(auto it : S)
            if(!it.inside(p)) LeftOver.push_back(it);
        auto Cur = sol_k3(LeftOver);
        if(!Cur.empty()) {
            Cur.push_back(p);
            Re = Cur;
        }
    };
    vector<ii> Corners = { {lh, lv}, {lh, rv}, {rh, lv}, {rh, rv}, };
    for(auto p : Corners) check_rest(p);
    if(!Re.empty())
        return Re;
    /// now we're sure no corners are used
    Re = sol_k4_special(S);
    if(!Re.empty()) return Re;
    for(auto &it : S) {
        it.v.first *= -1; it.v.second *= -1;
        swap(it.v.first, it.v.second);
    }
    Re = sol_k4_special(S);
    assert(!Re.empty());
    for(auto &[x, y] : Re) y *= -1;

    for(auto &it : S) {
        it.v.first *= -1; it.v.second *= -1;
        swap(it.v.first, it.v.second);
    }

    for(auto x : S) {
        bool ok = false;
        for(auto it : Re) {
            ok |= x.inside(it);
        }
        assert(ok);
    }

    return Re;
}

signed main() {
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    int n, k;
    cin >> n >> k;
    vector<steak> S(n);
    for(int i = 0; i < n; ++i) {
        cin >> S[i].h.first >> S[i].v.first >> S[i].h.second >> S[i].v.second;
    }

    vector<ii> Re;
    if(k == 1) Re = sol_k1(S);
    if(k == 2) Re = sol_k2(S);
    if(k == 3) Re = sol_k3(S);
    if(k == 4) Re = sol_k4(S);

    for(auto it : Re) cout << it.first << " " << it.second << "\n";

    return 0;
}

• 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