oj.uz

Submission #1066820

# Submission time Handle Problem Language Result Execution time Memory
1066820 2024-08-20T07:41:27 Z vjudge1 Fire (BOI24_fire) C++17
0 / 100
 2000 ms 348 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2089 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2089 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2089 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Execution timed out 2095 ms 348 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Execution timed out 2068 ms 348 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Execution timed out 2089 ms 348 KB Time limit exceeded
4 Halted 0 ms 0 KB -