Submission #1214821

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214821		biank	Fire (BOI24_fire)	C++20	100 / 100	85 ms	20040 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
#define forn(i,n) for(int i=0;i<int(n);i++)
#define forsn(i,s,n) for(int i=int(s);i<int(n);i++)
#define dforn(i,n) for(int i=int(n)-1;i>=0;i--)
#define dforsn(i,s,n) for(int i=int(n)-1;i>=int(s);i--)
#define fst first
#define snd second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
 
typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef pair<int,int> ii;
 
const int INF = 1e9;
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n, m;
    cin >> n >> m;
    vector<ii> ranges(n);
    for (auto &[s, e] : ranges) {
        cin >> s >> e;
        if (s > e) e += m;
    }
    vi orderByL(n), orderByR(n);
    iota(all(orderByL), 0);
    iota(all(orderByR), 0);
    sort(all(orderByL), [&](const int &lhs, const int &rhs) {
        return ranges[lhs].fst < ranges[rhs].fst;
    });
    sort(all(orderByR), [&](const int &lhs, const int &rhs) {
        return ranges[lhs].snd < ranges[rhs].snd;
    });
    const int k = 20;
    vector<vi> up(k, vi(n));
    pair<int, int> best = {-1, -1};
    {
        int j = 0;
        forn(i, n) {
            while (j < n && ranges[orderByL[j]].fst <= ranges[orderByR[i]].snd) {
                best = max(best, {ranges[orderByL[j]].snd, orderByL[j]});
                j++;
            }
            assert(best.snd != -1);
            up[0][orderByR[i]] = best.snd;
        }
    }
    forn(i, k - 1) forn(j, n) {
        up[i + 1][j] = up[i][up[i][j]];
    }
    int ans = INF;
    forn(i, n) {
        auto [start, end] = ranges[i];
        int res = 1;
        int curr = i;
        dforn(p, k) {
            if (ranges[up[p][curr]].snd - start < m) {
                res += 1 << p;
                curr = up[p][curr];
            }
        }
        curr = up[0][curr];
        res++;
        if (ranges[curr].snd - start >= m) ans = min(ans, res);
    }
    if (ans == INF) cout << "-1\n";
    else cout << ans << '\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