Submission #1217561

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217561		asdfghqwert	Fire (BOI24_fire)	C++20	100 / 100	98 ms	48984 KiB

Main

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

struct Seg {
    ll l, r;
};

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll m;
    cin >> n >> m;
    vector<Seg> segs(n);
    for(int i = 0; i < n; i++){
        cin >> segs[i].l >> segs[i].r;
        // ensure normalized in [0, m)
        if(segs[i].l > segs[i].r) {
            // wrap‑around segment: split into two
            // [l, m) U [0, r]
            // but easier to treat as l→r+m
            segs[i].r += m;
        }
    }

    // Duplicate each to handle wrap around
    vector<Seg> all;
    all.reserve(2*n);
    for(auto &s : segs){
        all.push_back(s);
        all.push_back({s.l + m, s.r + m});
    }
    sort(all.begin(), all.end(), [](auto &a, auto &b){
        return a.l < b.l;
    });

    int N = all.size();
    // For each i, we'll find the index j of the interval
    // with max r among those with l <= all[i].r.
    // We sweep from left to right maintaining a pointer k
    // and a priority queue (max‐heap) on r.
    vector<int> nxt(N, -1);
    priority_queue<pair<ll,int>> pq;
    int k = 0;
    for(int i = 0; i < N; i++){
        // push into heap all intervals whose left <= current's r
        while(k < N && all[k].l <= all[i].r){
            pq.push({ all[k].r, k });
            k++;
        }
        // the top of heap is the interval reaching farthest
        nxt[i] = pq.empty() ? -1 : pq.top().second;
    }

    // Build binary lifting table up to LOG levels
    int LOG = 1;
    while((1<<LOG) <= N) LOG++;
    vector<vector<int>> jump(LOG, vector<int>(N, -1));
    jump[0] = nxt;
    for(int j = 1; j < LOG; j++){
        for(int i = 0; i < N; i++){
            int mid = jump[j-1][i];
            jump[j][i] = (mid < 0 ? -1 : jump[j-1][mid]);
        }
    }

    // Now for each original interval in [0,m), compute
    // min jumps to cover length m.
    ll ans = LLONG_MAX;
    for(int i = 0; i < N; i++){
        if(all[i].l >= m) break;    // only starts in [0,m)
        ll target = all[i].l + m;
        int cur = i;
        ll used = 1;                // we start by using interval i
        if(all[i].r >= target){
            ans = min(ans, used);
            continue;
        }
        // jump from highest bit down
        for(int b = LOG-1; b >= 0; b--){
            int nxti = jump[b][cur];
            if(nxti >= 0 && all[nxti].r < target){
                cur = nxti;
                used += (1LL<<b);
            }
        }
        // one more jump to cover
        int final_jump = nxt[cur];
        if(final_jump >= 0 && all[final_jump].r >= target){
            ans = min(ans, used+1);
        }
    }

    if(ans == LLONG_MAX) 
        cout << "-1\n";      // impossible
    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