Submission #696600

#	Time	Username	Problem	Language	Result	Execution time	Memory
696600		jhwest2	Event Hopping (BOI22_events)	C++17	100 / 100	137 ms	17972 KiB

events

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

const int N = 101010;

int n, q, l[N], r[N], w[N], go[20][N], ans[N];
vector<array<int, 2>> query[N];

int main() {
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) 
        cin >> l[i] >> r[i];
    
    iota(w + 1, w + 1 + n, 1);
    sort(w + 1, w + 1 + n, [&](auto i, auto j) {
        if (r[i] == r[j])
            return l[i] < l[j];
        return r[i] < r[j];
    });

    for (int i = 0; i < q; i++) {
        int s, e; cin >> s >> e;
        if (s != e) {
            if (r[s] <= r[e])
                query[e].push_back({s, i});
            else
                ans[i] = 1e9;
        }
    }
    vector<int> v;
    for (int i = 1; i <= n; i++) {
        while (!v.empty() && l[v.back()] >= l[w[i]])
            v.pop_back();
        v.push_back(w[i]);

        int L = 0, R = (int)v.size() - 1;
        while (L < R) {
            int M = (L + R) / 2;
            if (r[v[M]] < l[w[i]])
                L = M + 1;
            else
                R = M;
        }
        go[0][w[i]] = v[L];
        for (int j = 1; j < 20; j++)
            go[j][w[i]] = go[j - 1][go[j - 1][w[i]]];

        for (auto [s, t] : query[w[i]]) {
            int x = w[i];
            for (int j = 19; j >= 0; j--) {
                if (r[s] < l[go[j][x]]) {
                    x = go[j][x];
                    ans[t] += (1 << j);
                }
            }
            ans[t] += (r[s] < l[x]) ? 2 : 1;
        }
    }
    for (int i = 0; i < q; i++) {
        if (ans[i] > n)
            cout << "impossible\n";
        else
            cout << ans[i] << '\n';
    }
}

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