Submission #581141

#	Time	Username	Problem	Language	Result	Execution time	Memory
581141		KoD	Event Hopping (BOI22_events)	C++17	100 / 100	164 ms	11616 KiB

events

#include <bits/stdc++.h>

using ll = long long;
using std::vector;
using std::array;
using std::tuple;
using std::pair;

template <class F> struct fixed : private F {
    explicit fixed(F&& f) : F(std::forward<F>(f)) {}
    template <class... Args> decltype(auto) operator()(Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

template <class T>
constexpr T infty = std::numeric_limits<T>::max() / 2;

constexpr pair<int, int> unit = {infty<int>, infty<int>};

class segtree {
    int size;
    vector<pair<int, int>> data;

  public:
    explicit segtree(const int n) : size(n), data(2 * n, unit) {}
    
    void assign(int i, const pair<int, int>& x) {
        i += size;
        data[i] = x;
        while (i > 1) {
            i >>= 1;
            data[i] = std::min(data[2 * i], data[2 * i + 1]);
        }
    }

    pair<int, int> fold(int l, int r) {
        l += size;
        r += size;
        auto ret = unit;
        while (l < r) {
            if (l & 1) ret = std::min(ret, data[l++]);
            if (r & 1) ret = std::min(ret, data[--r]);
            l >>= 1;
            r >>= 1;
        }
        return ret;
    }
};

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int N, Q;
    std::cin >> N >> Q;
    vector<int> S(N), E(N);
    for (int i = 0; i < N; ++i) {
        std::cin >> S[i] >> E[i];
    }
    vector<pair<int, int>> vec(N);
    for (int i = 0; i < N; ++i) {
        vec[i] = {E[i], i};
    }
    std::sort(vec.begin(), vec.end());
    segtree seg(N);
    for (int i = 0; i < N; ++i) {
        const int k = vec[i].second;
        seg.assign(i, pair(S[k], k));
    }
    constexpr int LOG = 18;
    array<vector<int>, LOG> parent = {};
    parent[0].resize(N);
    for (int i = 0; i < N; ++i) {
        const int l = std::lower_bound(vec.begin(), vec.end(), pair(S[i], 0)) - vec.begin();
        const int r = std::lower_bound(vec.begin(), vec.end(), pair(E[i] + 1, 0)) - vec.begin();
        parent[0][i] = seg.fold(l, r).second;
    }
    for (int i = 0; i < LOG - 1; ++i) {
        parent[i + 1].resize(N);
        for (int j = 0; j < N; ++j) {
            parent[i + 1][j] = parent[i][parent[i][j]];
        }
    }
    while (Q--) {
        int s, e;
        std::cin >> s >> e;
        s -= 1, e -= 1;
        const int root = parent[LOG - 1][e];
        if (s == e) {
            std::cout << 0 << '\n';
            continue;
        }
        if (E[e] < E[s] or E[s] < S[root]) {
            std::cout << "impossible\n";
            continue;
        }
        if (S[e] <= E[s]) {
            std::cout << 1 << '\n';
            continue;
        }
        int ans = 0;
        for (int k = LOG - 1; k >= 0; --k) {
            if (E[s] < S[parent[k][e]]) {
                e = parent[k][e];
                ans |= 1 << k;
            }
        }
        std::cout << ans + 2 << '\n';
    }
    return 0;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 15 / 15
• Subtask 5: 20 / 20
• Subtask 6: 30 / 30