/**
____ ____ ____ ____ ____ ____
||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;
len[0][i] = 0;
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;
len[1][i] = 0;
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][i]])
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;
}
set < pair < int, int > > act;
const int maxlog = 21;
int dp[maxlog][maxn];
int fen[2][maxn];
void add(int r, int p, int v)
{
///cout << v << endl;
for (int i = p; i <= m; i += (i & -i))
fen[r][i] += v;
}
int sum(int r, int p)
{
int s = 0;
for (int i = p; i > 0; i -= (i & -i))
s += fen[r][i];
return s;
}
int get_length(int pos, int to)
{
int jump = 0;
for (int bit = maxlog - 1; bit >= 0; bit --)
{
//cout << "get length " << pos << " " << jump << " " << m << endl;
if (dp[bit][pos] <= to)
{
jump += (1 << bit);
pos = dp[bit][pos];
}
}
return jump + 1;
}
int get_pos(int r, int pos)
{
return sum(r, pos) - sum(r, pos - 1);
}
void remove_interval(int l, int r)
{
while(true)
{
set < pair < int, int > > :: iterator it = act.lower_bound({l, -1});
if (it == act.end() || it -> first > r)
break;
if (it -> second <= r)
act.erase(it);
else
{
pair < int, int > nw;
nw.first = r + 1;
nw.second = it -> second;
act.erase(it);
add(1, it -> first, -get_pos(1,it -> first));
act.insert(nw);
add(1, nw.first, get_length(nw.first, nw.second));
break;
}
}
set < pair < int, int > > :: iterator it = act.lower_bound({l, -1});
//cout << "cur " << it -> first << " " << it -> second << endl;
if (it != act.begin())
{
it = prev(it);
///cout << "back " << it -> first << " " << it -> second << endl;
if (it -> second > r)
{
pair < int, int > lf = *it, rf = *it;
lf.second = l - 1;
rf.first = r + 1;
act.erase(it);
add(1, it -> first, -get_pos(1,it -> first));
act.insert(lf);
add(1, lf.first, get_length(lf.first, lf.second));
act.insert(rf);
add(1, rf.first, get_length(rf.first, rf.second));
}
else if (it -> second >= l)
{
pair < int, int > nw = *it;
nw.second = l - 1;
act.erase(it);
add(1, it -> first, -get_pos(1, it -> first));
act.insert(nw);
add(1, nw.first, get_length(nw.first, nw.second));
}
}
}
pair < int, int > first_bef(int pos)
{
set < pair < int, int > > :: iterator it = act.lower_bound({pos, -1});
if (it == act.begin())
return {0, 0};
return {it -> first, min(pos - 1, prev(it) -> second)};
}
pair < int, int > first_aft(int pos)
{
set < pair < int, int > > :: iterator it = act.lower_bound({pos, -1});
if (it != act.begin() && prev(it) -> second > pos)
return {pos + 1, prev(it) -> second};
if (it == act.end())
return {m + 1, m + 1};
return {max(pos + 1, it -> first), it -> second};
}
int lb_last, rb_last;
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 lf = 1, rf = m;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (rel[mf].r <= cur.l)
lf = mf + 1;
else
rf = mf - 1;
}
int lb = lf;
lf = 1;
rf = m;
while(lf <= rf)
{
int mf = (lf + rf) / 2;
if (rel[mf].l >= cur.r)
rf = mf - 1;
else
lf = mf + 1;
}
int rb = rf;
pair < int, int > fb = first_bef(lb);
pair < int, int > fa = first_aft(rb);
///cout << sum(1, m) << " :::: " << sum(1, fa.second) << endl;
int longest = len[0][fb.second];
///cout << "HERE " << fa.first << " " << fa.second << " " << get_length(fa.first, fa.second) << endl;
if (fa.second != m + 1)
longest += get_length(fa.first, fa.second) + sum(1, m) - sum(1, fa.second);
///int longest = len[0][fb.second] + len[1][fa.first];
lb_last = lb;
rb_last = rb;
/**for (pair < int, int > cur : act)
cout << cur.first << " ::: " << cur.second << endl;
cout << "borders " << lb << " " << rb << " " << first_bef(lb) << " " << first_aft(rb) << 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 binary_lifting()
{
int last = 0;
rel[m + 1].l = 1e9 + 10;
for (int i = 1; i <= m; i ++)
{
if (used[i])
continue;
len[0][i] = 0;
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;
len[1][i] = 0;
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][i]])
pt[1][i] ++;
len[1][i] = len[1][pt[1][i]] + 1;
///cout << "line 107 " << i << " " << pt[1][i] << endl;
last = i;
}
for (int i = 0; i <= m; i ++)
dp[0][i] = pt[1][i];
for (int j = 0; j < maxlog; j ++)
dp[j][m + 1] = m + 1;
for (int j = 1; j < maxlog; j ++)
{
for (int i = 1; i <= m; i ++)
{
dp[j][i] = dp[j - 1][dp[j - 1][i]];
}
}
}
void create_sequence()
{
act.insert({1, m});
binary_lifting();
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 << "longest " << i << " -- " << longest << endl;
/*for (int j = 1; j <= m; j ++)
cout << used[j] << " ";
cout << endl;*/
/* for (int j = 1; j <= m; j ++)
cout << len[0][j] << " ";
cout << endl;*/
if (longest >= k - 1)
{
seq.push_back(i);
k --;
remove_interval(lb_last, rb_last);
get_intersections(seg[i]);
apply_intersections();
}
/**for (int j = 1; j <= m; j ++)
cout << used[j] << " ";
cout << endl;*/
}
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
20 9
18 22
2 5
28 31
21 25
25 27
3 6
36 39
22 26
8 12
27 31
27 29
32 36
14 18
16 20
22 26
10 14
17 21
13 17
15 19
37 40
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12788 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 4 |
Execution timed out |
3082 ms |
12912 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 5 |
Correct |
1 ms |
12888 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 8 |
Correct |
2 ms |
12728 KB |
Output is correct |
| 9 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 10 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 11 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 12 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 13 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 14 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 15 |
Correct |
2 ms |
12740 KB |
Output is correct |
| 16 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 17 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 18 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 19 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 20 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 21 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 22 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 23 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 24 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 25 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 26 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 27 |
Correct |
1 ms |
12636 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 4 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 5 |
Correct |
1 ms |
12888 KB |
Output is correct |
| 6 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 7 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 8 |
Correct |
2 ms |
12728 KB |
Output is correct |
| 9 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 10 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 11 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 12 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 13 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 14 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 15 |
Correct |
2 ms |
12740 KB |
Output is correct |
| 16 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 17 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 18 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 19 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 20 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 21 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 22 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 23 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 24 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 25 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 26 |
Correct |
2 ms |
12632 KB |
Output is correct |
| 27 |
Correct |
1 ms |
12636 KB |
Output is correct |
| 28 |
Incorrect |
4 ms |
12888 KB |
Output isn't correct |
| 29 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
12788 KB |
Output is correct |
| 2 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 3 |
Correct |
2 ms |
12636 KB |
Output is correct |
| 4 |
Execution timed out |
3082 ms |
12912 KB |
Time limit exceeded |
| 5 |
Halted |
0 ms |
0 KB |
- |
