Submission #1286755

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286755		tdd209	Fire (BOI24_fire)	C++20	0 / 100	1 ms	576 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 F first
#define S second

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

void zip()
{
    vector <int> z;
    z.push_back(m);
    fti(i, 1, n)
        z.push_back(t[i].F), z.push_back(t[i].S);
    z.push_back(1e9 + 7);
    sort(z.begin(), z.end());
    z.erase(unique(z.begin(), z.end()), z.end());
    m = lower_bound(z.begin(), z.end(), m) - z.begin();
    fti(i, 1, n)
    {
        t[i].F = lower_bound(z.begin(), z.end(), t[i].F) - z.begin();
        t[i].S = lower_bound(z.begin(), z.end(), t[i].S) - z.begin();
    }
}

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

bool ok[51];

void suf1()
{
    int msk = (1 << n) - 1;
    fti(mask, 1, msk)
    {
        bool chek = 1;
        fti(i, 0, m) ok[i] = 0;
        fti(i, 1, n)
            if ((mask >> (i - 1)) & 1)
            {
                fti(u, t[i].F, min(t[i].S, m)) ok[u] = 1;
            }
        fti(i, 0, m)
            if (!ok[i])
            {
                chek = 0; break;
            }
        if (chek) res = min(res, __builtin_popcount(mask));
    }
    cout << (res > n ? -1 : res);
}

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

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);
    res = n + 1;
    int mock = t[1].F;
    m -= mock;
    fti(i, 1, n)
    {
        t[i].F -= mock, t[i].S -= mock;
    }
    zip();
    if (n <= 20)
        suf1();
    else
        sus2();
    return 0;
}

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