Submission #568084

#	Time	Username	Problem	Language	Result	Execution time	Memory
568084		Cyanmond	New Home (APIO18_new_home)	C++17	57 / 100	5060 ms	302536 KiB

new_home

#include <bits/stdc++.h>

using namespace std;
using i64 = int64_t;

constexpr int inf = 1000000100;

#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)

#define ALL(x) (x).begin(), (x).end()

struct PriqueErase {
    priority_queue<int, vector<int>, greater<int>> a, b;

    void push(int x) { a.push(x); }

    void erase(int x) { b.push(x); }

    int top() {
        while (not a.empty()) {
            const int v = a.top();
            if (b.empty()) {
                return v;
            } else if (v == b.top()) {
                a.pop();
                b.pop();
            } else {
                return v;
            }
        }
        return inf;
    }
};

struct RIEPM {
    int n, siz;
    vector<PriqueErase> data;

    RIEPM(int n_) : n(n_) {
        siz = 1;
        while (siz < n) siz <<= 1;
        data.assign(2 * siz, PriqueErase());
    }

    void push(int l, int r, int v) {
        assert(0 <= l and l <= r and r <= n);
        for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) data[l++].push(v);
            if (r & 1) data[--r].push(v);
        }
    }

    void erase(int l, int r, int v) {
        assert(0 <= l and l <= r and r <= n);
        for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) {
            if (l & 1) data[l++].erase(v);
            if (r & 1) data[--r].erase(v);
        }
    }

    int top(int i) {
        assert(0 <= i and i < n);
        i += siz;
        int res = inf;
        while (i != 0) {
            res = min(res, data[i].top());
            i >>= 1;
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K, Q;
    cin >> N >> K >> Q;
    vector<int> X(N), T(N), A(N), B(N);
    REP(i, N) {
        cin >> X[i] >> T[i] >> A[i] >> B[i];
        --T[i];
    }
    vector<int> L(Q), Y(Q);
    REP(i, Q) cin >> L[i] >> Y[i];

    auto reverse_points = [&]() {
        REP(i, N) X[i] = inf - X[i];
        REP(i, Q) L[i] = inf - L[i];
    };

    auto solve = [&]() {
        vector<int> press;
        REP(i, N) press.push_back(X[i]);
        REP(i, Q) press.push_back(L[i]);
        sort(ALL(press));
        press.erase(unique(ALL(press)), press.end());

        auto get_key = [&](int i) { return (int)(lower_bound(ALL(press), i) - press.begin()); };

        const int M = (int)press.size();
        RIEPM hp(M);

        vector<tuple<int, int, int, int>> event;
        REP(i, N) {
            event.push_back({A[i], 0, X[i], T[i]});
            event.push_back({B[i] + 1, 1, X[i], T[i]});
        }
        REP(i, Q) event.push_back({Y[i], 2, L[i], i});
        sort(ALL(event));

        vector<map<int, int>> pd(K);
        vector<int> res(Q, -1);

        int cnt_zero = K;
        for (const auto &[c, qt, p, i] : event) {
            if (qt == 0) {
                if (pd[i].empty()) --cnt_zero;
                auto [itr, vld] = pd[i].insert({p, 1});
                if (not vld) {
                    ++itr->second;
                    continue;
                }
                auto itr_r = itr;
                ++itr_r;
                if (itr_r == pd[i].end()) {
                    hp.push(get_key(p), M, p);
                } else {
                    hp.push(get_key(p), get_key((p + itr_r->first + 2) / 2), p);
                }
                if (itr == pd[i].begin()) continue;
                auto itr_l = itr;
                --itr_l;
                const int l_id = get_key(itr_l->first);
                if (itr_r != pd[i].end()) {
                    hp.erase(l_id, get_key((itr_l->first + itr_r->first + 2) / 2), itr_l->first);
                } else {
                    hp.erase(l_id, M, itr_l->first);
                }
                hp.push(l_id, get_key((itr_l->first + p + 2) / 2), itr_l->first);
            }
            if (qt == 1) {
                auto itr = pd[i].find(p);
                if (--(itr->second) != 0) {
                    continue;
                }
                pd[i].erase(p);
                if (pd[i].empty()) ++cnt_zero;
                auto itr_r = pd[i].upper_bound(p);
                if (itr_r != pd[i].end()) {
                    hp.erase(get_key(p), get_key((p + itr_r->first + 2) / 2), p);
                } else {
                    hp.erase(get_key(p), M, p);
                }
                if (itr_r == pd[i].begin()) continue;
                auto itr_l = itr_r;
                --itr_l;
                const int l_id = get_key(itr_l->first);
                hp.erase(l_id, get_key((itr_l->first + p + 2) / 2), itr_l->first);
                if (itr_r != pd[i].end()) {
                    hp.push(l_id, get_key((itr_l->first + itr_r->first + 2) / 2), itr_l->first);
                } else {
                    hp.push(l_id, M, itr_l->first);
                }
            }
            if (qt == 2) {
                if (cnt_zero != 0) continue;
                const int pi = get_key(p);
                const int vi = hp.top(pi);
                if (vi == inf) continue;
                res[i] = p - vi;
            }
        }

        return res;
    };

    const auto res1 = solve();
    reverse_points();
    const auto res2 = solve();
    REP(i, Q) {
        const int ans = max(res1[i], res2[i]);
        cout << ans << '\n';
    }
}

• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 10 / 10
• Subtask 4: 0 / 23
• Subtask 5: 35 / 35
• Subtask 6: 0 / 20