#include <bits/stdc++.h>
#define se second
#define fs first
#define pb push_back
#define ll long long
#define ii pair<ll,ll>
#define ld long double
#define SZ(v) (int)v.size()
#define ALL(v) v.begin(), v.end()
#define bit(msk, i) ((msk >> i) & 1)
#define iter(id, v) for(auto id : v)
#define rep(i,m,n) for(int i=(m); i<=(n); i++)
#define reb(i,m,n) for(int i=(m); i>=(n); i--)
using namespace std;
mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }
const int N = 5e5 + 7;
const ll Mod = 1e9 + 7;
const int szBL = 916;
const int INF = 2e9 + 7;
const int BASE = 137;
struct Segment_Tree {
int Range;
ll st[N << 2], lz[N << 2];
void init (int n) {
Range = n;
}
void down (int id, int l, int r) {
int mid = l + r >> 1;
st[id << 1] += lz[id] * (mid - l + 1);
lz[id << 1] += lz[id];
st[id << 1 | 1] += lz[id] * (r - mid);
lz[id << 1 | 1] += lz[id];
lz[id] = 0;
}
void update (int id, int l, int r, int u, int v, int val) {
if (l > v || r < u) return;
if (l >= u && r <= v) {
st[id] += val * (r - l + 1);
lz[id] += val;
return;
}
int mid = l + r >> 1;
down (id, l, r);
update (id << 1, l, mid, u, v, val);
update (id << 1 | 1, mid + 1, r, u, v, val);
st[id] = st[id << 1] + st[id << 1 | 1];
}
void Assign (int id, int l, int r, int pos, int val) {
if (l > pos || r < pos) return;
if (l == r) {
st[id] = val;
return;
}
int mid = l + r >> 1;
down (id, l, r);
Assign (id << 1, l, mid, pos, val);
Assign (id << 1 | 1, mid + 1, r, pos, val);
st[id] = st[id << 1] + st[id << 1 | 1];
}
ll get (int id, int l, int r, int u, int v) {
if (l > v || r < u) return 0;
if (l >= u && r <= v) return st[id];
int mid = l + r >> 1;
down (id, l, r);
return get (id << 1, l, mid, u, v) + get (id << 1 | 1, mid + 1, r, u, v);
}
void update (int u, int v, int val) {
update (1, 1, Range, u, v, val);
}
void Assign (int pos, int val) {
Assign (1, 1, Range, pos, val);
}
ll get (int u, int v) {
return get (1, 1, Range, u, v);
}
}pre, suf, Fixed;
int n, K;
pair<int,int> a[N];
pair<int,int> toIT[N];
int spt[N][25];
vector<int> rar;
int numVal;
int mnsuf[N];
void compress () {
rep (i, 1, n) rar.push_back(a[i].fs), rar.push_back(a[i].se);
sort (ALL(rar));
rar.resize(numVal = unique(ALL(rar)) - rar.begin());
rep (i, 1, n)
a[i].fs = lower_bound(ALL(rar), a[i].fs) - rar.begin() + 1,
a[i].se = lower_bound(ALL(rar), a[i].se) - rar.begin() + 1;
}
void solution() {
cin >> n >> K;
rep (i, 1, n) {
cin >> a[i].fs >> a[i].se;
}
compress();
// rep (i, 1, n) {
// cout << a[i].fs <<","<<a[i].se <<"\n";
// }
rep (i, 0, numVal + 1) mnsuf[i] = numVal + 2;
rep (i, 1, n)
mnsuf[a[i].fs] = min (mnsuf[a[i].fs], a[i].se);
rep (i, 0, numVal)
mnsuf[i] = min (mnsuf[i + 1], mnsuf[i]);
rep (i, 0, numVal)
spt[i][0] = mnsuf[i];
rep (j, 1, 20)
rep (i, 0, numVal) spt[i][j] = spt[spt[i][j - 1]][j - 1];
pre.init(numVal);
suf.init(numVal);
Fixed.init(numVal);
vector<int> Ans;
function<int(int L, int R)> numIT = [] (int L, int R) {
int start = L, res = 0;
reb (i, 20, 0) {
if (spt[start][i] <= R) {
start = spt[start][i];
res += (1 << i);
}
}
return res;
};
rep (i, 1, n) {
if (SZ(Ans) == K) break;
int L = a[i].fs, R = a[i].se;
if (Fixed.get (L + 1, R - 1)) {
continue;
}
function<int()> val_Left = [&] () {
if (Fixed.get (1, L) == 0) return 0;
int lf = 1, rt = L;
while (lf < rt) {
int mid = lf + rt + 1 >> 1;
if (Fixed.get (mid, L) >= 1) lf = mid;
else rt = mid - 1;
}
return lf;
};
function<int()> val_Right = [&] () {
if (Fixed.get (R, numVal) == 0) return numVal + 1;
int lf = R, rt = numVal;
while (lf < rt) {
int mid = lf + rt >> 1;
if (Fixed.get (R, mid) >= 1) rt = mid;
else lf = mid + 1;
}
return rt;
};
int Left = val_Left(), Right = val_Right();
int valLR = numIT (Left, Right),
nvalLR = 1 + numIT(Left, L) + numIT(R, Right);
if (pre.get(Left, Left) + suf.get(Right, Right) + nvalLR >= K) {
Fixed.update (L, R, 1);
suf.update (1, Left, -valLR + nvalLR);
pre.update (Right, numVal, -valLR + nvalLR);
pre.Assign (R, pre.get(Left, Left) + numIT(Left, L) + 1);
suf.Assign (L, suf.get(Right, Right) + numIT(R, Right) + 1);
Ans.push_back(i);
}
}
if (SZ(Ans) < K) cout << -1 <<"\n";
else {
iter (&id, Ans) cout << id <<"\n";
}
}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
// file("c");
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll num_Test = 1;
// cin >> num_Test;
while(num_Test--)
solution();
}
/*
14 3
74 17 88 80 70 24 66 29 24 63 84 36 72 43
*/
Compilation message
event2.cpp: In member function 'void Segment_Tree::down(int, int, int)':
event2.cpp:34:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
34 | int mid = l + r >> 1;
| ~~^~~
event2.cpp: In member function 'void Segment_Tree::update(int, int, int, int, int, int)':
event2.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
50 | int mid = l + r >> 1;
| ~~^~~
event2.cpp: In member function 'void Segment_Tree::Assign(int, int, int, int, int)':
event2.cpp:62:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
62 | int mid = l + r >> 1;
| ~~^~~
event2.cpp: In member function 'long long int Segment_Tree::get(int, int, int, int, int)':
event2.cpp:71:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
71 | int mid = l + r >> 1;
| ~~^~~
event2.cpp: In lambda function:
event2.cpp:149:35: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
149 | int mid = lf + rt + 1 >> 1;
| ~~~~~~~~^~~
event2.cpp: In lambda function:
event2.cpp:159:30: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
159 | int mid = lf + rt >> 1;
| ~~~^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 4 |
Incorrect |
456 ms |
52524 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
10584 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
10588 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
10584 KB |
Output is correct |
| 2 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 3 |
Correct |
2 ms |
10588 KB |
Output is correct |
| 4 |
Incorrect |
456 ms |
52524 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
