Submission #925044

#	Time	Username	Problem	Language	Result	Execution time	Memory
925044		Camillus	New Home (APIO18_new_home)	C++17	80 / 100	5067 ms	807520 KiB

new_home

#include "bits/stdc++.h"
#pragma GCC optimize("O3")
using namespace std;

constexpr int INF = 1e9;

struct Event {
    static constexpr int OPEN = 0;
    static constexpr int CLOSE = 1;
    static constexpr int QUERY = 2;

    int type = OPEN;
    int ind = 0;

    Event() = default;

    Event(int type, int ind) : type(type), ind(ind) {
    }

    bool operator<(const Event&other) const {
        return type < other.type;
    }
};

namespace st {
    static constexpr int size = 1 << 21;

    multiset<int> tree[size * 2 - 1];

    void add(int i, int v) {
        int x = size + i - 1;
        tree[x].insert(v);

        while (x) {
            x = (x - 1) / 2;
            tree[x].insert(v);
        }
    }

    void del(int i, int v) {
        int x = size + i - 1;
        tree[x].erase(tree[x].find(v));

        while (x) {
            x = (x - 1) / 2;
            tree[x].erase(tree[x].find(v));
        }
    }

    int get(int l, int r, int x = 0, int lx = 0, int rx = size) {
        if (tree[x].empty() || l >= rx || lx >= r) {
            return 0;
        }

        if (l <= lx && rx <= r) {
            return *prev(tree[x].end());
        }

        return max(
            get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
            get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
        );
    }
}

namespace st2 {
    static constexpr int size = 1 << 21;

    int tree[size * 2 - 1];

    void set(int i, int v) {
        int x = size + i - 1;
        tree[x] = max(tree[x], v);
        while (x) {
            x = (x - 1) / 2;
            tree[x] = max(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    int get(int l, int r, int x = 0, int lx = 0, int rx = size) {
        if (l <= lx && rx <= r) {
            return tree[x];
        }

        if (l >= rx || lx >= r) {
            return 0;
        }

        return max(
            get(l, r, x * 2 + 1, lx, (lx + rx) / 2),
            get(l, r, x * 2 + 2, (lx + rx) / 2, rx)
        );
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k, q;
    cin >> n >> k >> q;

    map<int, vector<Event>> events;

    vector<int> P = {-INF + 1, INF - 1};

    bool ok = true;

    vector<int> x(n), t(n), a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> x[i] >> t[i] >> a[i] >> b[i];
        t[i]--;

        if (a[i] != 1) {
            ok = false;
        }

        P.push_back(x[i] + 1);
        P.push_back(x[i] - 1);

        events[a[i]].emplace_back(Event::OPEN, i);
        events[b[i] + 1].emplace_back(Event::CLOSE, i);
    }

    vector<int> l(q), y(q);
    vector<int> ans(q);

    for (int i = 0; i < q; i++) {
        cin >> l[i] >> y[i];

        P.push_back(l[i] + 1);
        P.push_back(l[i] - 1);

        events[y[i]].emplace_back(Event::QUERY, i);
    }

    sort(P.begin(), P.end());
    P.erase(unique(P.begin(), P.end()), P.end());

    vector<multiset<int>> pos(k);

    if (!ok) {
        for (int i = 0; i < k; i++) {
            pos[i] = {-INF, INF};
            st::add(0, INF - 1);
        }

        for (auto [cur_pos, cur_events]: events) {
            for (const auto&event: cur_events) {
                if (event.type == Event::OPEN) {
                    auto it = pos[t[event.ind]].insert(x[event.ind]);

                    int R = *next(it);
                    int L = *prev(it);
                    int M = *it;

                    if (L + 1 <= R - 1) {
                        int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                        st::del(j, R - 1);
                    }

                    if (L + 1 <= M - 1) {
                        int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                        st::add(j, M - 1);
                    }

                    if (M + 1 <= R - 1) {
                        int j = lower_bound(P.begin(), P.end(), M + 1) - P.begin();
                        st::add(j, R - 1);
                    }
                } else if (event.type == Event::CLOSE) {
                    auto it = pos[t[event.ind]].find(x[event.ind]);

                    int R = *next(it);
                    int L = *prev(it);
                    int M = *it;

                    if (L + 1 <= R - 1) {
                        int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                        st::add(j, R - 1);
                    }

                    if (L + 1 <= M - 1) {
                        int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                        st::del(j, M - 1);
                    }

                    if (M + 1 <= R - 1) {
                        int j = lower_bound(P.begin(), P.end(), M + 1) - P.begin();
                        st::del(j, R - 1);
                    }

                    pos[t[event.ind]].erase(it);
                } else {
                    int loc = l[event.ind];

                    int L = -1, R = 1e8 + 5;

                    while (R - L > 1) {
                        int M = (L + R) / 2;

                        int left = loc - M;
                        int right = loc + M;

                        int j = upper_bound(P.begin(), P.end(), left) - P.begin();
                        if (st::get(0, j) < right) {
                            R = M;
                        }
                        else {
                            L = M;
                        }
                    }

                    if (R == 1e8 + 5) {
                        ans[event.ind] = -1;
                    } else {
                        ans[event.ind] = R;
                    }
                }
            }
        }

        for (int i = 0; i < q; i++) {
            cout << ans[i] << '\n';
        }
    } else {
        for (int i = 0; i < k; i++) {
            pos[i] = {-INF, INF};
        }

        for (int i = 0; i < n; i++) {
            pos[t[i]].insert(x[i]);
        }

        for (int i = 0; i < k; i++) {
            for (auto it = pos[i].begin(); it != pos[i].end() && next(it) != pos[i].end(); it = next(it)) {
                int L = *it;
                int R = *next(it);
                int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                st2::set(j, R - 1);
            }
        }

        for (auto [cur_pos, cur_events]: events) {
            for (const auto&event: cur_events) {
                if (event.type == Event::OPEN) {
                } else if (event.type == Event::CLOSE) {
                    auto it = pos[t[event.ind]].find(x[event.ind]);

                    int R = *next(it);
                    int L = *prev(it);
                    int M = *it;

                    if (L + 1 <= R - 1) {
                        int j = lower_bound(P.begin(), P.end(), L + 1) - P.begin();
                        st2::set(j, R - 1);
                    }

                    pos[t[event.ind]].erase(it);
                } else {
                    int loc = l[event.ind];

                    int L = -1, R = 1e8 + 5;

                    while (R - L > 1) {
                        int M = (L + R) / 2;

                        int left = loc - M;
                        int right = loc + M;

                        int j = upper_bound(P.begin(), P.end(), left) - P.begin();
                        if (st2::get(0, j) < right) {
                            R = M;
                        }
                        else {
                            L = M;
                        }
                    }

                    if (R == 1e8 + 5) {
                        ans[event.ind] = -1;
                    } else {
                        ans[event.ind] = R;
                    }
                }
            }
        }

        for (int i = 0; i < q; i++) {
            cout << ans[i] << '\n';
        }
    }
    return 0;
}

Compilation message (stderr)

new_home.cpp: In function 'int main()':
new_home.cpp:251:25: warning: unused variable 'M' [-Wunused-variable]
  251 |                     int M = *it;
      |                         ^

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