Submission #1182480

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182480		gyg	Fire (BOI24_fire)	C++20	0 / 100	48 ms	103752 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define arr array 
#define vec vector 
#define pii pair<int, int>
#define fir first
#define sec second
const int N = 2e5 + 5, LG = 22, INF = 1e12;

int n, m;
arr<int, N> l, r;

struct Sgt {
    arr<pii, 4 * N> tr;
    void bld() {
        for (int i = 1; i <= n; i++) {
            if (l[i] <= r[i]) tr[l[i]] = max(tr[l[i]], {r[i], i});
            else tr[l[i]] = max(tr[l[i]], {r[i] + m, i});
        }
    } 
    pii qry(int l, int r) {
        pii mx;
        for (int i = l; i <= r; i++) mx = max(mx, tr[i]);
        return mx;
    }
} sgt;

arr<arr<vec<int>, LG>, N> jmp;
void jmp_cmp() {
    sgt.bld();
    jmp[0][0] = {0, 0};
    for (int i = 1; i <= n; i++) {
        jmp[i][0] = {0, 0};

        pii x;
        if (l[i] <= r[i]) x = sgt.qry(l[i], r[i]);
        else x = max(sgt.qry(l[i], m - 1), sgt.qry(0, r[i]));

        if (x.fir - r[i] < 0) continue;
        jmp[i][0] = {x.fir - r[i], x.sec};
    }

    // for (int i = 1; i <= n; i++) {
    //     cout << i << ": " << jmp[i][0][0] << " " << jmp[i][0][1] << '\n';
    // }

    for (int i = 1; i <= 20; i++) {
        for (int j = 0; j <= n; j++) {
            vec<int> x = jmp[j][i - 1];
            vec<int> y = jmp[x[1]][i - 1];
            jmp[j][i] = {x[0] + y[0], y[1]};
        }
    }
}

int lft(int i) {
    int rq = m - (r[i] - l[i]);

    int cr = 0, ans = 1;
    for (int j = 20; j >= 0; j--) {
        vec<int> x = jmp[i][j];
        if (x[1] == 0) continue;
        if (cr + x[0] >= rq) continue;
        i = x[1], cr += x[0], ans += (1 << j);
    }
    
    vec<int> x = jmp[i][0];
    if (x[1] == 0) return INF;
    ans++;
    return ans;
}
void ans_cmp() {
    int ans = INF;
    for (int i = 1; i <= n; i++)
        ans = min(ans, lft(i));
    cout << ((ans == INF) ? -1 : ans) << '\n';
}

signed main() {
    // freopen("in", "r", stdin);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];

    jmp_cmp();
    ans_cmp();
}

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