#include <bits/stdc++.h>
using namespace std::literals::string_literals;
using i64 = long long;
using std::cout;
using std::endl;
using std::cin;
template<typename T>
std::vector<T> make_v(size_t a){return std::vector<T>(a);}
template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
return std::vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}
struct LazySegmentTree {
std::vector<int> seg, lazy;
int sz = 1;
LazySegmentTree(int n) {
while(sz < n) sz <<= 1;
seg.assign(sz * 2 - 1, 0);
lazy.assign(sz * 2 - 1, 0);
}
void update(int k, int x) {
get(k, k + 1);
k += sz - 1;
seg[k] = x;
while(k) {
k = (k - 1) >> 1;
seg[k] = std::max(seg[2 * k + 1], seg[2 * k + 2]);
}
}
void push(int k) {
if(k < sz) {
lazy[2 * k + 1] += lazy[k];
lazy[2 * k + 2] += lazy[k];
}
seg[k] += lazy[k];
lazy[k] = 0;
}
int get(int a, int b, int k, int l, int r) {
push(k);
if(b <= l || r <= a) return 0;
if(a <= l && r <= b) return seg[k];
int L = get(a, b, 2 * k + 1, l, (l + r) >> 1);
int R = get(a, b, 2 * k + 2, (l + r) >> 1, r);
return std::max(L, R);
}
int get(int a, int b) {
return get(a, b, 0, 0, sz);
}
void add(int a, int b, int k, int l, int r, int x) {
push(k);
if(b <= l || r <= a) return;
if(a <= l && r <= b) {
lazy[k] += x;
push(k);
return;
}
add(a, b, 2 * k + 1, l, (l + r) >> 1, x);
add(a, b, 2 * k + 2, (l + r) >> 1, r, x);
seg[k] = std::max(seg[2 * k + 1], seg[2 * k + 2]);
}
void add(int a, int b, int x) {
add(a, b, 0, 0, sz, x);
};
int operator[](int k) {
return get(k, k + 1);
}
};
int main() {
int n, q, K; scanf("%d%d%d", &n, &K, &q);
std::vector<int> x(n), t(n), a(n), b(n), l(q), y(q);
for(int i = 0; i < n; i++) {
scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]); t[i]--;
}
for(int i = 0; i < q; i++) scanf("%d%d", &l[i], &y[i]);
std::function<int (std::set<std::pair<int, int>>&, int)> calcDist = [](std::set<std::pair<int, int>>& st, int t) {
auto it = st.lower_bound(std::make_pair(t, -1));
if(it == st.end()) it = std::prev(it);
if(it == st.begin()) return std::abs((*it).first - t);
return std::min(std::abs((*it).first - t),
std::abs((*std::prev(it)).first - t));
};
std::vector<int> ans(q, -1);
if(n <= 400 and q <= 400 and false) {
for(int i = 0; i < q; i++) {
std::vector<int> vec(K, 1 << 30);
for(int j = 0; j < n; j++) {
if(!(a[j] <= y[i] and y[i] <= b[j])) continue;
vec[t[j]] = std::min(vec[t[j]], std::abs(x[j] - l[i]));
}
for(int j = 0; j < K; j++) {
if(vec[j] == 1 << 30) {
ans[i] = -1;
break;
}
ans[i] = std::max(ans[i], vec[j]);
}
}
} else if(K <= 400 and false) {
std::vector<std::pair<int, int>> A, B;
for(int i = 0; i < n; i++) {
A.push_back({a[i], i});
B.push_back({b[i] + 1, i});
}
sort(begin(A), end(A)); sort(begin(B), end(B));
std::vector<std::pair<int, int>> query;
for(int i = 0; i < q; i++) query.push_back({y[i], i});
sort(begin(query), end(query));
int curA = 0, curB = 0;
std::vector<std::set<std::pair<int, int>>> vec(K);
for(auto YYS: query) {
int L = l[YYS.second], Y = y[YYS.second];
while(curA < A.size() and A[curA].first <= Y) {
int p = A[curA++].second;
vec[t[p]].insert({x[p], p});
}
while(curB < B.size() and B[curB].first <= Y) {
int p = B[curB++].second;
vec[t[p]].erase({x[p], p});
}
int ret = 0;
for(int k = 0; k < K; k++) {
if(vec[k].empty()) {
ret = -1;
break;
}
ret = std::max(ret, calcDist(vec[k], L));
}
ans[YYS.second] = ret;
}
} else {
for(int i = 0; i < n; i++) assert(a[i] == 1 and b[i] == 1e8);
std::vector<std::pair<int, std::pair<int, int>>> A;
std::vector<std::vector<int>> vec(K);
for(int i = 0; i < n; i++) {
vec[t[i]].push_back(x[i]);
A.push_back({x[i], {t[i], 1}});
}
for(int k = 0; k < K; k++) {
sort(begin(vec[k]), end(vec[k]));
A.push_back({(vec[k][0] + 1) >> 1, {k, 0}});
for(int i = 0; i < vec[k].size() - 1; i++) {
A.push_back({(vec[k][i] + vec[k][i + 1] + 1) >> 1, {k, 0}});
}
}
sort(begin(A), end(A));
std::vector<std::pair<int, int>> query(1, {0, 0});
for(int i = 0; i < q; i++) query.push_back({l[i], i});
sort(begin(query), end(query));
int cur = 0;
LazySegmentTree X(K), Y(K);
for(int i = 0; i < K; i++) Y.update(i, vec[i].front());
for(int i = 0; i < query.size(); i++) {
int L = query[i].first;
if(i) {
X.add(0, K, query[i].first - query[i - 1].first);
Y.add(0, K, query[i - 1].first - query[i].first);
}
while(cur < A.size() and A[cur].first <= L) {
int type = A[cur].second.second, p = A[cur].second.first, x = A[cur++].first;
if(type == 1) {
X.update(p, L - x);
Y.update(p, 0);
vec[p].erase(begin(vec[p]));
} else if(type == 0) {
Y.update(p, vec[p].front() - L);
X.update(p, 0);
}
}
/*
cout << "X: "; for(int j = 0; j < K; j++) cout << X[j] << " "; cout << endl;
cout << "Y: "; for(int j = 0; j < K; j++) cout << Y[j] << " "; cout << endl;
cout << endl;
*/
if(i) ans[query[i].second] = std::max(X.get(0, K), Y.get(0, K));
}
}
for(auto v: ans) printf("%d\n", v);
return 0;
}
/*
4 2 4
3 1 1 100000000
9 2 1 100000000
7 2 1 100000000
4 1 1 100000000
5 3
5 6
5 9
1 10
*/
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:124:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(curA < A.size() and A[curA].first <= Y) {
~~~~~^~~~~~~~~~
new_home.cpp:128:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(curB < B.size() and B[curB].first <= Y) {
~~~~~^~~~~~~~~~
new_home.cpp:156:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < vec[k].size() - 1; i++) {
~~^~~~~~~~~~~~~~~~~~~
new_home.cpp:169:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < query.size(); i++) {
~~^~~~~~~~~~~~~~
new_home.cpp:175:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(cur < A.size() and A[cur].first <= L) {
~~~~^~~~~~~~~~
new_home.cpp:75:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int n, q, K; scanf("%d%d%d", &n, &K, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:78:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d%d", &x[i], &t[i], &a[i], &b[i]); t[i]--;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:80:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
for(int i = 0; i < q; i++) scanf("%d%d", &l[i], &y[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
2 ms |
512 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 |
2 ms |
512 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 |
Correct |
1184 ms |
26412 KB |
Output is correct |
| 2 |
Incorrect |
1353 ms |
31612 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
242 ms |
16892 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 |
2 ms |
512 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 |
2 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
