Submission #1010158

#	Time	Username	Problem	Language	Result	Execution time	Memory
1010158		Unforgettablepl	Event Hopping 2 (JOI21_event2)	C++17	7 / 100	30 ms	6096 KiB

event2

#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';
}

• Subtask 1: 7 / 7
• Subtask 2: 0 / 1
• Subtask 3: 0 / 31
• Subtask 4: 0 / 61