/**
____ ____ ____ ____ ____ ____
||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;
rel[m + 1].l = 1e9 + 10;
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][i] ++;
len[1][i] = len[1][pt[1][i]] + 1;
///cout << "line 107 " << i << " " << pt[1][i] << endl;
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(interval cur)
{
int lb = 1;
while(lb <= m && rel[lb].r <= cur.l)
lb ++;
lb --;
while(lb > 0 && used[lb])
lb --;
int rb = m;
while(rb > 0 && rel[rb].l >= cur.r)
rb --;
rb ++;
while(rb <= m && used[rb])
rb ++;
int longest = len[0][lb] + len[1][rb];
//cout << lb << " " << rb << " " << len[1][3] << endl;
return longest;
}
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(seg[i]);
/**cout << i << " -- " << longest << endl;
cout << i << " " << longest << endl;
for (int j = 1; j <= m; j ++)
cout << len[1][j] << " ";
cout << endl;*/
if (longest >= k - 1)
{
seq.push_back(i);
k --;
get_intersections(seg[i]);
apply_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
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Execution timed out |
3057 ms |
3672 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 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 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
348 KB |
Output is correct |
| 2 |
Correct |
0 ms |
348 KB |
Output is correct |
| 3 |
Correct |
0 ms |
348 KB |
Output is correct |
| 4 |
Execution timed out |
3057 ms |
3672 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
