#include <bits/stdc++.h>
using namespace std;
const int N = (int) 4e6;
const int inf = (int) 1e9;
int mn[N], mx[N], sz;
void Build(int x, int l, int r) {
mn[x] = inf;
mx[x] = -inf;
if (l == r) {
return;
}
int mid = l + r >> 1;
Build(x << 1, l, mid);
Build(x << 1 | 1, mid + 1, r);
}
void ModifyMin(int x, int l, int r, int p, int v) {
if (l == r) {
mn[x] = v;
return;
}
int mid = l + r >> 1;
if (p <= mid) {
ModifyMin(x << 1, l, mid, p, v);
} else {
ModifyMin(x << 1 | 1, mid + 1, r, p, v);
}
mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
}
void ModifyMax(int x, int l, int r, int p, int v) {
if (l == r) {
mx[x] = v;
return;
}
int mid = l + r >> 1;
if (p <= mid) {
ModifyMax(x << 1, l, mid, p, v);
} else {
ModifyMax(x << 1 | 1, mid + 1, r, p, v);
}
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
}
void ChangeMin(int p, int v) {
ModifyMin(1, 0, sz - 1, p, v);
}
void ChangeMax(int p, int v) {
ModifyMax(1, 0, sz - 1, p, v);
}
int query_max(int x, int l, int r, int ll, int rr) {
if (l > r || l > rr || r < ll) {
return -inf;
}
if (ll <= l && r <= rr) {
return mx[x];
}
int mid = l + r >> 1;
return max(query_max(x << 1, l, mid, ll, rr), query_max(x << 1 | 1, mid + 1, r, ll, rr));
}
int query_min(int x, int l, int r, int ll, int rr) {
if (l > r || l > rr || r < ll) {
return inf;
}
if (ll <= l && r <= rr) {
return mn[x];
}
int mid = l + r >> 1;
return min(query_min(x << 1, l, mid, ll, rr), query_min(x << 1 | 1, mid + 1, r, ll, rr));
}
int get_max(int l, int r) {
return query_max(1, 0, sz - 1, l, r);
}
int get_min(int l, int r) {
return query_min(1, 0, sz - 1, l, r);
}
int readint() {
int x = 0;
char c = getchar();
while (c < '0' || c > '9') {
c = getchar();
}
while (c >= '0' && c <= '9') {
x = x * 10 + c - '0';
c = getchar();
}
return x;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n = readint(), k = readint(), q = readint();
//cin >> n >> k >> q;
vector<int> x(n);
vector<int> t(n);
vector<int> a(n);
vector<int> b(n);
map<pair<int, int>, vector<pair<int, int>>> mp;
for (int i = 0; i < n; i++) {
//cin >> x[i] >> t[i] >> a[i] >> b[i];
x[i] = readint();
t[i] = readint();
a[i] = readint();
b[i] = readint();
--t[i]; ++b[i];
mp[{x[i], t[i]}].emplace_back(a[i], b[i]);
}
vector<int> new_x;
vector<int> new_t;
vector<int> new_a;
vector<int> new_b;
for (auto& p : mp) {
vector<pair<int, int>> v = p.second;
sort(v.begin(), v.end());
int sz = (int) v.size();
for (int i = 0; i < sz; i++) {
int ptr = i;
int mx = v[i].second;
while (ptr + 1 < sz && v[ptr + 1].first < mx) {
ptr += 1;
mx = max(mx, v[ptr].second);
}
new_x.push_back(p.first.first);
new_t.push_back(p.first.second);
new_a.push_back(v[i].first);
new_b.push_back(mx);
i = ptr;
}
}
x = new_x;
t = new_t;
a = new_a;
b = new_b;
n = (int) x.size();
vector<int> l(q);
vector<int> y(q);
for (int i = 0; i < q; i++) {
cin >> l[i] >> y[i];
}
vector<int> xs(1, 1e9);
for (int i = 0; i < n; i++) {
xs.push_back(a[i]);
xs.push_back(b[i]);
}
for (int i = 0; i < q; i++) {
xs.push_back(y[i]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (int i = 0; i < n; i++) {
a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin());
b[i] = (int) (lower_bound(xs.begin(), xs.end(), b[i]) - xs.begin());
}
for (int i = 0; i < q; i++) {
y[i] = (int) (lower_bound(xs.begin(), xs.end(), y[i]) - xs.begin());
}
int T = (int) xs.size();
vector<vector<int>> ids(T);
for (int i = 0; i < n; i++) {
ids[a[i]].push_back(i);
ids[b[i]].push_back(~i);
}
vector<multiset<tuple<int, int, int>>> open(k);
vector<array<int, 4>> ev;
vector<multiset<int>> my(k);
auto Insert = [&](int t, int x, int y) {
auto ptr = my[t].lower_bound(x);
if (ptr != my[t].begin() && ptr != my[t].end()) {
auto it = open[t].lower_bound({*prev(ptr), *ptr, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open[t].erase(it);
} else if (ptr != my[t].begin()) {
auto it = open[t].lower_bound({*prev(ptr), inf, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open[t].erase(it);
} else if (ptr != my[t].end()) {
auto it = open[t].lower_bound({-inf, *ptr, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open[t].erase(it);
}
if (ptr != my[t].end()) {
open[t].emplace(x, *ptr, y);
} else {
open[t].emplace(x, inf, y);
}
if (ptr != my[t].begin()) {
ptr = prev(ptr);
open[t].emplace(*ptr, x, y);
} else {
open[t].emplace(-inf, x, y);
}
my[t].insert(x);
};
auto Remove = [&](int t, int x, int y) {
auto ptr = my[t].lower_bound(x);
if (ptr != prev(my[t].end())) {
auto it = open[t].lower_bound({x, *next(ptr), -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open[t].erase(it);
} else {
auto it = open[t].lower_bound({x, inf, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open[t].erase(it);
}
if (ptr != my[t].begin()) {
auto it = open[t].lower_bound({*prev(ptr), x, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open[t].erase(it);
} else {
auto it = open[t].lower_bound({-inf, x, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open[t].erase(it);
}
if (ptr != my[t].begin() && ptr != prev(my[t].end())) {
open[t].emplace(*prev(ptr), *next(ptr), y);
} else if (ptr != my[t].begin()) {
open[t].emplace(*prev(ptr), inf, y);
} else if (ptr != prev(my[t].end())) {
open[t].emplace(-inf, *next(ptr), y);
}
my[t].erase(my[t].find(x));
};
for (int i = 0; i < T; i++) {
sort(ids[i].begin(), ids[i].end());
for (int j : ids[i]) {
if (j >= 0) {
Insert(t[j], x[j], i);
} else {
j = ~j;
Remove(t[j], x[j], i);
}
}
}
for (int i = 0; i < k; i++) {
for (auto& p : open[i]) {
ev.push_back({get<0>(p), get<1>(p), get<2>(p), T - 1});
}
}
vector<vector<int>> qs(T);
for (int i = 0; i < q; i++) {
qs[y[i]].push_back(i);
}
vector<pair<int, int>> min_with;
vector<pair<int, int>> max_with;
for (auto& p : ev) {
int L = p[0];
int R = p[1];
int mid = (L + R) / 2;
min_with.emplace_back(L, mid);
max_with.emplace_back(R, mid + (L % 2 != R % 2));
}
sort(min_with.begin(), min_with.end(), [&](pair<int, int> p, pair<int, int> q) {
return p.second > q.second;
});
sort(max_with.begin(), max_with.end(), [&](pair<int, int> p, pair<int, int> q) {
return p.second < q.second;
});
map<pair<int, int>, vector<int>> idx_mn;
map<pair<int, int>, vector<int>> idx_mx;
sz = (int) ev.size();
for (int i = 0; i < sz; i++) {
idx_mn[min_with[i]].push_back(i);
}
for (int i = 0; i < sz; i++) {
idx_mx[max_with[i]].push_back(i);
}
vector<vector<int>> qs_mn(T);
vector<vector<int>> qs_mx(T);
for (int i = 0; i < sz; i++) {
int L = ev[i][0];
int R = ev[i][1];
int from = ev[i][2];
int to = ev[i][3];
int mid = (L + R) / 2;
{
int idx = idx_mn[{L, mid}].back();
idx_mn[{L, mid}].pop_back();
qs_mn[from].push_back(idx);
qs_mn[to].push_back(~idx);
}
{
int idx = idx_mx[{R, mid + (L % 2 != R % 2)}].back();
idx_mx[{R, mid + (L % 2 != R % 2)}].pop_back();
qs_mx[from].push_back(idx);
qs_mx[to].push_back(~idx);
}
}
Build(1, 0, sz - 1);
vector<int> res(q);
for (int i = 0; i < T; i++) {
for (int j : qs_mn[i]) {
if (j >= 0) {
ChangeMin(j, min_with[j].first);
} else {
j = ~j;
ChangeMin(j, inf);
}
}
for (int j : qs_mx[i]) {
if (j >= 0) {
ChangeMax(j, max_with[j].first);
} else {
j = ~j;
ChangeMax(j, -inf);
}
}
for (int j : qs[i]) {
{
int low = 0, high = sz - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (min_with[mid].second >= l[j]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
res[j] = max(res[j], l[j] - get_min(0, pos));
}
}
{
int low = 0, high = sz - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (max_with[mid].second <= l[j]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
res[j] = max(res[j], get_max(0, pos) - l[j]);
}
}
}
}
vector<vector<int>> qs_type(T);
for (int i = 0; i < n; i++) {
qs_type[a[i]].push_back(t[i]);
qs_type[b[i]].push_back(~t[i]);
}
int bal = 0;
vector<int> cnt(k);
for (int i = 0; i < T; i++) {
for (int j : qs_type[i]) {
if (j >= 0) {
cnt[j] += 1;
if (cnt[j] == 1) {
bal += 1;
}
} else {
j = ~j;
cnt[j] -= 1;
if (cnt[j] == 0) {
bal -= 1;
}
}
}
for (int j : qs[i]) {
if (bal != k) {
res[j] = -1;
}
}
}
for (int i = 0; i < q; i++) {
cout << res[i] << '\n';
}
return 0;
}
/*
4 2 4
3 1 1 10
9 2 2 4
7 2 5 7
4 1 8 10
5 3
5 6
5 9
1 10
2 1 3
1 1 1 4
1 1 2 6
1 3
1 5
1 7
1 1 1
100000000 1 1 1
1 1
*/
Compilation message
new_home.cpp: In function 'void Build(int, int, int)':
new_home.cpp:17:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
17 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'void ModifyMin(int, int, int, int, int)':
new_home.cpp:27:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
27 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'void ModifyMax(int, int, int, int, int)':
new_home.cpp:41:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
41 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'int query_max(int, int, int, int, int)':
new_home.cpp:65:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
65 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'int query_min(int, int, int, int, int)':
new_home.cpp:76:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
76 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:323:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
323 | int mid = low + high >> 1;
| ~~~~^~~~~~
new_home.cpp:338:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
338 | int mid = low + high >> 1;
| ~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2741 ms |
304184 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5044 ms |
418680 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
2396 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
