제출 #1286759

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1286759		tdd209	Fire (BOI24_fire)	C++20	100 / 100	109 ms	19728 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define fti(i, x, y) for (int i = x; i <= y; ++i)
#define ftd(i, x, y) for (int i = x; i >= y; --i)
#define F first
#define S second

int n, m, res = 200005, lg;
pair <int, int> t[200005];
bool gr[200005];
int s[200005], e[200005], up[200005][20];
int tree[800005];

int get(int x, int y)
{
    return (t[x].S < t[y].S ? y : x);
}

void build(int nd = 1, int l = 1, int r = n)
{
    if (l == r)
    {
        tree[nd] = l; return;
    }
    int c = (l + r) >> 1, p1 = nd << 1, p2 = p1 | 1;
    build(p1, l, c); build(p2, c + 1, r);
    tree[nd] = get(tree[p1], tree[p2]);
}

int query(int L, int R, int nd = 1, int l = 1, int r = n)
{
    if (r < L || R < l) return 0;
    if (L <= l && r <= R) return tree[nd];
    int c = (l + r) >> 1, p1 = nd << 1, p2 = p1 | 1;
    return get(query(L, R, p1, l, c), query(L, R, p2, c + 1, r));
}

void sus2()
{
    build();
    fti(i, 1, n)
    {
        pair <int, int> nxt = {t[i].S + 1, 0};
        int pos = lower_bound(t + 1, t + n + 1, nxt) - t - 1;
        up[i][0] = query(1, pos);
    }
    lg = __lg(n);
    fti(j, 1, lg)
        fti(i, 1, n)
            up[i][j] = up[up[i][j - 1]][j - 1];
    fti(i, 1, n)
    {
        int l = t[i].F, cur = i, cnt = 1;
        ftd(j, 19, 0)
        {
            int r = t[up[cur][j]].S;
            if (r && r - l + 1 <= m)
                cur = up[cur][j], cnt += (1 << j);
        }
        int r = t[up[cur][0]].S;
        if (r - l + 1 > m)
            res = min(res, cnt + 1);
    }
    cout << (res > n ? -1 : res);
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    fti(i, 1, n)
    {
        cin >> t[i].F >> t[i].S;
        if (t[i].F > t[i].S) t[i].S += m;
    }
    sort(t + 1, t + 1 + n);
    sus2();
    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