#include <bits/stdc++.h>
using namespace std;
class bag {
private:
vector<multiset<long long>> g;
public:
bag(long long k) {
g.resize(k);
}
void add(long long idx, long long k) {
g[k].insert(idx);
}
void rem(long long idx, long long k) {
g[k].erase(g[k].find(idx));
}
//long long qry(long long lx, long long rx) {
//}
long long qry(long long x) {
for (long long k = 0; k < (long long) g.size(); k++) {
if (g[k].empty()) {
return -1;
}
}
long long ans = 0;
for (long long k = 0; k < (long long) g.size(); k++) {
auto lo = g[k].lower_bound(x);
if (lo == g[k].end()) {
ans = max(ans, abs(x - *prev(lo)));
} else if (lo == g[k].begin()) {
ans = max(ans, abs(x - *lo));
} else {
ans = max(ans, abs(x - *lo));
ans = max(ans, abs(x - *prev(lo)));
}
}
return ans;
}
};
const long long start = 0;
const long long query = 1;
const long long endd = 2;
class E {
public:
long long op, x, ty, ti;
E(long long opp, long long xx, long long tyy, long long tii) {
op = opp;
x = xx;
ty = tyy;
ti = tii;
}
bool operator <(const E& o) {
if (ti == o.ti) {
return op < o.op;
}
return ti < o.ti;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
long long n, k, q;
cin >> n >> k >> q;
vector<E> events;
for (long long i = 0; i < n; i++) {
long long x, t, a, b;
cin >> x >> t >> a >> b;
--t;
events.emplace_back(E(start, x, t, a));
events.emplace_back(E(endd, x, t, b));
}
for (long long i = 0; i < q; i++) {
long long l, y;
cin >> l >> y;
events.emplace_back(E(query, l, i, y));
}
sort(events.begin(), events.end());
vector<long long> ans(q);
bag mrsrtr(k);
for (long long i = 0; i < (long long) events.size(); i++) {
if (events[i].op == start) {
mrsrtr.add(events[i].x, events[i].ty);
} else if (events[i].op == query) {
//long long l = -1, r = 1e8;
//while (r - l > 1) {
//long long mid = (l + r) >> 1;
//if (mrsrtr.qry(max(events[i].x - mid, 0), min(events[i].x + mid, (long long) 1e8)) == k) {
//r = mid;
//} else {
//l = mid;
//}
long long r = mrsrtr.qry(events[i].x);
ans[events[i].ty] = r;
//}
} else {
mrsrtr.rem(events[i].x, events[i].ty);
}
}
for (long long x : ans) {
cout << x << '\n';
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5079 ms |
47748 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5095 ms |
45136 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
1 ms |
204 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
204 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
