//#pragma GCC optimize("Ofast,unroll-loops,O3")
//#pragma GCC optimize("avx,avx2,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,fma,tune=native")
#include<bits/stdc++.h>
//#include<bits/extc++.h>
//#pragma pack(1)
#define fast ios::sync_with_stdio(0); cin.tie(0);
#define int long long
#define pii pair<int,int>
#define x first
#define y second
#define N 100015
using namespace std;
//using namespace __gnu_pbds;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
//typedef tree<int, null_type,less_equal<int>, rb_tree_tag,tree_order_statistics_node_update> order_multiset;
//typedef tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update> order_set;
struct lisan{
vector<int>vt;
void in(int x){ vt.push_back(x); }
void build(){
sort(vt.begin(),vt.end());
vt.resize(unique(vt.begin(),vt.end())-vt.begin());
}
int find(int x){ return upper_bound(vt.begin(),vt.end(),x)-vt.begin(); }
}uni;
int n,k;
pii seg[N];
vector<int>ans;
bool run(vector<int>have,int need){
vector<int>all[2*n+5];
vector<int>dp(2*n+5,0LL);
for (auto i:have){
all[seg[i].x].push_back(seg[i].y);
}
for (int i=2*n+1;i>=0;i--){
dp[i]=max(dp[i],dp[i+1]);
for (auto j:all[i])
dp[i]=max(dp[i],dp[j]+1);
}
return dp[0]>=need;
}
bool touch(int a,int b){
if (seg[a].x>seg[b].x) swap(a,b);
if (seg[a].y>seg[b].x) return 1;
return 0;
}
void solve(vector<int>have,int need){
if (need==0) return;
if (have.empty()) return;
vector<int>last;
for (int i=1;i<have.size();i++){
if (!touch(have[0],have[i]))
last.push_back(have[i]);
}
bool flag=run(last,need-1);
if (flag){
ans.push_back(have[0]);
solve(last,need-1);
}
else {
last.clear();
for (int i=1;i<have.size();i++)
last.push_back(have[i]);
solve(last,need);
}
}
signed main(){
fast
cin>>n>>k;
for (int i=1;i<=n;i++){
cin>>seg[i].x>>seg[i].y;
uni.in(seg[i].x); uni.in(seg[i].y);
}
uni.build();
for (int i=1;i<=n;i++){
seg[i].x=uni.find(seg[i].x);
seg[i].y=uni.find(seg[i].y);
}
vector<int>have;
for (int i=1;i<=n;i++)
have.push_back(i);
solve(have,k);
if (ans.size()!=k) cout<<"-1\n";
else {
for (auto i:ans)
cout<<i<<'\n';
}
}
Compilation message
event2.cpp: In function 'void solve(std::vector<long long int>, long long int)':
event2.cpp:51:16: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
51 | for (int i=1;i<have.size();i++){
| ~^~~~~~~~~~~~
event2.cpp:62:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
62 | for (int i=1;i<have.size();i++)
| ~^~~~~~~~~~~~
event2.cpp: In function 'int main()':
event2.cpp:83:19: warning: comparison of integer expressions of different signedness: 'std::vector<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
83 | if (ans.size()!=k) cout<<"-1\n";
| ~~~~~~~~~~^~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Runtime error |
2154 ms |
524288 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
332 KB |
Output is correct |
4 |
Correct |
1 ms |
332 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
332 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
384 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
212 KB |
Output is correct |
23 |
Correct |
1 ms |
332 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
212 KB |
Output is correct |
28 |
Correct |
23 ms |
4692 KB |
Output is correct |
29 |
Correct |
15 ms |
2816 KB |
Output is correct |
30 |
Correct |
9 ms |
1628 KB |
Output is correct |
31 |
Correct |
4 ms |
792 KB |
Output is correct |
32 |
Correct |
3 ms |
724 KB |
Output is correct |
33 |
Correct |
335 ms |
88576 KB |
Output is correct |
34 |
Correct |
280 ms |
88524 KB |
Output is correct |
35 |
Correct |
414 ms |
86164 KB |
Output is correct |
36 |
Correct |
424 ms |
84780 KB |
Output is correct |
37 |
Correct |
337 ms |
65204 KB |
Output is correct |
38 |
Correct |
468 ms |
88808 KB |
Output is correct |
39 |
Correct |
358 ms |
69492 KB |
Output is correct |
40 |
Correct |
332 ms |
67876 KB |
Output is correct |
41 |
Correct |
339 ms |
65920 KB |
Output is correct |
42 |
Correct |
451 ms |
88660 KB |
Output is correct |
43 |
Correct |
160 ms |
28196 KB |
Output is correct |
44 |
Correct |
129 ms |
21064 KB |
Output is correct |
45 |
Correct |
107 ms |
19532 KB |
Output is correct |
46 |
Correct |
460 ms |
88700 KB |
Output is correct |
47 |
Correct |
70 ms |
13224 KB |
Output is correct |
48 |
Correct |
34 ms |
5396 KB |
Output is correct |
49 |
Correct |
16 ms |
3192 KB |
Output is correct |
50 |
Correct |
447 ms |
88580 KB |
Output is correct |
51 |
Correct |
73 ms |
14416 KB |
Output is correct |
52 |
Correct |
43 ms |
7296 KB |
Output is correct |
53 |
Correct |
5 ms |
1108 KB |
Output is correct |
54 |
Correct |
415 ms |
87724 KB |
Output is correct |
55 |
Correct |
357 ms |
88756 KB |
Output is correct |
56 |
Correct |
362 ms |
88856 KB |
Output is correct |
57 |
Correct |
353 ms |
87824 KB |
Output is correct |
58 |
Correct |
349 ms |
87772 KB |
Output is correct |
59 |
Correct |
390 ms |
88140 KB |
Output is correct |
60 |
Correct |
351 ms |
87816 KB |
Output is correct |
61 |
Correct |
377 ms |
87744 KB |
Output is correct |
62 |
Correct |
343 ms |
87036 KB |
Output is correct |
63 |
Correct |
325 ms |
84628 KB |
Output is correct |
64 |
Correct |
356 ms |
88652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Runtime error |
2154 ms |
524288 KB |
Execution killed with signal 9 |
5 |
Halted |
0 ms |
0 KB |
- |