Submission #1281392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281392		HiepVu217	Fire (BOI24_fire)	C++20	21 / 100	96 ms	20504 KiB

Main

//Proud of You//
#include <bits/stdc++.h>
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
using namespace std;
const int N = 2e5 + 17;
int n, m, lg, st[4 * N], f[N][21];
pair <int, int> a[N];
inline int calc (int u, int v)
{
    return a[u].second > a[v].second ? u : v;
}
inline void build (int id, int l, int r)
{
    if (l == r)
    {
        st[id] = l;
        return;
    }
    int mid = l + r >> 1;
    build (id * 2, l, mid);
    build (id * 2 + 1, mid + 1, r);
    st[id] = calc (st[id * 2], st[id * 2 + 1]);
}
inline long long get (int id, int l, int r, int u, int v)
{
    if (v < l || r < u)
    {
        return 0;
    }
    if (u <= l && r <= v)
    {
        return st[id];
    }
    int mid = l + r >> 1;
    return calc (get (id * 2, l, mid, u, v), get (id * 2 + 1, mid + 1, r, u, v));
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for (int i = 1, l, r; i <= n; ++i)
    {
        cin >> l >> r;
        if (r < l)
        {
            r += m - 1;
        }
        a[i] = {l, r};
    }
    sort (a + 1, a + n + 1);
    build (1, 1, n);
    for (int i = 1; i <= n; ++i)
    {
        auto [l, r] = a[i];
        pair <int, int> _ = {r + 1, 0};
        int j = lower_bound (a + 1, a + n + 1, _) - a;
        f[i][0] = get (1, 1, n, i + 1, j - 1);
    }
    lg = __lg(n);
    for (int j = 1; j <= lg; ++j)
    {
        for (int i = 1; i <= n; ++i)
        {
            f[i][j] = f[f[i][j - 1]][j - 1];
        }
    }
    int ans = 1e9;
    for (int i = 1; i <= n; ++i)
    {
        int l = a[i].first, x = i, z = 1;
        for (int j = lg; j >= 0; --j)
        {
            int r = a[f[x][j]].second;
            if (r && r - l + 1 < m)
            {
                x = f[x][j], z += (1 << j);
            }
        }
        int r = a[f[x][0]].second;
        if (r - l + 1 >= m)
        {
            ans = min (ans, z + 1);
        }
    }
    if (ans == 1e9)
    {
        ans = -1;
    }
    cout << ans;
}

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