Submission #1066828

#	Time	Username	Problem	Language	Result	Execution time	Memory
1066828		vjudge1	Fire (BOI24_fire)	C++17	53 / 100	48 ms	5724 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;
    if(n <= 5000){
        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++;
                }
                if((l == n && nxt < vai[i].fi + m) || (nxt == cur)){
                    bisa = false;
                    break;
                }
                cur = nxt;
                banyak++;
                
            }
            if(bisa){
                res = min(res, banyak);
            }
                
        }
    }else{
        int l = 0;
        int banyak = 0;
        int nxt = 0;
        int cur = 0;
        bool bisa = true;
        while(cur < m){
            while(l < n && vai[l].fi <= cur){
                nxt = max(nxt, vai[l].se);
                l++;
            }
            if((l == n && nxt < m) || (nxt == cur)){
                bisa = false;
                break;
            }
            cur = nxt;
            banyak++;
            
        }
        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: 14 / 14
• Subtask 2: 17 / 17
• Subtask 3: 9 / 9
• Subtask 4: 13 / 13
• Subtask 5: 0 / 21
• Subtask 6: 0 / 26