#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...));
}
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));
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) {
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});
}
/*
cout << "YEAR: " << Y << endl;
for(int k = 0; k < K; k++) {
cout << k << ": ";
for(auto v: vec[k]) cout << v.second + 1 << " ";
cout << endl;
}
cout << endl;
*/
int ret = 0;
for(int k = 0; k < K; k++) {
if(vec[k].empty()) {
ret = -1;
break;
}
int mi = 1 << 30;
for(auto amber: vec[k]) mi = std::min(mi, std::abs(amber.first - L));
assert(mi == calcDist(vec[k], L));
ret = std::max(ret, mi);
}
ans[YYS.second] = ret;
}
} else {
assert(0);
}
for(auto v: ans) printf("%d\n", v);
return 0;
}
Compilation message
new_home.cpp: In function 'int main()':
new_home.cpp:63:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(curA < A.size() and A[curA].first <= Y) {
~~~~~^~~~~~~~~~
new_home.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(curB < B.size() and B[curB].first <= Y) {
~~~~~^~~~~~~~~~
new_home.cpp:17: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:20: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:22: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]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
209 ms |
16888 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Runtime error |
254 ms |
16880 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
256 KB |
Output is correct |
| 4 |
Runtime error |
3 ms |
512 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 5 |
Halted |
0 ms |
0 KB |
- |
