Submission #1176004

#	Time	Username	Problem	Language	Result	Execution time	Memory
1176004		minhpk	Event Hopping (BOI22_events)	C++20	0 / 100	162 ms	52172 KiB

events

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

int a, q;
pair<int,int> z[1000005];
vector<int> v;

struct node {
    int l, id;
};

const int INF = 1e16;
node f[4000005];

// Hàm combine: chọn nút có giá trị l nhỏ hơn; nếu bằng nhau thì chọn nút có id lớn hơn.
node combine(const node &left, const node &right) {
    if (left.l < right.l) return left;
    if (left.l == right.l && left.id > right.id) return left;
    return right;
}

void build(int id, int l, int r) {
    if (l == r) {
        f[id] = {INF, INF};
        return;
    }
    int mid = (l + r) / 2;
    build(id * 2, l, mid);
    build(id * 2 + 1, mid + 1, r);
    f[id] = combine(f[id * 2], f[id * 2 + 1]);
}

void update(int id, int l, int r, int pos, int L, int idx) {
    if (l == r) {
        // Cập nhật nút tại vị trí pos với thông tin {L, idx}
        f[id] = combine(f[id], {L, idx});
        return;
    }
    int mid = (l + r) / 2;
    if (pos <= mid)
        update(id * 2, l, mid, pos, L, idx);
    else
        update(id * 2 + 1, mid + 1, r, pos, L, idx);
    f[id] = combine(f[id * 2], f[id * 2 + 1]);
}

node query(int id, int l, int r, int ql, int qr) {
    if (qr < l || ql > r)
        return {INF, INF};
    if (ql <= l && r <= qr)
        return f[id];
    int mid = (l + r) / 2;
    node leftNode = query(id * 2, l, mid, ql, qr);
    node rightNode = query(id * 2 + 1, mid + 1, r, ql, qr);
    return combine(leftNode, rightNode);
}

int up[100005][25];
int cost[100005][25];

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

    cin >> a >> q;
    for (int i = 1; i <= a; i++) {
        cin >> z[i].first >> z[i].second;
        v.push_back(z[i].first);
        v.push_back(z[i].second);
    }
    // Tiến hành coordinate compression
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int n = v.size();
    for (int i = 1; i <= a; i++) {
        z[i].first = lower_bound(v.begin(), v.end(), z[i].first) - v.begin() + 1;
        z[i].second = lower_bound(v.begin(), v.end(), z[i].second) - v.begin() + 1;
    }

    // Xây dựng cây phân đoạn trên khoảng [1, n]
    build(1, 1, n);
    // Với mỗi khoảng, cập nhật tại vị trí = z[i].second giá trị là {z[i].first, i}
    for (int i = 1; i <= a; i++) {
        update(1, 1, n, z[i].second, z[i].first, i);
    }

    // Xây dựng bảng nhảy một bước (up[i][0]) và chi phí tương ứng.
    // Với mỗi khoảng i, truy vấn trên [z[i].first, z[i].second] để tìm khoảng "tối ưu" nối được với i.
    for (int i = 1; i <= a; i++) {
        node res = query(1, 1, n, z[i].first, z[i].second);
        // Nếu không tìm được khoảng nào khác (res.id == i) thì không có bước nhảy
        if (res.id == i) {
            up[i][0] = i;
            cost[i][0] = 0;
        } else {
            up[i][0] = res.id;
            cost[i][0] = 1;
        }
    }

    // Xây dựng bảng nhảy đôi (binary lifting)
    for (int j = 1; j <= 20; j++) {
        for (int i = 1; i <= a; i++) {
            up[i][j] = up[up[i][j - 1]][j - 1];
            cost[i][j] = cost[i][j - 1] + cost[up[i][j - 1]][j - 1];
        }
    }

    // Xử lý truy vấn:
    // Mục tiêu: từ khoảng x có thể nối chuỗi tới khoảng y với số bước tối thiểu
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (x == y) {
            cout << 0 << "\n";
            continue;
        }
        // Nếu khoảng bắt đầu của x không nhỏ hơn kết thúc của y, không nối được
        if (z[x].first >= z[y].second) {
            cout << "impossible" << "\n";
            continue;
        }
        int p = y;
        int ans = 0;
        // Sử dụng nhảy nhị phân từ y về x (tìm khoảng mà z[x].second có thể nối được)
        for (int i = 20; i >= 0; i--) {
            int candidate = up[p][i];
            // Nếu khoảng candidate vẫn có đầu trái lớn hơn z[x].second, ta có thể nhảy ngược tiếp
            if (z[candidate].first > z[x].second) {
                ans += cost[p][i];
                p = candidate;
            }
        }
        // Kiểm tra sau nhảy nhị phân, nếu z[x].second nối được với khoảng p thì cộng thêm 1 bước
        if (z[x].second >= z[p].first) {
            cout << ans + 1 << "\n";
        } else {
            // Thử nhảy thêm một bước nữa
            p = up[p][0];
            if (z[x].second >= z[p].first) {
                cout << ans + 2 << "\n";
            } else {
                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