Submission #1012752

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012752		Beerus13	Fire (BOI24_fire)	C++17	100 / 100	69 ms	21684 KiB

Main

#include<bits/stdc++.h>
using namespace std;
#define FOR(i, a, b)  for(int i = (a), _b = (b); i <= _b; ++i)
#define FORD(i, b, a) for(int i = (b), _a = (a); i >= _a; --i)
#define REP(i, a, b)  for(int i = (a), _b = (b); i < _b;  ++i)
#define REPD(i, b, a) for(int i = (b), _a = (a); i > _a;  --i)
#define MASK(i) (1LL << (i))
#define BIT(mask, i) (((mask) >> (i)) & 1)
#define __builtin_popcount __builtin_popcountll
#define all(val) val.begin(), val.end()
#define ll long long
#define ull unsigned long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define fi first
#define se second

mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
ll Rand(ll l, ll r) {return l + rng() % (r - l + 1);}

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y) {
            x = y;
            return true;
        } else return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y) {
            x = y;
            return true;
        } else return false;
    }
template<class T>
    T Abs(const T &x) {
        return (x < 0 ? -x : x);
    }

const int N = 2e5 + 5;
const int inf = 1e9;
const int K = 18;

int n, m;
pii a[N];
int nxt[N][K];
vector<pii> opt;

int calc(int pos, int r) {
    if(opt[pos].se >= r) return 1;
    int ans = 1;
    FORD(i, K - 1, 0) if(pos + MASK(i) < n) {
        if(opt[nxt[pos][i]].se < r) {
            ans += MASK(i);
            pos = nxt[pos][i];
        }
    }
    REP(i, 0, K) if(pos + MASK(i) < n) {
        if(opt[nxt[pos][i]].se >= r) {
            ans += MASK(i);
            return ans;
        }
    }
    return inf;
}

void solve() {
    cin >> n >> m;
    FOR(i, 1, n) {
        cin >> a[i].fi >> a[i].se;
        if(a[i].fi > a[i].se) a[i].se += m;
    }

    sort(a + 1, a + n + 1, [&](pii &x, pii &y) {
        if(x.fi != y.fi) return x.fi < y.fi;
        return x.se > y.se;
    });

    for(int i = 1, mx = 0; i <= n; ++i) {
        if(a[i].se > mx) opt.push_back(a[i]);
        maximize(mx, a[i].se);
    }

    n = opt.size();
    for(int i = 0, j = 0; i < n; ++i) {
        while(j < n && opt[j].fi <= opt[i].se) ++j;
        nxt[i][0] = j - 1;
    }
    REP(j, 1, K) REP(i, 0, n) nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
    int ans = inf;
    REP(i, 0, n) {
        minimize(ans, calc(i, opt[i].fi + m));
    }
    cout << (ans == inf ? -1 : ans) << '\n';
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int test = 1;
    // cin >> test;
    while(test--) solve();
    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