#include <bits/stdc++.h>
using namespace std;
#define f1r(i, a, b) for (int i = a; i < b; ++i)
#define f0r(i, a) f1r(i, 0, a)
#define each(t, a) for (auto& t : a)
#define mp make_pair
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
template <class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template <class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
template <class T> int get_pos(vector<T>& v, T x) {
return lower_bound(all(v), x) - v.begin();
}
const int INF = 1e9;
const int INF2 = 5e8;
struct SegmentTree {
vpi st;
int sz;
int ty = 0;
int nil;
void init(int n, int t) {
ty = t;
if (ty == 0) {
nil = INF;
} else {
nil = -INF;
}
sz = 1;
while (sz < n) sz <<= 1;
st.assign(2 * sz, mp(nil, 0));
f0r(i, sz) st[i + sz].s = i;
}
pi comb(pi x, pi y) {
if (ty == 0) return min(x, y);
return max(x, y);
}
void pull(int i) {
st[i] = comb(st[2 * i], st[2 * i + 1]);
}
void upd(int p, int x, int i = 1, int l = 0, int r = -1) {
if (r == -1) r += sz;
if (p < l || r < p) return;
if (l == r) {
st[i] = comb(st[i], {x, p});
return;
}
int m = (l + r) >> 1;
upd(p, x, 2 * i, l, m);
upd(p, x, 2 * i + 1, m + 1, r);
pull(i);
}
pi query(int lo, int hi, int i = 1, int l = 0, int r = -1) {
if (r == -1) r += sz;
if (hi < l || r < lo) return {nil, nil};
else if (lo <= l && r <= hi) return st[i];
int m = (l + r) >> 1;
return comb(query(lo, hi, 2 * i, l, m), query(lo, hi, 2 * i + 1, m + 1, r));
}
};
struct IntervalUnion {
set<pi> ivals;
void insert(pi x) {
ivals.insert(x);
}
bool bad(pi x) {
auto it = ivals.lower_bound({x.f, -INF});
if (it != ivals.end()) {
if (it->f == x.f) return true;
if (it->f < x.s) return true;
}
if (it == ivals.begin()) return false;
it = prev(it);
if (it->s > x.f) return true;
return false;
}
};
int main() {
cin.tie(0)->sync_with_stdio(0);
int n, k; cin >> n >> k;
vpi v(n);
f0r(i, n) cin >> v[i].f >> v[i].s;
vi pts;
each(p, v) pts.pb(p.f), pts.pb(p.s);
sort(all(pts));
pts.erase(unique(all(pts)), pts.end());
each(p, v) p.f = get_pos(pts, p.f), p.s = get_pos(pts, p.s);
map<pi, int> conv; // this is not unique possibly, but that doesn't matter
f0r(i, n) conv[v[i]] = i;
vi ord(n);
iota(all(ord), 0);
sort(all(ord), [&](int x, int y) {
return v[x].f < v[y].f;
});
int d = 1;
while ((1 << d) < n) ++d;
vector<vi> L, R;
vector<vector<bool>> LB, RB;
L = R = vector<vi>(d, vi(n));
LB = RB = vector<vector<bool>>(d, vector<bool>(n));
int sz = sz(pts);
SegmentTree seg;
seg.init(sz, 0);
for (int i = n - 1; i >= 0; i--) {
int id = ord[i];
int l = v[id].f;
int r = v[id].s;
auto res = seg.query(r, sz - 1);
if (res.f != seg.nil) {
R[0][id] = conv[{res.s, res.f}];
RB[0][id] = true;
} else {
R[0][id] = id;
}
seg.upd(l, r);
}
sort(all(ord), [&](int x, int y) {
return v[x].s < v[y].s;
});
seg.init(sz, 1);
f0r(i, n) {
int id = ord[i];
int l = v[id].f;
int r = v[id].s;
auto res = seg.query(0, l);
if (res.f != seg.nil) {
L[0][id] = conv[{res.f, res.s}];
LB[0][id] = true;
} else {
L[0][id] = id;
}
seg.upd(r, l);
}
f1r(j, 1, d) {
f0r(i, n) {
L[j][i] = L[j - 1][L[j - 1][i]];
R[j][i] = R[j - 1][R[j - 1][i]];
LB[j][i] = LB[j - 1][L[j - 1][i]] & LB[j - 1][i];
RB[j][i] = RB[j - 1][R[j - 1][i]] & RB[j - 1][i];
}
}
vi ans;
IntervalUnion IU;
auto overlap = [&](pi x, pi y) -> bool {
if (x > y) swap(x, y);
if (x.s <= y.f) return false;
return true;
};
auto compute = [&](int x, int y) -> int { // assumes nonoverlapping
int amt = 0;
if (x == -1 && y == -1) {
amt = 0;
} else if (x == -1) { // that means null left
int cur = y;
for (int i = d - 1; i >= 0; i--) {
if (LB[i][cur]) continue;
cur = L[i][cur];
amt += (1 << i);
}
} else if (y == -1) {
int cur = x;
for (int i = d - 1; i >= 0; i--) {
if (RB[i][cur]) continue;
cur = R[i][cur];
amt += (1 << i);
}
} else {
if (v[x] > v[y]) swap(x, y);
int cur = x;
for (int i = d - 1; i >= 0; i--) {
if (!RB[i][cur]) continue;
auto g = R[i][cur];
if (v[g].s <= v[y].f) {
amt += (1 << i);
cur = g;
}
}
}
return amt;
};
int cur = 0;
f0r(i, n) {
auto& p = v[i];
int l = p.f;
int r = p.s;
if (IU.bad(p)) continue;
auto it = IU.ivals.upper_bound(p);
int aft = -1;
if (it != IU.ivals.end()) aft = conv[*it];
int bef = -1;
if (it != IU.ivals.begin()) bef = conv[*prev(it)];
int now = compute(bef, aft);
int future = compute(bef, i) + compute(i, aft);
if (cur - now + future + 1 >= k) {
cur = cur - now + future + 1;
IU.insert(p);
ans.pb(i);
}
}
if (sz(ans) >= k) {
f0r(i, k) cout << ans[i] + 1 << '\n';
} else {
cout << -1 << '\n';
}
return 0;
}
/**
* store at left coordinate right coordinate, find minimum right coordinate
*/
Compilation message
event2.cpp: In function 'int main()':
event2.cpp:231:13: warning: unused variable 'l' [-Wunused-variable]
231 | int l = p.f;
| ^
event2.cpp:232:13: warning: unused variable 'r' [-Wunused-variable]
232 | int r = p.s;
| ^
event2.cpp:188:10: warning: variable 'overlap' set but not used [-Wunused-but-set-variable]
188 | auto overlap = [&](pi x, pi y) -> bool {
| ^~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
368 ms |
32960 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
312 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
368 ms |
32960 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
