Submission #1281448

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281448		lightentheshadow	Fire (BOI24_fire)	C++20	100 / 100	114 ms	20988 KiB

Main

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

const int maxN = 2e5 + 5;
pair<int, int> p[maxN];
int s[maxN], jump[20][maxN];

struct node {
    int val, id;
} st[maxN << 4];

node Merge(node A, node B) {
    if (A.val >= B.val) return A;
    return B;
}

void build(int id, int l, int r) {
    if (l == r) {
        st[id].val = p[l].second;
        st[id].id = l;
        return ;
    }

    int mid = (l + r) >> 1;

    build(id << 1, l, mid);
    build(id << 1 | 1, mid + 1, r);

    st[id] = Merge(st[id << 1], st[id << 1 | 1]);
}

node get(int id, int l, int r, int u, int v) {
    if (v < l || r < u) return {-100, 0};

    if (u <= l && r <= v) return st[id];

    int mid = (l + r) >> 1;

    node A = get(id << 1, l, mid, u, v);
    node B = get(id << 1 | 1, mid + 1, r, u, v);

    return Merge(A, B);
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> p[i].first >> p[i].second;
        if (p[i].first > p[i].second) p[i].second += m;
    }

    sort(p + 1, p + n + 1);
    build(1, 1, n);
    for (int i = 1; i <= n; i++)
        s[i] = p[i].first;

    for (int i = 1; i <= n; i++) {
        int l = lower_bound(s + 1, s + n + 1, p[i].first) - s;
        int r = upper_bound(s + 1, s + n + 1, p[i].second) - s - 1;
        node res = get(1, 1, n, l, r);
        if (res.val <= p[i].second) continue;
        jump[0][i] = res.id;
    }

    for (int k = 1; k <= 17; k++)
        for (int i = 1; i <= n; i++)
            jump[k][i] = jump[k - 1][jump[k - 1][i]];

    int ans = 1e9;
    for (int i = 1; i <= n; i++) {
        int id = i, goal = p[i].first + m, res = 0;
        for (int k = 17; k >= 0; k--) {
            int nxt = jump[k][id];
            if (nxt == 0 || p[nxt].second >= goal) continue;
            res += (1 << k);
            id = nxt;
        }

        res++; id = jump[0][id];
        if (p[id].second >= goal) ans = min(ans, res);
    }

    if (ans == 1e9) cout << -1 << '\n';
        else cout << ans + 1 << '\n';

    return 0;
}

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