Submission #1182476

#	Time	Username	Problem	Language	Result	Execution time	Memory
1182476		gyg	Fire (BOI24_fire)	C++20	40 / 100	2099 ms	107076 KiB

Main

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

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

arr<arr<vec<int>, LG>, N> jmp;
void jmp_cmp() {
    jmp[0][0] = {0, 0};
    for (int i = 1; i <= n; i++) {
        jmp[i][0] = {0, 0};
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (l[i] <= r[i] && l[j] <= r[j]) {
                if (l[j] < l[i] || l[j] > r[i]) continue;
                if (r[j] <= r[i]) continue;   
                jmp[i][0] = max(jmp[i][0], {r[j] - r[i], j});
            } else if (l[i] <= r[i] && l[j] > r[j]) {
                if (l[j] < l[i] || l[j] > r[i]) continue;
                jmp[i][0] = max(jmp[i][0], {r[j] + m - r[i], j});
            } else if (l[i] > r[i] && l[j] <= r[j]) {
                if (l[j] > r[i]) continue;
                if (r[j] <= r[i]) continue;
                jmp[i][0] = max(jmp[i][0], {r[j] - r[i], j});
            } else {
                if (l[j] < l[i]) continue;
                if (r[j] <= r[i]) continue;
                jmp[i][0] = max(jmp[i][0], {r[j] - r[i], j});
            }
        }
    }

    // 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]};
        }
    }
}

// i changes
int lft(int i) {
    int rq = m - (r[i] - l[i]);
    // cout << i << ": " << rq << '\n';

    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: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 0 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26