/**
____ ____ ____ ____ ____ ____
||l |||e |||i |||n |||a |||d ||
||__|||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|/__\|
**/
#include<bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
const int maxn = 1e5 + 10;
struct interval
{
int l, r;
};
int n, k;
interval seg[maxn];
void input()
{
cin >> n >> k;
for (int i = 1; i <= n; i ++)
cin >> seg[i].l >> seg[i].r;
}
bool cmp(interval it1, interval it2)
{
if (it1.l != it2.l)
return it1.l < it2.l;
return it1.r > it2.r;
}
interval rel[maxn];
int m;
void get_relevant()
{
vector < interval > vec;
for (int i = 1; i <= n; i ++)
vec.push_back(seg[i]);
sort(vec.begin(), vec.end(), cmp);
int cl = 1e9 + 10;
for (int i = n - 1; i >= 0; i --)
{
if (vec[i].r >= cl)
{
continue;
}
rel[++ m] = vec[i];
cl = vec[i].r;
}
reverse(rel + 1, rel + m + 1);
}
int len[2][maxn], pt[2][maxn], used[maxn];
void calc_pointers()
{
int last = 0;
for (int i = 1; i <= m; i ++)
{
if (used[i])
continue;
pt[0][i] = 0;
if (last != 0)
pt[0][i] = pt[0][last];
while(rel[pt[0][i]].r <= rel[i].l)
pt[0][i] ++;
pt[0][i] --;
while(pt[0][i] > 0 && used[pt[0][i]])
pt[0][i] --;
len[0][i] = len[0][pt[0][i]] + 1;
last = i;
}
last = m + 1;
for (int i = m; i > 0; i --)
{
if (used[i])
continue;
pt[1][i] = m + 1;
if (last != m + 1)
pt[1][i] = pt[1][last];
while(rel[pt[1][i]].l >= rel[i].r)
pt[1][i] --;
pt[1][i] ++;
while(pt[1][i] <= m && used[pt[1][m]])
pt[1][m] ++;
len[1][i] = len[1][pt[1][i]] + 1;
last = i;
}
}
bool intersect(interval a, interval b)
{
if (a.l == b.l)
return true;
if (a.l > b.l)
swap(a, b);
if (a.r >= b.r)
return true;
return a.r > b.l;
}
void get_intersections(interval cur)
{
for (int i = 1; i <= m; i ++)
if (used[i] == 0 && intersect(rel[i], cur))
used[i] = 2;
}
int get_longest()
{
int ans = 0;
for (int i = 1; i <= m; i ++)
{
if (used[i])
continue;
ans = max(ans, max(len[0][i], len[1][i]));
}
return ans;
}
void reverse_intersections()
{
for (int i = 1; i <= m; i ++)
if (used[i] == 2)
used[i] = 0;
}
void apply_intersections()
{
for (int i = 1; i <= m; i ++)
if (used[i] == 2)
used[i] = 1;
}
void create_sequence()
{
vector < int > seq;
for (int i = 1; i <= n && k > 0; i ++)
{
bool valid = true;
for (int cur : seq)
{
if (intersect(seg[cur], seg[i]))
{
valid = false;
break;
}
}
if (!valid)
continue;
get_intersections(seg[i]);
calc_pointers();
int longest = get_longest();
/**cout << i << " " << longest << endl;
for (int j = 1; j <= m; j ++)
cout << len[0][j] << " ";
cout << endl;*/
if (longest >= k - 1)
{
seq.push_back(i);
k --;
apply_intersections();
}
else
reverse_intersections();
}
if (k != 0)
{
cout << -1 << endl;
return;
}
for (int cur : seq)
cout << cur << endl;
}
void solve()
{
input();
get_relevant();
///calc_pointers();
create_sequence();
}
int main()
{
solve();
return 0;
}
/**
2 2
1 3
1 2
*/
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Execution timed out |
3007 ms |
3924 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
504 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
504 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Correct |
0 ms |
348 KB |
Output is correct |
5 |
Correct |
1 ms |
348 KB |
Output is correct |
6 |
Correct |
0 ms |
348 KB |
Output is correct |
7 |
Correct |
0 ms |
348 KB |
Output is correct |
8 |
Correct |
0 ms |
348 KB |
Output is correct |
9 |
Correct |
0 ms |
348 KB |
Output is correct |
10 |
Correct |
0 ms |
348 KB |
Output is correct |
11 |
Correct |
0 ms |
344 KB |
Output is correct |
12 |
Correct |
0 ms |
348 KB |
Output is correct |
13 |
Correct |
0 ms |
348 KB |
Output is correct |
14 |
Correct |
0 ms |
344 KB |
Output is correct |
15 |
Correct |
0 ms |
348 KB |
Output is correct |
16 |
Correct |
0 ms |
348 KB |
Output is correct |
17 |
Correct |
0 ms |
348 KB |
Output is correct |
18 |
Correct |
0 ms |
348 KB |
Output is correct |
19 |
Correct |
0 ms |
348 KB |
Output is correct |
20 |
Correct |
0 ms |
348 KB |
Output is correct |
21 |
Correct |
0 ms |
348 KB |
Output is correct |
22 |
Correct |
0 ms |
348 KB |
Output is correct |
23 |
Correct |
0 ms |
348 KB |
Output is correct |
24 |
Correct |
1 ms |
348 KB |
Output is correct |
25 |
Correct |
0 ms |
348 KB |
Output is correct |
26 |
Correct |
0 ms |
348 KB |
Output is correct |
27 |
Correct |
1 ms |
348 KB |
Output is correct |
28 |
Correct |
3 ms |
348 KB |
Output is correct |
29 |
Correct |
3 ms |
348 KB |
Output is correct |
30 |
Correct |
2 ms |
348 KB |
Output is correct |
31 |
Correct |
2 ms |
348 KB |
Output is correct |
32 |
Correct |
2 ms |
348 KB |
Output is correct |
33 |
Correct |
5 ms |
552 KB |
Output is correct |
34 |
Correct |
5 ms |
348 KB |
Output is correct |
35 |
Correct |
126 ms |
604 KB |
Output is correct |
36 |
Correct |
117 ms |
604 KB |
Output is correct |
37 |
Correct |
88 ms |
600 KB |
Output is correct |
38 |
Correct |
90 ms |
604 KB |
Output is correct |
39 |
Correct |
105 ms |
852 KB |
Output is correct |
40 |
Correct |
95 ms |
604 KB |
Output is correct |
41 |
Correct |
97 ms |
604 KB |
Output is correct |
42 |
Correct |
89 ms |
604 KB |
Output is correct |
43 |
Correct |
34 ms |
604 KB |
Output is correct |
44 |
Correct |
27 ms |
604 KB |
Output is correct |
45 |
Correct |
25 ms |
604 KB |
Output is correct |
46 |
Correct |
73 ms |
604 KB |
Output is correct |
47 |
Correct |
7 ms |
348 KB |
Output is correct |
48 |
Correct |
5 ms |
348 KB |
Output is correct |
49 |
Correct |
4 ms |
348 KB |
Output is correct |
50 |
Correct |
30 ms |
348 KB |
Output is correct |
51 |
Correct |
5 ms |
348 KB |
Output is correct |
52 |
Correct |
3 ms |
348 KB |
Output is correct |
53 |
Correct |
3 ms |
552 KB |
Output is correct |
54 |
Correct |
13 ms |
348 KB |
Output is correct |
55 |
Correct |
65 ms |
604 KB |
Output is correct |
56 |
Correct |
66 ms |
604 KB |
Output is correct |
57 |
Correct |
66 ms |
604 KB |
Output is correct |
58 |
Correct |
65 ms |
600 KB |
Output is correct |
59 |
Correct |
68 ms |
604 KB |
Output is correct |
60 |
Correct |
63 ms |
600 KB |
Output is correct |
61 |
Correct |
62 ms |
600 KB |
Output is correct |
62 |
Correct |
61 ms |
608 KB |
Output is correct |
63 |
Correct |
57 ms |
856 KB |
Output is correct |
64 |
Correct |
86 ms |
604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
344 KB |
Output is correct |
3 |
Correct |
0 ms |
348 KB |
Output is correct |
4 |
Execution timed out |
3007 ms |
3924 KB |
Time limit exceeded |
5 |
Halted |
0 ms |
0 KB |
- |