#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using oset = __gnu_pbds::tree<int, __gnu_pbds::null_type,
std::less<int>,
__gnu_pbds::rb_tree_tag,
__gnu_pbds::tree_order_statistics_node_update>;
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
const int base = 1 << 16;
const int inf = 1e9;
oset 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) {
return t[v].size() - t[v].order_of_key(r);
}
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) {
t[v].insert(val);
v /= 2;
}
}
void tdel(int v, int val) {
v += base;
while (v >= 1) {
int ss = t[v].size();
t[v].erase(val);
ss -= t[v].size();
assert(ss == 1);
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 |
27 ms |
27132 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 |
27 ms |
27132 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 |
984 ms |
75544 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 |
968 ms |
76204 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 |
27 ms |
27132 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 |
27 ms |
27132 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
