Submission #1141625

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141625		SyedSohaib_123	Fire (BOI24_fire)	C++20	31 / 100	2095 ms	964 KiB

Main

#include <bits/stdc++.h>

using namespace std;

#define append push_back
#define int long long

const int N=2e5+10,LG=17;
int mod=998244353;

int tree[N<<3];

void upd(int l,int r,int s,int a,int b){
    if(r<a or l>a) return;
    if(l==r){
        tree[s]=min(tree[s],b);
        return;
    }
    int m=(l+r)>>1;
    upd(l,m,s*2,a,b);
    upd(m+1,r,s*2+1,a,b);
    tree[s]=min(tree[s*2],tree[s*2+1]);
}

int get(int l,int r,int s,int a,int b){
    if(r<a or l>b) return 1e18;
    if(a<=l and r<=b) return tree[s];
    int m=(l+r)>>1;
    return min(get(l,m,s*2,a,b),get(m+1,r,s*2+1,a,b));
}

void solve(int tst){
    int n,m;
    cin>>n>>m;
    vector<pair<int,int>>v={{0,0}};
    for(int i=1;i<=n;i++){
        int a,b;
        cin>>a>>b;
        v.append({a,b});
    }
    vector<pair<int,int>>t;
    for(int i=1;i<=n;i++){
        t.append({v[i].first,i});
        t.append({v[i].second,i+n});
    }
    t.append({0,0});
    t.append({m,1e18});
    sort(t.begin(),t.end());
    int cnt=1;
    for(int i=1;i<t.size();i++){
        if(t[i].first!=t[i-1].first) cnt++;
        int j=t[i].second;
        if(j and j<=n){
            v[j].first=cnt;
        }
        if(j>n and j!=1e18){
            v[j-n].second=cnt;
        }
    }
    sort(v.begin(),v.end());
    int ans=1e18;
    for(int X=1;X<=n;X++){
        for(int i=1;i<=cnt*4;i++) tree[i]=1e18;
        upd(1,cnt,1,v[X].first,0);
        for(int i=X;i<=n;i++){
            int x=1e18;
            if(v[i].first<v[i].second) x=get(1,cnt,1,v[i].first,v[i].second);
            else x=min(get(1,cnt,1,v[i].first,cnt),get(1,cnt,1,1,min(v[X].first-1,v[i].second)));
            upd(1,cnt,1,v[i].second,x+1);
            if(v[i].second<v[i].first and v[i].second>=v[X].first) ans=min(ans,x+1);
        }
        for(int i=1;i<X;i++){
            int x=1e18;
            if(v[i].first<v[i].second) x=get(1,cnt,1,v[i].first,v[i].second);
            else x=min(get(1,cnt,1,v[i].first,cnt),get(1,cnt,1,1,min(v[X].first-1,v[i].second)));
            upd(1,cnt,1,v[i].second,x+1);
            if(v[i].second<v[i].first and v[i].second>=v[X].first) ans=min(ans,x+1);
        }
    }
    if(ans==1e18) ans=-1;
    cout<<ans<<endl;
}

signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; i++) {
        solve(i);
    }
}

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