#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fi first
#define se second
const int N = 2e5+5;
const int lg = 18;
int n,k,st[N][lg],nxt[N];
pii a[N];
map<int,int>mp;
multiset<pii>s;
void build(){
for(int i = 1; i <= mp.size(); i++){
st[i][0] = nxt[i];
if(nxt[i] == 1e9) st[i][0] = 0;
}
for(int j = 1; j < lg; j++){
for(int i = 1; i <= mp.size(); i++) st[i][j] = st[st[i][j-1]][j-1];
}
}
int jump(int u, int v){
int sum = 0;
for(int i = lg-1; i >= 0; i--){
if(st[u][i] > u && st[u][i] <= v){
sum += (1 << i);
u = st[u][i];
}
}
return sum;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> n >> k;
for(int i = 1; i <= n; i++){
cin >> a[i].fi >> a[i].se;
mp[a[i].fi]++;
mp[a[i].se]++;
}
int cnt = 0;
for(auto it: mp) mp[it.fi] = ++cnt;
for(int i = 1; i <= n; i++){
a[i].fi = mp[a[i].fi];
a[i].se = mp[a[i].se];
}
for(int i = 1; i <= mp.size(); i++) nxt[i] = 1e9;
for(int i = 1; i <= n; i++) nxt[a[i].fi] = min(nxt[a[i].fi],a[i].se);
for(int i = mp.size()-1; i >= 1; i--) nxt[i] = min(nxt[i],nxt[i+1]);
build();
s.insert({1,1});
s.insert({mp.size(),mp.size()});
int cur = jump(1,mp.size());
if(cur < k){
cout << -1;
return 0;
}
for(int i = 1; i <= n; i++){
auto[x,y] = a[i];
auto reze = s.lower_bound({y,-1});
auto[x1,x2] = *reze;
--reze;
auto[y2,y1] = *reze;
if(x < y1) continue;
int nw = cur+1-jump(y1,x1)+jump(y1,x)+jump(y,x1);
if(nw >= k){
cur = nw;
cout << i << "\n";
s.insert({x,y});
}
if(s.size() == k+2) return 0;
}
}
# | 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... |