Submission #1065984

#	Time	Username	Problem	Language	Result	Execution time	Memory
1065984		Boomyday	Fire (BOI24_fire)	C++17	100 / 100	1408 ms	87260 KiB

Main

//
// Created by adavy on 8/19/2024.
//
#include <bits/stdc++.h>
//#pragma GCC optimize("O3")

using namespace std;

using ll = long long;

#define f first
#define s second


int main(){
    ll N,M; cin >> N >> M;
    ll B = 25;
    set<ll> coords;
    vector<ll> s(N),e(N);
    for(int i=0;i<N;++i) {
        cin >> s[i] >> e[i];
        coords.insert(s[i]);
        coords.insert(e[i]);
    }
    vector<ll> coords_v(coords.begin(),coords.end());
    map<ll,ll> coords_ind;
    for(int i=0;i<coords_v.size();++i){
        coords_ind[coords_v[i]] = i;
    }
    for(int i=0;i<N;++i){
        s[i] = coords_ind[s[i]];
        e[i] = coords_ind[e[i]];
    }
    M = coords.size();
    for(int i=0;i<N;++i){
        if (e[i] < s[i]){
            e[i] += M;
        }
    }
    // output starts and ends
    vector<vector<int>> best_next(N, vector<int>(B));
    vector<pair<pair<int,int>,int>> sweep; // time, {0 open 1 close}, number
    for(int i=0;i<N;++i){
        sweep.push_back({{s[i],0},i});
        sweep.push_back({{e[i],1},i});
    }
    sort(sweep.begin(),sweep.end());
    multiset<pair<int,int>,greater<pair<int,int>>> open; // end, number
    for(auto&[state,ind]:sweep){
        if (state.s == 0){
            open.insert({e[ind],ind});
        }
        else {
            best_next[ind][0] = open.begin()->s;
            open.erase({e[ind],ind});
        }
    }
    for(int j=1;j<B;++j){
        for(int i=0;i<N;++i){
            best_next[i][j] = best_next[best_next[i][j-1]][j-1];
        }
    }
    ll lo = 0, hi = 3*N;
    while (lo<hi){
        bool is_good = false;
        ll mid = (lo+hi)/2;
        for(int i=0;i<N;++i){
            ll cur = i;
            for(int j=0;j<B;++j){
                if (mid & (1<<j)){
                    cur = best_next[cur][j];
                }
            }
            if (e[cur] - s[i] >= M){
                //cout << i << " " << cur << " " << mid << endl;
                is_good = true;
                break;
            }
        }
        if (is_good){
            hi = mid;
        }
        else {
            lo = mid+1;
        }
    }
    if (hi == 3*N){
        cout << -1 << endl;
    }
    else {
        cout << hi+1 << endl;
    }
    // output best nexts



}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:27:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for(int i=0;i<coords_v.size();++i){
      |                 ~^~~~~~~~~~~~~~~~

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