Submission #949673

#	Time	Username	Problem	Language	Result	Execution time	Memory
949673		ifateen	Event Hopping (BOI22_events)	C++17	0 / 100	404 ms	36232 KiB

events

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define lc (node + 1)
#define mid ((tl + tr) >> 1)
#define rc (node + 2 * (mid - tl + 1))
const int MAXN = 1e5 + 5, MAX = 2e5 + 5;
pair<int, int> v[MAXN];
vector<int> ind, stop[MAXN];
int prv[22][MAXN]; // mn[i] = j such that l[j] is minimized and l[i]<=r[j]<=r[i]

struct Node {
    int mn = 1e18, mnIndex = -1;
    friend Node operator+(Node a, Node b) {
        if (a.mn < b.mn) return a;
        else return b;
    }
};

struct SegmentTree {
    vector<Node> tree;
    SegmentTree() {
        tree.resize(2 * MAX);
    }
    void update(int tl, int tr, int node, int val, int idx, int IDX) {
        if (tl == tr) tree[node] = tree[node] + Node{val, IDX};
        else {
            if (idx <= mid) update(tl, mid, lc, val, idx, IDX);
            else update(mid + 1, tr, rc, val, idx, IDX);
            tree[node] = tree[lc] + tree[rc];
        }
    }
    Node query(int tl, int tr, int node, int l, int r) {
        if (tl > r || tr < l) return {(int)1e18, -1};
        if (tl >= l && tr <= r) return tree[node];
        return query(tl, mid, lc, l, r) + query(mid + 1, tr, rc, l, r);
    }
};

signed main() {
    int n, q;
    cin >> n >> q;
    for (int i = 1; i <= n; ++i) {
        cin >> v[i].first >> v[i].second;
        ind.push_back(v[i].first), ind.push_back(v[i].second);
    }
    sort(begin(ind), end(ind));
    ind.erase(unique(begin(ind), end(ind)), end(ind));
    for (int i = 1; i <= n; ++i) {
        v[i].first = lower_bound(begin(ind), end(ind), v[i].first) - begin(ind);
        v[i].second = lower_bound(begin(ind), end(ind), v[i].second) - begin(ind);
        stop[v[i].second].push_back(i);
    }
    SegmentTree st;
    for (auto & i : stop) {
        for (auto& idx : i) {
            prv[0][idx] = st.query(0, MAX - 1, 1, v[idx].first, v[idx].second).mnIndex;
            st.update(0, MAX - 1, 1, v[idx].first, v[idx].second, idx);
        }
    }
    for (int LOG = 1; LOG < 22; ++LOG) {
        for (int i = 1; i <= n; ++i) {
            int res = prv[LOG - 1][i];
            prv[LOG][i] = -1;
            if (res == -1) continue;
            prv[LOG][i] = prv[LOG - 1][res];
        }
    }
    while (q--) {
        int s, e;
        cin >> s >> e;
        int ans = 0;
        if (v[s].second > v[e].second) {
            cout << "impossible\n";
            continue;
        }
        if (s == e) {
            cout << "0\n";
            continue;
        }
        for (int i = 21; i >= 0; --i) {
            if (prv[i][e] == -1) continue;
            int S = v[prv[i][e]].first;
            if (S >= v[s].first) e = prv[i][e], ans += 1 << i;
        }
        if (v[e].first == v[s].first) cout << ans << '\n';
        else if (prv[0][e] != -1 && v[prv[0][e]].first <= v[s].first) cout << ans + 1 << '\n';
        else cout << "impossible\n";
    }
}

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