Submission #1066820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066820		vjudge1	Fire (BOI24_fire)	C++17	0 / 100	2095 ms	348 KiB

Main

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
#define fi first 
#define se second

using namespace std;


int n, m;

void solve(){
    cin >> n >> m;
    vector<pair<int, int>> vai(n);
    for(int i = 0; i < n; i++){
        cin >> vai[i].fi >> vai[i].se;
    }
    sort(vai.begin(), vai.end());

    for(int i = 0; i < n; i++){
        if(vai[i].se < vai[i].fi){
            vai[i].se += m;
        }
    }

    int res = 1e9;
    for(int i = 0; i < n; i++){
    
        int l = 0;
        int banyak = 1;
        int nxt = vai[i].se;
        int cur = vai[i].se;
        bool bisa = true;
        while(cur < vai[i].fi + m){
            while(l < n && vai[l].fi <= cur){
                nxt = max(nxt, vai[l].se);
                l++;
            }
            cur = nxt;
            banyak++;
            if(l == n && cur < vai[i].fi + m){
                bisa = false;
                break;
            }
        }
        if(bisa){
            res = min(res, banyak);
        }
    }
    if(res != 1e9){
        cout << res << endl;
    }else{
        cout << -1 << endl;
    }
    
    

}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    while(t--){
        solve();
    }
}

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