Submission #1310603

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310603		harryleee	Fire (BOI24_fire)	C++20	0 / 100	1 ms	716 KiB

Main

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

const int INF = 1e9;

struct Interval {
    int id;
    int l, r;
    // Để sắp xếp: ưu tiên l nhỏ nhất, nếu l bằng nhau thì r lớn nhất đứng trước
    bool operator<(const Interval& other) const {
        if (l != other.l) return l < other.l;
        return r > other.r;
    }
};

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m;
    if (!(cin >> n >> m)) return 0;

    vector<Interval> a;
    for (int i = 0; i < n; ++i) {
        int s, e;
        cin >> s >> e;
        if (s < e) {
            a.push_back({i, s, e});
            a.push_back({i, s + m, e + m});
        } else {
            // Qua đêm: ví dụ 90 -> 10 trong ngày 100 thành 90 -> 110
            a.push_back({i, s, e + m});
            a.push_back({i, s + m, e + 2 * m});
        }
    }

    // Sắp xếp các khoảng theo thời gian bắt đầu
    sort(a.begin(), a.end());

    int sz = a.size();
    
    // next_interval[i] lưu chỉ số của khoảng tốt nhất để nhảy tới từ khoảng i
    vector<int> nxt(sz);
    
    // Kỹ thuật 2 con trỏ (Two Pointers) hoặc tìm max prefix để tìm nxt[i]
    // Vì mảng đã sort theo L, với mỗi i, ta cần tìm j sao cho L[j] <= R[i] và R[j] là max.
    
    // Precompute max R cho các prefix để truy vấn nhanh
    // Tuy nhiên, chỉ cần duy trì một "cửa sổ" các interval hợp lệ.
    // Cách đơn giản hơn: Với mỗi i, ta tìm upper_bound của R[i] trong mảng L,
    // và cần max R trong đoạn [0, index_found - 1].
    
    // Xây dựng mảng max_r_index[k] lưu chỉ số của interval có R lớn nhất trong phạm vi a[0...k]
    vector<int> max_r_idx(sz);
    max_r_idx[0] = 0;
    for(int i = 1; i < sz; ++i){
        if (a[i].r > a[max_r_idx[i-1]].r) {
            max_r_idx[i] = i;
        } else {
            max_r_idx[i] = max_r_idx[i-1];
        }
    }

    // Xây dựng Binary Lifting
    // up[k][i] là chỉ số interval sau khi nhảy 2^k bước từ i
    int LOG = 20;
    vector<vector<int>> up(LOG, vector<int>(sz));

    // Tìm điểm đến trực tiếp (bước nhảy 2^0)
    for (int i = 0; i < sz; ++i) {
        // Tìm khoảng j xa nhất về bên phải mà a[j].l <= a[i].r
        // Sử dụng binary search trên l
        Interval key; 
        key.l = a[i].r; 
        key.r = 2000000000; // Để đảm bảo upper_bound trả về phần tử đầu tiên > a[i].r
        
        auto it = upper_bound(a.begin(), a.end(), key);
        int idx = distance(a.begin(), it) - 1;

        if (idx == -1) {
            // Không có khoảng nào bắt đầu trước khi i kết thúc (trường hợp này khó xảy ra nếu sort đúng và dữ liệu hợp lệ)
            up[0][i] = i; 
        } else {
            int best_idx = max_r_idx[idx];
            // Nếu khoảng tốt nhất không giúp vươn xa hơn hiện tại, ta bị kẹt
            if (a[best_idx].r <= a[i].r) {
                up[0][i] = i;
            } else {
                up[0][i] = best_idx;
            }
        }
    }

    // Xây dựng các bước nhảy lớn hơn
    for (int k = 1; k < LOG; ++k) {
        for (int i = 0; i < sz; ++i) {
            up[k][i] = up[k-1][up[k-1][i]];
        }
    }

    int min_vaidilutes = INF;

    // Duyệt qua các khoảng ban đầu (nằm trong ngày đầu tiên)
    for (int i = 0; i < sz; ++i) {
        // Chỉ xét những khoảng bắt đầu trong phạm vi ngày gốc [0, m)
        if (a[i].l >= m) continue;

        int curr = i;
        int count = 1;
        int target = a[i].l + m;

        // Nhảy binary lifting
        for (int k = LOG - 1; k >= 0; --k) {
            int next_node = up[k][curr];
            // Nếu nhảy 2^k bước mà vẫn chưa phủ đủ M (tức R < target) thì nhảy
            if (a[next_node].r < target) {
                curr = next_node;
                count += (1 << k);
            }
        }
        
        // Sau vòng lặp, curr đang ở vị trí sát đích nhất nhưng chưa qua đích.
        // Ta cần 1 bước nhảy nữa để kiểm tra xem có qua đích không.
        int final_node = up[0][curr];
        
        if (a[final_node].r >= target) {
            min_vaidilutes = min(min_vaidilutes, count + 1);
        } else {
            // Nếu ngay cả bước cuối cũng không qua được hoặc bị kẹt
            // thì phương án bắt đầu từ i là không khả thi
        }
    }

    if (min_vaidilutes == INF) {
        cout << -1 << endl;
    } else {
        cout << min_vaidilutes << endl;
    }

    return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 17
• Subtask 3: 0 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26