Submission #1190444

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190444		anmattroi	Event Hopping (BOI22_events)	C++17	30 / 100	374 ms	76740 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 it[48*maxn], L[48*maxn], R[48*maxn], nt = 0;

int root[2*maxn];
vector<ii> adj[2*maxn];

int build(int lo = 1, int hi = n1) {
    if (lo == hi) return ++nt;
    int cur = ++nt, mid = (lo + hi) >> 1;
    L[cur] = build(lo, mid);
    R[cur] = build(mid+1, hi);
    return cur;
}

int updPst(int u, int d, int oldver, int lo = 1, int hi = n1) {
    if (lo == hi) {
        it[++nt] = it[oldver] + d;
        return nt;
    }
    int cur = ++nt, mid = (lo + hi) >> 1;
    if (u <= mid) {
        L[cur] = updPst(u, d, L[oldver], lo, mid);
        R[cur] = R[oldver];
    } else {
        L[cur] = L[oldver];
        R[cur] = updPst(u, d, R[oldver], mid+1, hi);
    }
    it[cur] = it[L[cur]] + it[R[cur]];
    return cur;
}

int getPst(int u, int v, int r, int lo = 1, int hi = n1) {
    if (u <= lo && hi <= v) return it[r];
    int mid = (lo + hi) >> 1;
    return (u <= mid ? getPst(u, v, L[r], lo, mid) : 0) +
           (v > mid ? getPst(u, v, R[r], mid+1, hi) : 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;

    root[0] = build();

    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;
        adj[p].emplace_back(q, 1);
        adj[q+1].emplace_back(q, -1);
        update(p, q, ii{a[i].se, i});
    }
    for (int i = 1; i <= n1; i++) {
        root[i] = root[i-1];
        for (auto [v, p] : adj[i]) root[i] = updPst(v, p, root[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;
        }
        if (a[s].se > a[e].se) {
            cout << "impossible\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];
        }
        if (u <= a[s].se && a[s].se <= v) {
            cout << ++ans << "\n";
            continue;
        }
        int p = lower_bound(c + 1, c + n1 + 1, a[s].se) - c;
        int A = lower_bound(c + 1, c + n1 + 1, u) - c,
            B = lower_bound(c + 1, c + n1 + 1, v) - c;

        if (getPst(A, B, root[p])) cout << (ans += 2) << "\n";
        else cout << "impossible\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