Submission #1281427

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281427		whtth	Fire (BOI24_fire)	C++20	100 / 100	97 ms	21352 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int n, m, e[200001], s[200001], ma=0, ans=1e9, f[20][200001], tree[530001];
pair<int, int> a[200001];
int process(int u, int v){
    if(a[v].second>a[u].second)return v;
    return u;
}
void build(int id, int l, int r){
    if(l==r){
        tree[id]=l;
        return;
    }
    int mid=(l+r)/2;
    build(id*2, l, mid);
    build(id*2+1, mid+1, r);
    tree[id]=process(tree[id*2], tree[id*2+1]);
}
int get(int id, int l, int r, int L, int R){
    if(l>R || L>r)return 0;
    if(L<=l and r<=R)return tree[id];
    int mid=(l+r)/2;
    return process(get(id*2, l, mid, L, R), get(id*2+1, mid+1, r, L, R));
}
int main(){
    ios::sync_with_stdio(0);cin.tie(nullptr);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>s[i]>>e[i];
        if(s[i]>e[i])e[i]+=m;
        a[i]={s[i], e[i]};
    }
    sort(a+1, a+n+1);
    build(1, 1, n);
    for(int i=1;i<=n;i++){
        auto[l, r]=a[i];
        pair<int, int> nxt={r+1, 0};
        int j=lower_bound(a+1, a+n+1, nxt)-a;
        f[0][i]=get(1, 1, n, 1, j-1);
    }
    for(int i=1;i<=19;i++){
        for(int j=1;j<=n;j++){
            f[i][j]=f[i-1][f[i-1][j]];
        }
    }
    for(int i=1;i<=n;i++){
        int l=a[i].first, now=i, cnt=1;
        for(int j=19;j>=0;j--){
            int r=a[f[j][now]].second;
            if(r!=0 and r-l+1<=m){
                now=f[j][now];
                cnt+=(1<<j);
            }
        }
        int r=a[f[0][now]].second;
        if(r-l+1>m){
            ans=min(ans, cnt+1);
        }
    }
    if(ans==1e9)cout<<-1;
    else cout<<ans;
    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