Submission #1188877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188877		imppppp	Fire (BOI24_fire)	C++20	0 / 100	0 ms	328 KiB

Main

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

using ll = long long;
const int INF = 1e9;
const ll  LINF = 4e18;
const int MOD = 1'000'000'007;          // not needed for this task

struct Seg { ll l, r; };               // [l, r]  (inclusive)

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

    int N;
    ll M;
    if (!(cin >> N >> M)) return 0;

    vector<Seg> segs;  segs.reserve(2 * N);

    for (int i = 0; i < N; ++i) {
        ll s, e;  cin >> s >> e;
        if (s <= e) {
            segs.push_back({s, e});
            segs.push_back({s + M, e + M});       // duplicate for wrap
        } else {
            segs.push_back({s, e + M});           // overnight
        }
    }

    sort(segs.begin(), segs.end(),
         [](const Seg& a, const Seg& b) { return a.l < b.l; });

    const int SZ = segs.size();
    vector<int> prefBest(SZ);                     // index of max‑end so far
    prefBest[0] = 0;
    for (int i = 1; i < SZ; ++i) {
        prefBest[i] =
            (segs[i].r > segs[prefBest[i - 1]].r) ? i : prefBest[i - 1];
    }

    /*  next[i] : greedy successor  */
    vector<int> nxt(SZ, -1);
    for (int i = 0; i < SZ; ++i) {
        ll reach = segs[i].r;
        int pos  = int(upper_bound(segs.begin(), segs.end(), reach,
                     [](ll x, const Seg& s) { return x < s.l; })
                     - segs.begin()) - 1;
        if (pos >= 0) {
            int cand = prefBest[pos];
            if (segs[cand].r > segs[i].r) nxt[i] = cand;
        }
    }

    /*  binary lifting  */
    const int LOG = 18;                           // 2^18 > 4*10^5
    vector<array<int, LOG + 1>> up(SZ);
    vector<array<ll , LOG + 1>> far(SZ);

    for (int i = 0; i < SZ; ++i) {
        up[i][0]  = nxt[i];
        far[i][0] = segs[i].r;
    }
    for (int k = 1; k <= LOG; ++k) {
        for (int i = 0; i < SZ; ++i) {
            int mid = up[i][k - 1];
            if (mid == -1) {
                up[i][k]  = -1;
                far[i][k] = far[i][k - 1];
            } else {
                up[i][k]  = up[mid][k - 1];
                far[i][k] = max(far[i][k - 1], far[mid][k - 1]);
            }
        }
    }

    /*  try every interval whose left end is within the first day  */
    int bestAns = INF;

    for (int i = 0; i < SZ && segs[i].l < M; ++i) {
        ll goal = segs[i].l + M;
        if (segs[i].r >= goal) {                  // covers whole day alone
            bestAns = 1;
            continue;
        }
        int cur = i, used = 1;
        for (int k = LOG; k >= 0; --k) {
            if (up[cur][k] != -1 && far[cur][k] < goal) {
                used += 1 << k;
                cur   = up[cur][k];
            }
        }
        int nx = nxt[cur];
        if (nx != -1 && segs[nx].r >= goal) {
            bestAns = min(bestAns, used + 1);
        }
    }

    cout << (bestAns == INF ? -1 : bestAns) << '\n';
    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