oj.uz

Submission #1034374

# Submission time Handle Problem Language Result Execution time Memory
1034374 2024-07-25T12:52:36 Z istlemin Fire (BOI24_fire) C++17
34 / 100
 509 ms 89432 KB 
#include<bits/stdc++.h>

using namespace std;

#define rep(i,a,b) for(ll i = a; i<b;i++)
#define rrep(i,a,b) for(ll i = b-1; i>=a;i--)
#define trav(x,a) for(auto &x: a)
#define all(v) v.begin(),v.end()
#define sz(v) ll(v.size())

typedef long long ll;
typedef vector<ll> vl;
typedef pair<ll,ll> pll;

int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);

    ll n,m; cin>>n>>m;

    vl s(n);
    vl e(n);
    rep(i,0,n) cin>>s[i]>>e[i];

    vector<tuple<ll,ll,ll>> ev;
    rep(i,0,n){
        if(e[i]<s[i]){
            e[i]+=m;
        }
        ev.emplace_back(s[i],0,i);
        ev.emplace_back(e[i],1,i);
        ev.emplace_back(s[i]+m,0,i);
        ev.emplace_back(e[i]+m,1,i);
        ev.emplace_back(s[i]+m*2,0,i);
        ev.emplace_back(e[i]+m*2,1,i);
    }

    map<ll,ll> nextInterval;

    sort(all(ev));
    reverse(all(ev));
    set<pll> best;
    for(auto x: ev){
        auto [t,b,idx] = x;
        if(b==1){
            if(sz(best)){
                nextInterval[t] = max(nextInterval[t], prev(best.end())->first);
            }
            best.emplace(t,idx);
        } else {
            best.erase(make_pair(t+e[idx]-s[idx],idx));
        }
    }

    if(sz(nextInterval)==0){
        cout<<-1<<"\n";
        return 0;
    }

    // for(auto x: nextInterval){
    //     cout<<x.first<<": "<<x.second<<endl;
    // }

    deque<ll> q;
    q.push_front(nextInterval.begin()->first);
    ll topScore = 1e18;
    rep(i,0,10*n){
        // cout<<"q:"<<endl;
        // for(auto x:q){
        //     cout<<x<<" ";
        // }
        // cout<<endl;
        if(q.front()-q.back()>=m){
            topScore = min(topScore, sz(q)-1);
            q.pop_back();
        } else {
            if(nextInterval.find(q.front()) == nextInterval.end()) break;
            q.push_front(nextInterval[q.front()]);
        }
    }
    if(topScore==1e18){
        cout<<-1<<"\n";
    } else 
        cout<<topScore<<"\n";

}

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 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 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 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 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 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 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 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 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 416 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 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 600 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 7 ms 2516 KB Output is correct
16 Correct 7 ms 2260 KB Output is correct
17 Correct 8 ms 2512 KB Output is correct
18 Correct 8 ms 2260 KB Output is correct
19 Correct 7 ms 2512 KB Output is correct
20 Correct 272 ms 53660 KB Output is correct
21 Correct 358 ms 89432 KB Output is correct
22 Correct 383 ms 89428 KB Output is correct
23 Correct 400 ms 73812 KB Output is correct
24 Correct 302 ms 73852 KB Output is correct
25 Correct 509 ms 83224 KB Output is correct
26 Correct 471 ms 87420 KB Output is correct
27 Correct 452 ms 74880 KB Output is correct
28 Correct 376 ms 89172 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 600 KB Output is correct
2 Correct 1 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 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 464 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 7 ms 2516 KB Output is correct
13 Correct 8 ms 2252 KB Output is correct
14 Correct 7 ms 2004 KB Output is correct
15 Correct 307 ms 53732 KB Output is correct
16 Correct 438 ms 73820 KB Output is correct
17 Correct 274 ms 73044 KB Output is correct
18 Correct 314 ms 74368 KB Output is correct
19 Correct 344 ms 74068 KB Output is correct
20 Correct 402 ms 72436 KB Output is correct

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 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 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 1 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Incorrect 0 ms 348 KB Output isn't correct
21 Halted 0 ms 0 KB -