Submission #1281417

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281417		whtth	Fire (BOI24_fire)	C++20	0 / 100	46 ms	6596 KiB

Main

#include<bits/stdc++.h>
using namespace std;
int n, m, e[200001], s[200001], ma=0, ans=1e9;
vector<pair<int, int>> now;
bool cmp(pair<int, int> a, pair<int, int> b){
    if(a.first==b.first)return a.second>b.second;
    return a.first<b.first;
}
vector<pair<int, int>> chosenone;
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];
        ma=max(ma, e[i]);
        if(s[i]<=e[i])now.push_back({s[i], e[i]});
    }
    sort(now.begin(), now.end(), cmp);
    int cnt=2;
    int nxt=now[0].second, R=now[0].second, L=now[0].first;
    chosenone.push_back({L, R});
    for(int i=1;i<now.size();i++){
        if(nxt+1<now[i].first){
            cnt++;
            nxt=R;
            chosenone.push_back({L, R});
            if(R==ma)break;
        }
        if(R<now[i].second){
            R=now[i].second;
            L=now[i].first;
        }
    }
    if(chosenone.back().second!=ma)chosenone.push_back({L, R});
    chosenone.erase(unique(chosenone.begin(), chosenone.end()), chosenone.end());
    for(int i=1;i<chosenone.size();i++){
        if(chosenone[i].first>chosenone[i-1].second){
            cout<<-1;
            return 0;
        }
    }
    //for(auto[u, v] : chosenone)cout<<u<<" "<<v<<"\n";
    for(int i=1;i<=n;i++){
        if(s[i]>e[i]){
            int l=0, r=chosenone.size()-1, mid, vtst=-1;
            while(l<=r){
                mid=(l+r)/2;
                if(chosenone[mid].second>=s[i]){
                    vtst=mid;
                    r=mid-1;
                }
                else l=mid+1;
            }
            l=0, r=chosenone.size()-1;
            int vten=-1;
            while(l<=r){
                mid=(l+r)/2;
                if(chosenone[mid].first<=e[i]){
                    vten=mid;
                    l=mid+1;
                }
                else r=mid-1;
            }
            if(vten!=-1 and vtst!=-1){
                vtst++;
                ans=min(ans, int(chosenone.size()-(chosenone.size()-vtst)-vten)+1);
            }
        }
    }
    if(ans==1e9)cout<<-1;
    else cout<<ans;
    return 0;
}

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