Submission #1182492

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182492		gyg	Fire (BOI24_fire)	C++20	0 / 100	55 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 upd(int i, pii x) {
        tr[i] = max(tr[i], x);
    }
    pii qry(int l, int r) {
        pii mx;
        for (int i = l; i <= r; i++) mx = max(mx, tr[i]);
        return mx;
    }
} sgt[2];

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

    jmp[0][0] = {0, 0};
    for (int i = 1; i <= n; i++) {
        jmp[i][0] = {0, 0};

        if (l[i] <= r[i]) {
            pii x = sgt[0].qry(l[i], r[i]);
            pii y = sgt[1].qry(l[i], r[i]);

            if (y.sec) {
                jmp[i][0] = max(jmp[i][0], {y.fir + m - r[i], y.sec});
            } else if (x.fir > r[i]) {
                jmp[i][0] = max(jmp[i][0], {x.fir - r[i], x.sec});
            }
        } else {
            pii x = max(sgt[0].qry(0, r[i]), sgt[1].qry(l[i], m - 1));
            pii y = sgt[1].qry(0, r[i]);

            if (y.sec) {
                jmp[i][0] = max(jmp[i][0], {y.fir + m - r[i], y.sec});
            } else if (x.fir > r[i]) {
                jmp[i][0] = max(jmp[i][0], {x.fir - r[i], x.sec});
            }
        }
    }

    // for (int i = 0; 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