//#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,dp(2*N+5,0LL),all[2*N+5];
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);
all[seg[i].x].push_back(seg[i].y);
}
for (int i=2*N+3;i>=0;i--){
dp[i]=max(dp[i],dp[i+1]);
for (auto j:all[i])
dp[i]=max(dp[i],dp[j]+1);
}
int r=0,need=k;
for (int i=1;i<=n;i++){
if (seg[i].x>=r&&dp[seg[i].y]>=need-1){
ans.push_back(i);
r=seg[i].y;
need--;
}
if (need==0) break;
}
if (need==0){
for (auto i:ans)
cout<<i<<'\n';
}
else cout<<"-1\n";
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6484 KB |
Output is correct |
2 |
Correct |
5 ms |
6484 KB |
Output is correct |
3 |
Correct |
5 ms |
6484 KB |
Output is correct |
4 |
Correct |
54 ms |
16964 KB |
Output is correct |
5 |
Correct |
75 ms |
17024 KB |
Output is correct |
6 |
Correct |
55 ms |
16948 KB |
Output is correct |
7 |
Correct |
81 ms |
16804 KB |
Output is correct |
8 |
Correct |
56 ms |
17008 KB |
Output is correct |
9 |
Correct |
58 ms |
17012 KB |
Output is correct |
10 |
Correct |
58 ms |
16968 KB |
Output is correct |
11 |
Correct |
52 ms |
16844 KB |
Output is correct |
12 |
Correct |
58 ms |
16012 KB |
Output is correct |
13 |
Correct |
58 ms |
15956 KB |
Output is correct |
14 |
Correct |
55 ms |
15940 KB |
Output is correct |
15 |
Correct |
61 ms |
15812 KB |
Output is correct |
16 |
Correct |
51 ms |
15088 KB |
Output is correct |
17 |
Correct |
54 ms |
15052 KB |
Output is correct |
18 |
Correct |
55 ms |
14992 KB |
Output is correct |
19 |
Correct |
50 ms |
14736 KB |
Output is correct |
20 |
Correct |
53 ms |
14752 KB |
Output is correct |
21 |
Correct |
53 ms |
14800 KB |
Output is correct |
22 |
Correct |
56 ms |
14716 KB |
Output is correct |
23 |
Correct |
69 ms |
14736 KB |
Output is correct |
24 |
Correct |
56 ms |
14768 KB |
Output is correct |
25 |
Correct |
63 ms |
14708 KB |
Output is correct |
26 |
Correct |
72 ms |
14736 KB |
Output is correct |
27 |
Correct |
65 ms |
14776 KB |
Output is correct |
28 |
Correct |
51 ms |
14736 KB |
Output is correct |
29 |
Correct |
69 ms |
14744 KB |
Output is correct |
30 |
Correct |
53 ms |
14760 KB |
Output is correct |
31 |
Correct |
52 ms |
14768 KB |
Output is correct |
32 |
Correct |
57 ms |
14696 KB |
Output is correct |
33 |
Correct |
65 ms |
14796 KB |
Output is correct |
34 |
Correct |
53 ms |
15668 KB |
Output is correct |
35 |
Correct |
50 ms |
15244 KB |
Output is correct |
36 |
Correct |
49 ms |
14976 KB |
Output is correct |
37 |
Correct |
54 ms |
15944 KB |
Output is correct |
38 |
Correct |
51 ms |
15884 KB |
Output is correct |
39 |
Correct |
54 ms |
15912 KB |
Output is correct |
40 |
Correct |
50 ms |
15812 KB |
Output is correct |
41 |
Correct |
53 ms |
15812 KB |
Output is correct |
42 |
Correct |
58 ms |
14664 KB |
Output is correct |
43 |
Correct |
65 ms |
15920 KB |
Output is correct |
44 |
Correct |
68 ms |
15884 KB |
Output is correct |
45 |
Correct |
62 ms |
15904 KB |
Output is correct |
46 |
Correct |
62 ms |
15812 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6484 KB |
Output is correct |
2 |
Correct |
5 ms |
6484 KB |
Output is correct |
3 |
Incorrect |
4 ms |
6484 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6484 KB |
Output is correct |
2 |
Correct |
5 ms |
6484 KB |
Output is correct |
3 |
Incorrect |
4 ms |
6484 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
6484 KB |
Output is correct |
2 |
Correct |
5 ms |
6484 KB |
Output is correct |
3 |
Correct |
5 ms |
6484 KB |
Output is correct |
4 |
Correct |
54 ms |
16964 KB |
Output is correct |
5 |
Correct |
75 ms |
17024 KB |
Output is correct |
6 |
Correct |
55 ms |
16948 KB |
Output is correct |
7 |
Correct |
81 ms |
16804 KB |
Output is correct |
8 |
Correct |
56 ms |
17008 KB |
Output is correct |
9 |
Correct |
58 ms |
17012 KB |
Output is correct |
10 |
Correct |
58 ms |
16968 KB |
Output is correct |
11 |
Correct |
52 ms |
16844 KB |
Output is correct |
12 |
Correct |
58 ms |
16012 KB |
Output is correct |
13 |
Correct |
58 ms |
15956 KB |
Output is correct |
14 |
Correct |
55 ms |
15940 KB |
Output is correct |
15 |
Correct |
61 ms |
15812 KB |
Output is correct |
16 |
Correct |
51 ms |
15088 KB |
Output is correct |
17 |
Correct |
54 ms |
15052 KB |
Output is correct |
18 |
Correct |
55 ms |
14992 KB |
Output is correct |
19 |
Correct |
50 ms |
14736 KB |
Output is correct |
20 |
Correct |
53 ms |
14752 KB |
Output is correct |
21 |
Correct |
53 ms |
14800 KB |
Output is correct |
22 |
Correct |
56 ms |
14716 KB |
Output is correct |
23 |
Correct |
69 ms |
14736 KB |
Output is correct |
24 |
Correct |
56 ms |
14768 KB |
Output is correct |
25 |
Correct |
63 ms |
14708 KB |
Output is correct |
26 |
Correct |
72 ms |
14736 KB |
Output is correct |
27 |
Correct |
65 ms |
14776 KB |
Output is correct |
28 |
Correct |
51 ms |
14736 KB |
Output is correct |
29 |
Correct |
69 ms |
14744 KB |
Output is correct |
30 |
Correct |
53 ms |
14760 KB |
Output is correct |
31 |
Correct |
52 ms |
14768 KB |
Output is correct |
32 |
Correct |
57 ms |
14696 KB |
Output is correct |
33 |
Correct |
65 ms |
14796 KB |
Output is correct |
34 |
Correct |
53 ms |
15668 KB |
Output is correct |
35 |
Correct |
50 ms |
15244 KB |
Output is correct |
36 |
Correct |
49 ms |
14976 KB |
Output is correct |
37 |
Correct |
54 ms |
15944 KB |
Output is correct |
38 |
Correct |
51 ms |
15884 KB |
Output is correct |
39 |
Correct |
54 ms |
15912 KB |
Output is correct |
40 |
Correct |
50 ms |
15812 KB |
Output is correct |
41 |
Correct |
53 ms |
15812 KB |
Output is correct |
42 |
Correct |
58 ms |
14664 KB |
Output is correct |
43 |
Correct |
65 ms |
15920 KB |
Output is correct |
44 |
Correct |
68 ms |
15884 KB |
Output is correct |
45 |
Correct |
62 ms |
15904 KB |
Output is correct |
46 |
Correct |
62 ms |
15812 KB |
Output is correct |
47 |
Correct |
5 ms |
6484 KB |
Output is correct |
48 |
Correct |
5 ms |
6484 KB |
Output is correct |
49 |
Incorrect |
4 ms |
6484 KB |
Output isn't correct |
50 |
Halted |
0 ms |
0 KB |
- |