Submission #1286905

#	Time	Username	Problem	Language	Result	Execution time	Memory
1286905		HiepVu217	Fire (BOI24_fire)	C++20	100 / 100	100 ms	21276 KiB

Main

#include<bits/stdc++.h>

using namespace std;

pair<int,int>p[200005];
int n,m;
int mer(int a,int b){
    return(p[a].second<p[b].second?b:a);
}
int st[800005];
void build(int id,int l,int r){
    if(l==r){
        st[id]=r;
        return;
    }
    int mid=l+r>>1;
    build(id*2,l,mid);build(id*2+1,mid+1,r);
    st[id]=mer(st[id*2],st[2*id+1]);
}

int get(int id,int l,int r,int u,int v){
    if(l>v or r<r)return 0;
    if(u<=l and r<=v)return st[id];
    int mid=l+r>>1;
    return mer(get(id*2,l,mid,u,v),get(id*2+1,mid+1,r,u,v));
}
int up[200005][22];

int32_t main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    if(fopen("fire.inp","r")){freopen("fire.inp","r",stdin);freopen("fire.out","w",stdout);}
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>p[i].first>>p[i].second;
        if(p[i].first>p[i].second)p[i].second+=m;
    }
    sort(p+1,p+1+n);
    build(1,1,n);

    for(int i=1;i<=n;++i){
        int l=p[i].first,r=p[i].second;
        pair<int,int>ct={r+1,0};
        auto vt=upper_bound(p+1,p+1+n,ct)-p;
        up[i][0]=get(1,1,n,1,vt-1);
    }

    for(int i=n;i;--i){
        for(int j=1;j<=20;++j)up[i][j]=up[up[i][j-1]][j-1];
    }
    int ans=1e9;

    for(int i=1;i<=n;++i){
        int l=p[i].first,r=p[i].second,u=i,re=1;

        for(int j=20;j>=0;--j){
            if(p[up[u][j]].second-l+1<=m){
                u=up[u][j];re+=1<<j;
            }
        }
        u=up[u][0];
        if(p[u].second-l+1>m)ans=min(ans,re);
    }
    if(ans==1e9)ans=-2;
    cout<<ans+1;
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:31:38: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     if(fopen("fire.inp","r")){freopen("fire.inp","r",stdin);freopen("fire.out","w",stdout);}
      |                               ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Main.cpp:31:68: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |     if(fopen("fire.inp","r")){freopen("fire.inp","r",stdin);freopen("fire.out","w",stdout);}
      |                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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