Submission #1182509

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182509		gyg	Fire (BOI24_fire)	C++20	40 / 100	2110 ms	864692 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, M = 1e9;

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

struct Sgt {
    arr<pii, (int) 1e7> tr;
    arr<int, (int) 1e7> lf, rg;
    int nm = 1;
    
    void prp(int u) {
        if (lf[u]) return;
        lf[u] = ++nm, rg[u] = ++nm;
    }
    void upd(int i, pii x, int u = 1, int lw = 0, int hg = m) {
        if (lw == hg) { tr[u] = max(tr[u], x); return; }
        prp(u);
        int md = (lw + hg) / 2;
        if (i <= md) upd(i, x, lf[u], lw, md);
        else upd(i, x, rg[u], md + 1, hg);
        tr[u] = max(tr[lf[u]], tr[rg[u]]);
    }
    pii qry(int l, int r, int u = 1, int lw = 0, int hg = m) {
        if (l <= lw && hg <= r) return tr[u];
        prp(u);
        int md = (lw + hg) / 2;
        pii ans;
        if (l <= md) ans = max(ans, qry(l, r, lf[u], lw, md));
        if (r > md) ans = max(ans, qry(l, r, rg[u], md + 1, hg));
        return ans;
    }
} 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.sync_with_stdio(false), cin.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> l[i] >> r[i];

    jmp_cmp();
    ans_cmp();
}

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