Submission #1062067

#	Time	Username	Problem	Language	Result	Execution time	Memory
1062067		Jarif_Rahman	Fire (BOI24_fire)	C++17	100 / 100	209 ms	50496 KiB

Main

#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m; cin >> n >> m;
    vector<pair<int, int>> A(n);
    int MX = -1;
    for(auto &[x, y]: A){
        cin >> x >> y;
        if(x > y){
            MX = max(MX, y);
            y+=m;
        }
    }
    sort(A.begin(), A.end());

    map<int, vector<int>> L, R;
    for(int i = 0; i < n; i++){
        L[A[i].first].push_back(i);
        if(A[i].second < m) R[A[i].second].push_back(i);
    }

    vector<int> nxt(n, -1);
    set<pair<int, int>> st;
    while(!L.empty() || !R.empty()){
        if(R.empty() || (!L.empty() && L.begin()->first <= R.begin()->first)){
            auto [t, a] = *L.begin();
            L.erase(L.begin());
            for(int i: a) st.insert({A[i].second, i});
        }
        else{
            auto [t, a] = *R.begin();
            R.erase(R.begin());
            for(int i: a){
                st.erase({A[i].second, i});
                if(!st.empty() && st.rbegin()->first > A[i].second && A[st.rbegin()->second].first > A[i].first) nxt[i] = st.rbegin()->second;
            }
        }
    }

    vector<int> cnt(n, 0), mx(n, 0);
    int ans = 1e9;
    for(int i = n-1; i >= 0; i--){
        if(nxt[i] == -1){
            if(A[i].second >= m) cnt[i] = 1, mx[i] = A[i].second-m;
        }
        else if(cnt[nxt[i]] != 0){
            cnt[i] = cnt[nxt[i]]+1;
            mx[i] = mx[nxt[i]];
            if(mx[i] >= A[i].first) ans = min(ans, cnt[i]);
            else if(MX >= A[i].first) ans = min(ans, cnt[i]+1);
        }
    }

    if(ans > n) ans = -1;
    cout << ans << "\n";
}

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