#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
mt19937 rr(133337);
struct Node {
int x, y, cnt;
Node* l;
Node* r;
Node(int x) : x(x), y(rr()), cnt(1), l(nullptr), r(nullptr) {}
};
int cnt(Node* t) {
return t ? t->cnt : 0;
}
void update(Node* t) {
if (t) {
t->cnt = cnt(t->l) + cnt(t->r) + 1;
}
}
void split(Node* t, Node*& l, Node*& r, int x) {
if (!t) {
l = r = nullptr;
return;
}
if (t->x >= x) {
split(t->l, l, t->l, x);
r = t;
} else {
split(t->r, t->r, r, x);
l = t;
}
update(t);
}
void merge(Node*& t, Node* l, Node* r) {
if (!l) {
t = r;
} else if (!r) {
t = l;
} else {
if (l->y > r->y) {
merge(l->r, l->r, r);
t = l;
} else {
merge(r->l, l, r->l);
t = r;
}
update(t);
}
}
void ins(Node*& t, int x) {
Node* A;
split(t, t, A, x);
merge(t, t, new Node(x));
merge(t, t, A);
}
void del(Node*& t, int x) {
Node* A;
Node* B;
split(t, t, B, x + 1);
split(t, A, t, x);
assert(t);
delete t;
merge(t, A, B);
}
int order_of_key(Node*& t, int x) {
Node* A;
split(t, t, A, x);
int res = cnt(t);
merge(t, t, A);
return res;
}
const int base = 1 << 16;
const int inf = 1e9;
Node* t[base * 2];
vector<pair<int, int>> xc;
int k;
int tget(int l, int r, int v = 1, int cl = 0, int cr = base) {
if (l <= cl && cr <= r) {
int res = cnt(t[v]) - order_of_key(t[v], r);
return res;
}
if (r <= cl || cr <= l) {
return 0;
}
int cc = (cl + cr) / 2;
return tget(l, r, v * 2, cl, cc) + tget(l, r, v * 2 + 1, cc, cr);
}
int get(int x) {
int L = -1, R = inf / 2;
map<pair<int, int>, int> bscache;
bool ok = false;
while (L + 1 < R) {
int C = (L + R) / 2;
int lb = lower_bound(xc.begin(), xc.end(), pair<int, int>{x - C, -1}) - xc.begin();
int rb = upper_bound(xc.begin(), xc.end(), pair<int, int>{x + C, inf}) - xc.begin();
auto q = pair<int, int>{lb, rb};
int cnt;
if (bscache.count(q)) {
cnt = bscache[q];
} else {
bscache[q] = cnt = tget(lb, rb);
}
assert(cnt <= k);
if (cnt == k) {
R = C;
ok = true;
} else {
L = C;
}
}
if (!ok) {
return -1;
} else {
return R;
}
}
void tput(int v, int val) {
v += base;
while (v >= 1) {
ins(t[v], val);
v /= 2;
}
}
void tdel(int v, int val) {
v += base;
while (v >= 1) {
del(t[v], val);
v /= 2;
}
}
set<int> pos[base];
void put(int x, int t, int delta) {
if (delta == -1) {
auto it = pos[t].upper_bound(x);
int val = it == pos[t].end() ? inf + t : *it;
if (it != pos[t].begin()) {
--it;
tdel(*it, val);
tput(*it, x);
}
pos[t].insert(x);
tput(x, val);
} else if (delta == 1) {
assert(pos[t].count(x));
auto it = pos[t].upper_bound(x);
int val = it == pos[t].end() ? inf + t : *it;
tdel(x, val);
pos[t].erase(x);
if (it != pos[t].begin()) {
tput(*it, val);
}
} else {
assert(false);
}
}
signed main() {
#ifdef LOCAL
assert(freopen("a.in", "r", stdin));
#endif
struct Event {
int tp, tm, x, t, id;
bool operator<(const Event& e) const {
if (tm != e.tm) {
return tm < e.tm;
}
return tp < e.tp;
}
};
int n, q;
cin >> n >> k >> q;
vector<Event> ev;
for (int i = 0; i < n; ++i) {
int x, t, a, b;
cin >> x >> t >> a >> b;
ev.push_back(Event{-1, a, x, t, i});
ev.push_back(Event{1, b, x, t, i});
xc.emplace_back(x, i);
}
sort(xc.begin(), xc.end());
for (int i = 0; i < q; ++i) {
int l, y;
cin >> l >> y;
ev.push_back(Event{0, y, l, -1, i});
}
sort(ev.begin(), ev.end());
vector<int> res(q);
for (auto& e : ev) {
if (e.tp == 0) {
res[e.id] = get(e.x);
} else {
auto sx = lower_bound(xc.begin(), xc.end(), pair<int, int>{e.x, e.id}) - xc.begin();
put(sx, e.t, e.tp);
}
}
for (int i = 0; i < q; ++i) {
cout << res[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
6648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
6648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
975 ms |
54784 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1004 ms |
55476 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
6648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
8 ms |
6648 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
