Submission #1161426

#	Time	Username	Problem	Language	Result	Execution time	Memory
1161426		not_amir	New Home (APIO18_new_home)	C++20	80 / 100	5047 ms	946276 KiB

new_home

#include <bits/stdc++.h>
using namespace std;

constexpr int MIN = -1e8, MAX = 2e8;

struct leaf {
    multiset<int> leaf_min = {}, leaf_max = {};
};

struct vertex {
    vertex *l = nullptr, *r = nullptr;
    int minv = MAX, maxv = MIN;

    leaf *lf = nullptr;

    void extend() {
        if (l == nullptr) {
            l = new vertex;
            r = new vertex;
        }
    }

    int query_min(int tl, int tr, int lv, int rv) {
        if (lv >= rv)
            return MAX;
        if (lv == tl && rv == tr)
            return minv;
        int tm = (tl + tr) / 2;
        extend();
        return min(
            l->query_min(tl, tm, lv, min(tm, rv)),
            r->query_min(tm, tr, max(lv, tm), rv)
        );
    }

    int query_max(int tl, int tr, int lv, int rv) {
        if (lv >= rv)
            return MIN;
        if (lv == tl && rv == tr)
            return maxv;
        int tm = (tl + tr) / 2;
        extend();
        return max(
            l->query_max(tl, tm, lv, min(tm, rv)),
            r->query_max(tm, tr, max(lv, tm), rv)
        );
    }

    void update(int tl, int tr, int lv, int rv, bool add) {
        if (tl + 1 == tr) {
            if (!lf)
                lf = new leaf;
            if (add)
                lf->leaf_min.insert(lv), lf->leaf_max.insert(rv);
            else
                lf->leaf_min.erase(lf->leaf_min.find(lv)), lf->leaf_max.erase(lf->leaf_max.find(rv));
            minv = lf->leaf_min.empty() ? MAX : *lf->leaf_min.begin();
            maxv = lf->leaf_max.empty() ? MIN : *lf->leaf_max.rbegin();
        }
        else {
            int tm = (tl + tr) / 2;
            extend();
            if ((lv + rv) / 2 < tm)
                l->update(tl, tm, lv, rv, add);
            else
                r->update(tm, tr, lv, rv, add);
            minv = min(l->minv, r->minv);
            maxv = max(l->maxv, r->maxv);
        }
    }
};

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n, k, q;
    cin >> n >> k >> q;
    vector<array<int, 4>> sl;
    for (int i = 0; i < n; i++) {
        int x, t, a, b;
        cin >> x >> t >> a >> b;
        sl.push_back({a, 0, x, t - 1});
        sl.push_back({b + 1, 1, x, t - 1});
    }
    for (int i = 0; i < q; i++) {
        int l, y;
        cin >> l >> y;
        sl.push_back({y, 2, l, i});
    }
    sort(sl.begin(), sl.end());
    vector<multiset<int>> s(k);
    vertex *st = new vertex;
    int cnt = 0;
    for (int i = 0; i < k; i++) {
        s[i].insert(MIN), s[i].insert(MAX);
        st->update(MIN, MAX, MIN, MAX, true);
    }
    vector<int> ans(q);
    for (int i = 0; i < sl.size(); i++) {
        if (sl[i][1] == 0) {
            auto [x, t] = pair(sl[i][2], sl[i][3]);
            auto it = s[t].upper_bound(x);
            int nxt = *it, prv = *--it;
            st->update(MIN, MAX, prv, nxt, false);
            st->update(MIN, MAX, prv, x, true);
            st->update(MIN, MAX, x, nxt, true);
            if (s[t].size() == 2)
                cnt++;
            s[t].insert(x);
        }
        if (sl[i][1] == 1) {
            auto [x, t] = pair(sl[i][2], sl[i][3]);
            auto it = s[t].find(x);
            int nxt = *next(it, 1), prv = *prev(it, 1);
            st->update(MIN, MAX, prv, nxt, true);
            st->update(MIN, MAX, prv, x, false);
            st->update(MIN, MAX, x, nxt, false);
            s[t].erase(it);
            if (s[t].size() == 2)
                cnt--;
        }

        if (sl[i][1] == 2) {
            auto [l, j] = pair(sl[i][2], sl[i][3]);
            if (cnt < k)
                ans[j] = -1;
            else
                ans[j] = max(l - st->query_min(MIN, MAX, l, MAX),
                    st->query_max(MIN, MAX, MIN, l) - l);
        }
    }
    for (int x : ans)
        cout << x << '\n';
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
*/

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