제출 #1190440

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1190440		anmattroi	Event Hopping (BOI22_events)	C++17	30 / 100	226 ms	19056 KiB

events

#include <bits/stdc++.h>
#define maxn 100005
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

int n, q;

int f[20][maxn];

ii a[maxn];
int c[2*maxn], n1 = 0;

ii lz[8*maxn], st[8*maxn];

void apply(int r, ii d) {
    lz[r] = max(lz[r], d);
    st[r] = max(st[r], d);
}

void down(int r) {
    apply(r<<1, lz[r]);
    apply(r<<1|1, lz[r]);
}

void up(int r) {
    st[r] = max(st[r<<1], st[r<<1|1]);
}

void update(int u, int v, ii d, int r = 1, int lo = 1, int hi = n1) {
    if (u <= lo && hi <= v) {
        apply(r, d);
        return;
    }
    down(r);
    int mid = (lo + hi) >> 1;
    if (u <= mid) update(u, v, d, r<<1, lo, mid);
    if (v > mid) update(u, v, d, r<<1|1, mid+1, hi);
    up(r);
}

ii get(int u, int v, int r = 1, int lo = 1, int hi = n1) {
    if (u <= lo && hi <= v) return st[r];
    int mid = (lo + hi) >> 1;
    down(r);
    return max(u <= mid ? get(u, v, r<<1, lo, mid) : ii{0, 0}, v > mid ? get(u, v, r<<1|1, mid+1, hi) : ii{0, 0});
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se;
    for (int i = 1; i <= n; i++) {
        c[++n1] = a[i].fi;
        c[++n1] = a[i].se;
    }
    sort(c + 1, c + n1 + 1);
    n1 = unique(c + 1, c + n1 + 1) - c - 1;

    for (int i = 1; i <= n; i++) {
        int p = lower_bound(c + 1, c + n1 + 1, a[i].fi) - c,
            q = lower_bound(c + 1, c + n1 + 1, a[i].se) - c;
        update(p, q, ii{a[i].se, i});
    }
    for (int i = 1; i <= n; i++) {
        int p = lower_bound(c + 1, c + n1 + 1, a[i].fi) - c,
            q = lower_bound(c + 1, c + n1 + 1, a[i].se) - c;
        ii o = get(p, q);
        if (o.fi == a[i].se) f[0][i] = i;
        else f[0][i] = o.se;
    }

    for (int i = 1; i < 20; i++) for (int j = 1; j <= n; j++) f[i][j] = f[i-1][f[i-1][j]];
    while (q--) {
        int s, e;
        cin >> s >> e;
        if (s == e) {
            cout << "0\n";
            continue;
        }
        auto [u, v] = a[e];
        int ans = 0;
        for (int i = 19; i >= 0; i--)
        if (a[f[i][s]].se < u) {
            ans += (1<<i);
            s = f[i][s];
        }
        for (int o = 0; o < 3; o++) {
            if (u <= a[s].se && a[s].se <= v) {
                s = e;
                ++ans;
                break;
            }
            if (u <= a[f[0][s]].se && a[f[0][s]].se <= v) {
                s = f[0][s];
                ++ans;
            }
        }
        if (s != e) cout << "impossible\n";
        else cout << ans << "\n";
    }
}

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