#include <bits/stdc++.h>
using namespace std;
int N;
int K;
int l[100100];
int r[100100];
vector<int> ropt;
vector<int> lopt;
int ft[200100];
int seten[100100];
vector<int> de;
vector<int> taken;
int query(int i){
int v = 0;
while(i != 0){
v = max(v,ft[i]);
i -= (i&(-i));
}
return v;
}
void update(int i, int k){
while(i <= N * 2){
ft[i] = max(ft[i],k);
i += (i&(-i));
}
}
int main(){
scanf(" %d",&N);
scanf(" %d",&K);
vector<pair<int,int>> v;
for(int i = 0; i < N; i++){
scanf(" %d",&l[i]);
scanf(" %d",&r[i]);
de.push_back(l[i]);
de.push_back(r[i]);
}
sort(de.begin(),de.end());
de.resize(unique(de.begin(), de.end() ) - de.begin() );
for(int i = 0; i < N; i++){
l[i] = lower_bound(de.begin(), de.end(), l[i]) - de.begin() + 1;
r[i] = lower_bound(de.begin(),de.end(), r[i]) - de.begin() + 1;
//printf("%d %d\n",l[i],r[i]);
v.push_back({r[i],l[i]});
}
sort(v.begin(),v.end());
for(int i = 1 ; i <= N * 2; i++) ft[i] = 0;
int cont = 0;
for(int i = 0; i < N; i++){
if(query(v[i].second) + 1 > cont){
cont++;
ropt.push_back(v[i].first);
}
update(v[i].first, query(v[i].second) + 1);
}
v.clear();
for(int i = 0; i < N; i++){
v.push_back({l[i],r[i]});
}
sort(v.begin(),v.end());
for(int i = 1; i <= N * 2; i++) ft[i] = 0;
cont = 0;
for(int i = N - 1; i >= 0; i--){
//printf("%d\n",query(N * 2 + 1 - v[i].second));
if(query(N * 2 + 1 - v[i].second ) + 1 > cont){
cont++;
lopt.push_back(v[i].first);
}
update(N * 2 + 1 - v[i].first, query(N * 2 + 1 - v[i].second) + 1);
}
reverse(lopt.begin(),lopt.end());
for(int i = 0; i <= cont; i++){
seten[i] = -1;
//printf("%d %d\n",lopt[i],ropt[i]);
}
if(cont < K){
printf("-1");
return 0;
}
vector<int> taken;
for(int i = 0; i < N && K > 0; i++){
int it = upper_bound(ropt.begin(),ropt.end(),r[i]) - ropt.begin() - 1;
int bit = lower_bound(lopt.begin(),lopt.end(),l[i]) - lopt.begin();
if(cont - (it - bit + 1) < K - 1) continue;
bool die = false;
for(int j : taken){
if(r[j] <= l[i] || r[i] <= l[j]) continue;
else die = true;
}
if(die) continue;
taken.push_back(i);
for(int i = bit; i <= it; i++){
seten[i] = 0;
}
cont -= (it - bit + 1);
K--;
}
for(int i : taken) printf("%d\n",i+1);
}
Compilation message (stderr)
event2.cpp: In function 'int main()':
event2.cpp:34:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | scanf(" %d",&N);
| ~~~~~^~~~~~~~~~
event2.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
35 | scanf(" %d",&K);
| ~~~~~^~~~~~~~~~
event2.cpp:40:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf(" %d",&l[i]);
| ~~~~~^~~~~~~~~~~~~
event2.cpp:41:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
41 | scanf(" %d",&r[i]);
| ~~~~~^~~~~~~~~~~~~
# | 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... |