oj.uz

Submission #1034360

# Submission time Handle Problem Language Result Execution time Memory
1034360 2024-07-25T12:37:45 Z istlemin Fire (BOI24_fire) C++17
34 / 100
 693 ms 90728 KB 
#include<bits/stdc++.h>

#pragma GCC optimize ("Ofast")

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){
            best.emplace(t,idx);
            if(sz(best)){
                nextInterval[t] = max(nextInterval[t], prev(best.end())->first);
            }
        } 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 {
            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 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 7 ms 2508 KB Output is correct
16 Correct 8 ms 2260 KB Output is correct
17 Correct 9 ms 2388 KB Output is correct
18 Correct 8 ms 2516 KB Output is correct
19 Correct 6 ms 2516 KB Output is correct
20 Correct 296 ms 53644 KB Output is correct
21 Correct 385 ms 89284 KB Output is correct
22 Correct 346 ms 89480 KB Output is correct
23 Correct 447 ms 81912 KB Output is correct
24 Correct 453 ms 86512 KB Output is correct
25 Correct 693 ms 82812 KB Output is correct
26 Correct 509 ms 87372 KB Output is correct
27 Correct 515 ms 82856 KB Output is correct
28 Correct 408 ms 89116 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 452 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 416 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 11 ms 2512 KB Output is correct
13 Correct 12 ms 2260 KB Output is correct
14 Correct 8 ms 2636 KB Output is correct
15 Correct 317 ms 53696 KB Output is correct
16 Correct 502 ms 81936 KB Output is correct
17 Correct 304 ms 89468 KB Output is correct
18 Correct 358 ms 90728 KB Output is correct
19 Correct 344 ms 85080 KB Output is correct
20 Correct 434 ms 87640 KB Output is correct

Subtask #6
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB Output isn't correct
4 Halted 0 ms 0 KB -