Submission #1166439

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166439		Iskachun	Fire (BOI24_fire)	C++20	100 / 100	206 ms	81844 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
void solve() {
    int n, m; cin >> n >> m;
    vector<pair<int,int>> a(n);
    for (int i = 0; i < n; i++) {
        int l, r; cin >> l >> r;
        if (l <= r) {
            a.push_back({l, r});
            a.push_back({l + m, r + m});
        } else a.push_back({l, r + m});
    }
    sort(a.begin(), a.end());
    vector<int> b;
    for (auto [x, y] : a) {
        b.push_back(x), b.push_back(y);
    }
    b.push_back(0), b.push_back(2 * m);
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    int k = b.size();
    vector<int> c(k);
    int pos = 0, curr = 0;
    for (int i = 0; i < k; i++) {
        int x = b[i];
        while (pos < a.size() and a[pos].first <= x) {
            curr = max(curr, a[pos].second); pos++;
        }
        c[i] = curr;
    }
    vector<int> nxt(k);
    for (int i = 0; i < k; i++) {
        int j = upper_bound(b.begin(), b.end(), c[i]) - b.begin() - 1;
        nxt[i] = j;
    }
    int l = 0;
    while ((1 << l) <= k) l++;
    vector<vector<int>> dp(l, vector<int> (k));
    for (int i = 0; i < k; i++) {
        dp[0][i] = nxt[i];
    }
    for (int i = 1; i < l; i++) for (int j = 0; j < k; j++) dp[i][j] = dp[i - 1][dp[i - 1][j]];
    int ans = 1e9;
    for (int i = 0; i < k; i++) {
        int x = b[i];
        if (x < 0 or x >= m) continue;
        int need = x + m, cnt = 0, curr = i;
        if (b[curr] >= need) {
            ans = min(ans, cnt); continue;
        }
        for (int j = l - 1; j >= 0; j--) {
            int pos = dp[j][curr];
            if (b[pos] < need) {
                cnt += (1 << j), curr = pos;
            }
        }
        if (b[dp[0][curr]] >= need) {
            cnt++;
            ans = min(ans, cnt);
        }
    }
    if (ans == 1e9) ans = -1;
    cout << ans;
}
int main() {
    //freopen("filename.in", "r", stdin), freopen("filename.out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int t = 1; //cin >> t;
    while (t--) solve();
}

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