Submission #1164294

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164294		cjtsai	Fire (BOI24_fire)	C++20	100 / 100	165 ms	78960 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
 
struct Interval {
    int start, end;
};
 
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M;
    cin >> N >> M;
    vector<Interval> intervals;
    
    // Extend intervals to the doubled timeline [0, 2M]
    for (int i = 0; i < N; i++){
        int s, e;
        cin >> s >> e;
        if(s <= e){
            intervals.push_back({s, e});
            intervals.push_back({s + M, e + M});
        } else {
            intervals.push_back({s, e + M});
        }
    }
    
    // Sort intervals by start time
    sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b){
        return a.start < b.start;
    });
    
    // Build the discrete timeline B (all interval start and end times plus boundaries)
    vector<int> B;
    for (const auto &intv : intervals) {
        B.push_back(intv.start);
        B.push_back(intv.end);
    }
    B.push_back(0);
    B.push_back(2 * M);
    sort(B.begin(), B.end());
    B.erase(unique(B.begin(), B.end()), B.end());
    int Bsize = B.size();
    
    // For each discrete time B[i], compute f[i]:
    // the farthest time reachable in one jump (using any interval with start <= B[i])
    vector<int> f(Bsize, 0);
    int idx = 0;
    int current_max = 0;
    for (int i = 0; i < Bsize; i++){
        int t = B[i];
        while (idx < intervals.size() && intervals[idx].start <= t) {
            current_max = max(current_max, intervals[idx].end);
            idx++;
        }
        f[i] = current_max;
    }
    
    // For each B[i], define nxt[i] = index in B such that B[nxt[i]] is the maximum reachable time from B[i]
    vector<int> nxt(Bsize, 0);
    for (int i = 0; i < Bsize; i++){
        int val = f[i];
        int j = upper_bound(B.begin(), B.end(), val) - B.begin() - 1;
        nxt[i] = j;
    }
    
    // Build binary lifting table dp[k][i]:
    // dp[k][i] is the index in B reached after 2^k jumps starting from B[i].
    int L = 0;
    while ((1 << L) <= Bsize) L++;
    vector<vector<int>> dp(L, vector<int>(Bsize, 0));
    for (int i = 0; i < Bsize; i++){
        dp[0][i] = nxt[i];
    }
    for (int k = 1; k < L; k++){
        for (int i = 0; i < Bsize; i++){
            dp[k][i] = dp[k - 1][ dp[k - 1][i] ];
        }
    }
    
    // For each candidate starting time T in [0, M), use binary lifting to compute 
    // the minimal number of jumps needed to reach T + M.
    int ans = INT_MAX;
    for (int i = 0; i < Bsize; i++){
        int T = B[i];
        if(T < 0 || T >= M)
            continue; // Only consider starting times in [0, M)
        
        int target = T + M;
        int cnt = 0;
        int cur = i; // current index in B (represents current coverage time B[cur])
        
        // If we're already covering [T, T+M], no jumps needed.
        if(B[cur] >= target){
            ans = min(ans, cnt);
            continue;
        }
        
        // Use binary lifting: try the largest jump that doesn't reach the target yet.
        for (int k = L - 1; k >= 0; k--){
            int next_idx = dp[k][cur];
            if(B[next_idx] < target){
                cnt += (1 << k);
                cur = next_idx;
            }
        }
        // One more jump is needed.
        if(B[dp[0][cur]] >= target){
            cnt++;
            ans = min(ans, cnt);
        }
    }
    
    if(ans == INT_MAX)
        cout << -1 << "\n";
    else
        cout << ans << "\n";
    
    return 0;
}

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