Submission #1013877

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013877		hengliao	Fire (BOI24_fire)	C++17	100 / 100	224 ms	106068 KiB

Main

#include<bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;

#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;

const ll mxN=2e5+5;
const ll LOG=21;
const ll inf=1e18;

ll pw[LOG];

struct seg{
    ll s, e, id;
    seg *up[LOG];

    bool operator< (const seg &tar) const{
        if(s!=tar.s){
            return s<tar.s;
        }
        return e<tar.e;
    }

    ll bs(ll tar){
        ll re=0;
        if(e>=tar){
            return 1;
        }
        seg *cur=this;
        for(ll i=LOG-1;i>=0;i--){
            if(cur->up[i]->e<tar){
                re+=pw[i];
                cur=cur->up[i];
            }
        }
        return re+2;
    }
};

ll n, m;
vector<seg> a;
vll con;

ll getidx(ll tar){
    return lower_bound(con.begin(), con.end(), tar)-con.begin();
}

void solve(){
	cin>>n>>m;
    //a.resize(n);
    vector<pll> tep(n);
    for(ll i=0;i<n;i++){
        cin>>tep[i].F>>tep[i].S;
    }
    for(ll i=0;i<n;i++){
        if(tep[i].F>tep[i].S){
            tep[i].S+=m;
        }
    }
    sort(tep.begin(), tep.end());
    //a.erase(unique(a.begin(), a.end()), a.end());
    pll pre={0, 0};
    ll cnt=0;
    for(ll i=0;i<n;i++){
        if(tep[i].F!=pre.F || tep[i].S!=pre.S){
            a.pb({tep[i].F, tep[i].S, cnt});
            cnt++;
        }
        pre.F=tep[i].F;
        pre.S=tep[i].S;
    }
    n=a.size();
    for(ll i=0;i<n;i++){
        seg tep={a[i].s+m, a[i].e+m, cnt};
        cnt++;
        tep.e=min(tep.e, 2*m);
        a.pb(tep);
    }
    for(auto &cur:a){
        con.pb(cur.s);
        con.pb(cur.e);
    }
    sort(con.begin(), con.end());
    con.erase(unique(con.begin(), con.end()), con.end());
    ll pt=0;
    seg *mx=new seg();
    mx->s=0;
    mx->e=0;
    vector<seg*> bst(con.size());
    for(ll i=0;i<con.size();i++){
        ll it=con[i];
        if(it<a[0].s){
            assert(0);
            continue;
        }
        while(pt<a.size() && a[pt].s<=it){
            if(a[pt].e>(mx->e)){
                mx=&a[pt];
            }
            pt++;
        }
        assert(mx->e!=0);
        bst[i]=mx;
    }
    for(ll i=0;i<a.size();i++){
        ll id=getidx(a[i].e);
        a[i].up[0]=bst[id];
        //cout<<i<<' '<<0<<' '<<a[i].up[0]->id<<'\n';
    }
    /*for(ll i=0;i<a.size();i++){
        cout<<a[i].s<<' '<<a[i].e<<'\n';
    }*/
    for(ll j=1;j<LOG;j++){
        for(ll i=0;i<a.size();i++){
            a[i].up[j]=a[i].up[j-1]->up[j-1];
            //cout<<i<<' '<<j<<' '<<a[i].up[j]->id<<'\n';
        }
    }
    bool good=0;
    for(ll i=0;i<n;i++){
        if(a[i].up[LOG-1]->e>=a[i].s+m){
            good=1;
        }
    }
    if(!good){
        cout<<-1<<'\n';
        return;
    }
    ll ans=inf;
    for(ll i=0;i<n;i++){
        ll re=a[i].bs(a[i].s+m);
        //cout<<a[i].s<<' '<<a[i].e<<' '<<re<<'\n';
        ans=min(ans, re);
    }
    cout<<ans<<'\n';
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

    pw[0]=1;
    for(ll i=1;i<LOG;i++){
        pw[i]=pw[i-1]*2;
    }

	solve();
	return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void solve()':
Main.cpp:96:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |     for(ll i=0;i<con.size();i++){
      |                ~^~~~~~~~~~~
Main.cpp:102:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |         while(pt<a.size() && a[pt].s<=it){
      |               ~~^~~~~~~~~
Main.cpp:111:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  111 |     for(ll i=0;i<a.size();i++){
      |                ~^~~~~~~~~
Main.cpp:120:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<seg>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |         for(ll i=0;i<a.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