#include <cstdio>
#include <utility>
#include <algorithm>
#include <cstring>
#include <vector>
const int INF = 0x3f3f3f3f;
struct store {
int x, t, l, r;
bool operator<(store arg) {
return x < arg.x;
}
};
struct query {
int l, y, ind;
bool operator<(query arg) {
return y < arg.y;
}
};
bool cmp_l(query a, query b)
{
return a.l < b.l;
}
const int N = 300000;
const int K = 600;
int n, k, q, next[N + 1], type_amt[N], ans[N], it[N], fi[N], last[N], right[N], to[N];
bool ut[N], active[N];
store a[N + 1];
query qr[N];
int main()
{
scanf("%d%d%d", &n, &k, &q);
a[n].x = INF;
next[n] = n;
memset(to, 0x3f, k << 2);
for (int i = 0; i < n; ++i) {
scanf("%d%d%d%d", &a[i].x, &a[i].t, &a[i].l, &a[i].r);
--a[i].t;
++a[i].r;
}
std::sort(a, a + n);
for (int i = 0; i < q; ++i) {
scanf("%d%d", &qr[i].l, &qr[i].y);
qr[i].ind = i;
}
std::sort(qr, qr + q);
int X = 0;
for (int i = 0; i < q;) {
memset(ut, 0, k);
int until = std::min(i + K, q);
std::vector<int> inter, inter_type;
for (int j = 0; j < n; ++j) if (a[j].l >= qr[i].y + 1 && a[j].l <= qr[until - 1].y || a[j].r >= qr[i].y + 1 && a[j].r <= qr[until - 1].y) {
if (!ut[a[j].t]) {
inter_type.push_back(a[j].t);
fi[a[j].t] = n;
}
ut[a[j].t] = 1;
inter.push_back(j);
++X;
}
assert(X < 3 * N);
memset(last, -1, n << 2);
for (int j = 0; j < n; ++j) {
if (a[j].l <= qr[i].y && a[j].r > qr[until - 1].y) {
if (ut[a[j].t]) {
active[j] = false;
if (last[a[j].t] == -1) fi[a[j].t] = j;
else next[last[a[j].t]] = j;
last[a[j].t] = j;
next[j] = n;
}
else active[j] = true;
}
else active[j] = false;
}
for (int j = 0, l = 0, amt = 0; j < n; ++j) {
while (l == j || l <= n && amt < k - inter_type.size()) {
if (l < n && active[l]) {
if (!type_amt[a[l].t]) ++amt;
++type_amt[a[l].t];
}
++l;
}
right[j] = l;
if (active[j]) {
--type_amt[a[j].t];
if (!type_amt[a[j].t]) --amt;
}
}
std::sort(qr + i, qr + until, cmp_l);
for (int j = 0; i < until; ++i) {
while (qr[i].l - a[j].x > a[right[j] - 1].x - qr[i].l) ++j;
int res = std::min(j ? qr[i].l - a[j - 1].x : INF, a[right[j] - 1].x - qr[i].l);
for (int k = 0; k < (int)inter.size(); ++k) if (a[inter[k]].l <= qr[i].y && a[inter[k]].r > qr[i].y) to[a[inter[k]].t] = std::min(to[a[inter[k]].t], abs(qr[i].l - a[inter[k]].x));
for (int k = 0; k < (int)inter_type.size(); ++k) {
while (a[next[fi[inter_type[k]]]].x <= qr[i].l) fi[inter_type[k]] = next[fi[inter_type[k]]];
res = std::max(res, std::min(to[inter_type[k]], std::min(abs(qr[i].l - a[fi[inter_type[k]]].x), a[next[fi[inter_type[k]]]].x - qr[i].l)));
to[inter_type[k]] = INF;
}
ans[qr[i].ind] = res > INF / 2 ? -1 : res;
}
}
for (int i = 0; i < q; ++i) printf("%d\n", ans[i]);
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:57:57: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
57 | for (int j = 0; j < n; ++j) if (a[j].l >= qr[i].y + 1 && a[j].l <= qr[until - 1].y || a[j].r >= qr[i].y + 1 && a[j].r <= qr[until - 1].y) {
| ~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:66:3: error: 'assert' was not declared in this scope
66 | assert(X < 3 * N);
| ^~~~~~
new_home.cpp:5:1: note: 'assert' is defined in header '<cassert>'; did you forget to '#include <cassert>'?
4 | #include <cstring>
+++ |+#include <cassert>
5 | #include <vector>
new_home.cpp:82:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | while (l == j || l <= n && amt < k - inter_type.size()) {
| ~~~~^~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:82:28: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
82 | while (l == j || l <= n && amt < k - inter_type.size()) {
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:37:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
37 | scanf("%d%d%d", &n, &k, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
42 | scanf("%d%d%d%d", &a[i].x, &a[i].t, &a[i].l, &a[i].r);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:48:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
48 | scanf("%d%d", &qr[i].l, &qr[i].y);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
