제출 #1010158

#제출 시각아이디문제언어결과실행 시간메모리
1010158UnforgettableplEvent Hopping 2 (JOI21_event2)C++17
7 / 100
30 ms6096 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long


int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,k;
    cin >> n >> k;
    vector<pair<int,int>> ranges(n);
    vector<int> maxchoose(n+1);
    for(auto&[a,b]:ranges)cin>>a>>b;
    int last = 1e10;
    for(int i=n-1;i>=0;i--){
        if(ranges[i].second<=last){
            last = ranges[i].first;
            maxchoose[i]=maxchoose[i+1]+1;
        } else maxchoose[i]=maxchoose[i+1];
    }
    if(maxchoose[0]<k){
        cout << "-1\n";
        return 0;
    }
    vector<int> ans;
    int curr = 0;
    for(int i=0;i<n;i++){
        if(curr==k)break;
        int idx = lower_bound(ranges.begin(),ranges.end(),make_pair(ranges[i].second,0ll))-ranges.begin();
        if(curr+1+maxchoose[idx]>=k){ans.emplace_back(i);i=idx-1;curr++;}
    }
    for(int&i:ans)cout<<++i<<'\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...