Submission #1203249

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203249		AlgorithmWarrior	Fire (BOI24_fire)	C++20	100 / 100	169 ms	20964 KiB

Main

#include <bits/stdc++.h>

using namespace std;

int const MAX=2e5+5;
int n,m;
struct interval{
    int l,r;
}v[MAX];

void read(){
    cin>>n>>m;
    int i;
    for(i=1;i<=n;++i){
        cin>>v[i].l>>v[i].r;
        if(v[i].l>v[i].r)
            v[i].r+=m;
    }
}

struct event{
    int ind;
    bool tip; /// 1 0
    bool operator<(event ot){
        int nr1=((tip)?v[ind].l:v[ind].r);
        int nr2=((ot.tip)?v[ot.ind].l:v[ot.ind].r);
        if(nr1!=nr2)
            return nr1<nr2;
        return tip>ot.tip;
    }
}ev[2*MAX];

int const LOG=20;
int rmq[MAX][LOG];

void put_fathers(){
    int i;
    for(i=1;i<=n;++i){
        ev[2*i-1]={i,1};
        ev[2*i]={i,0};
    }
    sort(ev+1,ev+2*n+1);
    int best=0;
    for(i=1;i<=2*n;++i){
        int ind=ev[i].ind;
        if(ev[i].tip){
            if(v[best].r<v[ind].r)
                best=ind;
        }
        else
            rmq[ind][0]=best;
    }
}

void build_rmq(){
    int i,j;
    for(j=1;j<LOG;++j)
        for(i=1;i<=n;++i)
            rmq[i][j]=rmq[rmq[i][j-1]][j-1];
}

int const INF=1e9;

int bin_lift(int nod){
    int capat=v[nod].l+m;
    int anc=0;
    int bit;
    for(bit=LOG-1;bit>=0;--bit)
        if(v[rmq[nod][bit]].r<capat){
            anc+=(1<<bit);
            nod=rmq[nod][bit];
        }
    nod=rmq[nod][0];
    if(v[nod].r>=capat)
        return anc+2;
    return INF;
}

void minself(int& x,int val){
    if(x>val)
        x=val;
}

int solve(){
    int i;
    int rasp=INF;
    for(i=1;i<=n;++i)
        minself(rasp,bin_lift(i));
    if(rasp<INF)
        return rasp;
    return -1;
}

void write(int ans){
    cout<<ans;
}

int main()
{
    read();
    put_fathers();
    build_rmq();
    write(solve());
    return 0;
}

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