#include <bits/stdc++.h>
using namespace std;
pair<int,int> arr[100005],srt[100005];
vector<pair<pair<int,int>,int> > mono;
int n,k;
int nxt[20][100005];
int nombor(int l, int r){
int ind=lower_bound(mono.begin(),mono.end(),make_pair(make_pair(l,-1),-1))-mono.begin();
if(ind==(int)mono.size()) return 0;
int cur=mono[ind].second;
if(srt[cur].second>r) return 0;
int ret=1;
for(int i=19; i>=0; i--){
if(nxt[i][cur]==-1||srt[nxt[i][cur]].second>r) continue;
ret+=(1<<i);
cur=nxt[i][cur];
}
return ret;
}
int32_t main(){
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> k;
for(int i=0; i<n; i++){
cin >> arr[i].first >> arr[i].second;
srt[i]=arr[i];
}
sort(srt,srt+n);
for(int i=0; i<n; i++){
if(i&&srt[i].first==srt[i-1].first) continue;
while(!mono.empty()&&mono.back().first.second>=srt[i].second) mono.pop_back();
mono.push_back({srt[i],i});
}
for(int i=0; i<n; i++){
int ind=lower_bound(mono.begin(),mono.end(),make_pair(make_pair(srt[i].second,-1),-1))-mono.begin();
if(ind==(int)mono.size()) nxt[0][i]=-1;
else nxt[0][i]=mono[ind].second;
}
for(int i=1; i<20; i++){
for(int j=0; j<n; j++){
if(nxt[i-1][j]==-1) continue;
nxt[i][j]=nxt[i-1][nxt[i-1][j]];
}
}
set<pair<int,int> > ran;
set<pair<int,int> >::iterator it;
ran.insert({0,1'000'000'005});
vector<int> ans;
int can=nombor(0,1'000'000'005);
for(int i=0; i<n; i++){
it=ran.upper_bound(make_pair(arr[i].first+1,-1));
if(it==ran.begin()) continue;
it--;
pair<int,int> big=*it;
if(big.first>arr[i].first||big.second<arr[i].second) continue;
int net=nombor(big.first,arr[i].first)+nombor(arr[i].second,big.second)+1-nombor(big.first,big.second);
if(can+net>=k){
can+=net;
ran.erase(big);
ran.insert({big.first,arr[i].first});
ran.insert({arr[i].second,big.second});
ans.push_back(i+1);
}
}
if((int)ans.size()<k) cout << -1;
else for(int i=0; i<k; i++) cout << ans[i] << '\n';
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |