Submission #1176948

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176948		trinm01	Event Hopping (BOI22_events)	C++20	0 / 100	123 ms	52360 KiB

events

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

#define int long long
#define FOR(i, l, r) for (int i = (l); i <= (r); i++)

const int MAXN = 5 * 1e5 + 5;
const int INF = 1e18;

struct pii
{
    int fi, se, idx;
    
    bool operator<(const pii &other) const
    {
        return fi < other.fi; // Sắp xếp theo first, nếu cần thêm điều kiện khác thì bổ sung
    }
};

int n, q, m;
int par[MAXN], up[MAXN][25], cost[MAXN][25];
pii a[MAXN], b[MAXN];
pii st[4 * MAXN];

void compress() {
    vector<int> vals;
    FOR(i, 1, n) {
        vals.push_back(a[i].fi);
        vals.push_back(a[i].se);
    }
    sort(vals.begin(), vals.end());
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    m = vals.size();
    FOR(i, 1, n) {
        a[i].fi = lower_bound(vals.begin(), vals.end(), a[i].fi) - vals.begin() + 1;
        a[i].se = lower_bound(vals.begin(), vals.end(), a[i].se) - vals.begin() + 1;
    }
}

void seg_init(int id, int l, int r) {
    if (l == r) {
        st[id] = {INF, INF, -1};
        return;
    }
    int mid = (l + r) / 2;
    seg_init(id * 2, l, mid);
    seg_init(id * 2 + 1, mid + 1, r);
    st[id] = min(st[id * 2], st[id * 2 + 1]);
}

void update(int id, int l, int r, int pos, int val, int idx) {
    if (l == r) {
        if (val < st[id].fi) st[id] = {val, val, idx};
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid) update(id * 2, l, mid, pos, val, idx);
    else update(id * 2 + 1, mid + 1, r, pos, val, idx);
    st[id] = min(st[id * 2], st[id * 2 + 1]);
}

pii get(int id, int l, int r, int ql, int qr) {
    if (ql > r || qr < l) return {INF, INF, -1};
    if (ql <= l && r <= qr) return st[id];
    int mid = (l + r) / 2;
    return min(get(id * 2, l, mid, ql, qr), get(id * 2 + 1, mid + 1, r, ql, qr));
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    FOR(i, 1, n) {
        cin >> a[i].fi >> a[i].se;
        a[i].idx = i;
        b[i] = a[i];
    }

    compress();
    seg_init(1, 1, m);
    sort(a + 1, a + n + 1, [](pii x, pii y) { return x.fi < y.fi; });

    FOR(i, 1, n) {
        int u = a[i].idx;
        pii t = get(1, 1, m, a[i].fi, a[i].se);
        if (t.idx == -1) par[u] = u;
        else par[u] = t.idx;
        update(1, 1, m, a[i].se, a[i].fi, u);
    }

    FOR(i, 1, n) {
        up[i][0] = par[i];
        cost[i][0] = (par[i] != i ? 1 : 0);
        for (int k = 1; k < 21; k++) {
            up[i][k] = up[up[i][k - 1]][k - 1];
            cost[i][k] = cost[i][k - 1] + cost[up[i][k - 1]][k - 1];
        }
    }

    while (q--) {
        int u, v;
        cin >> u >> v;
        if (u == v) {
            cout << 0 << "\n";
            continue;
        }
        if (b[u].se > b[v].se) {
            cout << "impossible" << "\n";
            continue;
        }

        int sum = 0, cur = v;
        for (int k = 19; k >= 0; k--) {
            if (b[up[cur][k]].fi > b[u].se) {
                if (cur == up[cur][k]) {
                    sum = -1;
                    break;
                }
                sum += cost[cur][k];
                cur = up[cur][k];
            }
        }

        if (sum == -1) {
            cout << "impossible" << "\n";
            continue;
        }
        sum++;

        if (b[u].se >= b[cur].fi && b[u].se <= b[cur].se) {
            cout << sum << "\n";
            continue;
        }
        cur = up[cur][0];
        if (b[u].se >= b[cur].fi && b[u].se <= b[cur].se) {
            cout << sum + 1 << "\n";
            continue;
        }
        cur = up[cur][0];
        if (b[u].se >= b[cur].fi && b[u].se <= b[cur].se) {
            cout << sum + 2 << "\n";
            continue;
        }
        cout << "impossible" << "\n";
    }

    return 0;
}

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