#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
constexpr int inf = 1000000100;
#define REP(i, n) for (int i = 0; i < (n); ++i)
#define REP3(i, l, r) for (int i = (l); i < (r); ++i)
#define RVP(i, n) for (int i = (n - 1); i >= 0; --i)
#define ALL(x) (x).begin(), (x).end()
struct PriqueErase {
priority_queue<int, vector<int>, greater<int>> a, b;
void push(int x) { a.push(x); }
void erase(int x) { b.push(x); }
int top() {
while (not a.empty()) {
const int v = a.top();
if (b.empty()) {
return v;
} else if (v == b.top()) {
a.pop();
b.pop();
} else {
return v;
}
}
return inf;
}
};
struct RIEPM {
int n, siz;
vector<PriqueErase> data;
RIEPM(int n_) : n(n_) {
siz = 1;
while (siz < n) siz <<= 1;
data.assign(2 * siz, PriqueErase());
}
void push(int l, int r, int v) {
assert(0 <= l and l <= r and r <= n);
for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) {
if (l & 1) data[l++].push(v);
if (r & 1) data[--r].push(v);
}
}
void erase(int l, int r, int v) {
assert(0 <= l and l <= r and r <= n);
for (l += siz, r += siz; l < r; l >>= 1, r >>= 1) {
if (l & 1) data[l++].erase(v);
if (r & 1) data[--r].erase(v);
}
}
int top(int i) {
assert(0 <= i and i < n);
i += siz;
int res = inf;
while (i != 0) {
res = min(res, data[i].top());
i >>= 1;
}
return res;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K, Q;
cin >> N >> K >> Q;
vector<int> X(N), T(N), A(N), B(N);
REP(i, N) {
cin >> X[i] >> T[i] >> A[i] >> B[i];
--T[i];
}
vector<int> L(Q), Y(Q);
REP(i, Q) cin >> L[i] >> Y[i];
auto reverse_points = [&]() {
REP(i, N) X[i] = inf - X[i];
REP(i, Q) L[i] = inf - L[i];
};
auto solve = [&]() {
vector<int> press;
REP(i, N) press.push_back(X[i]);
REP(i, N) press.push_back(L[i]);
sort(ALL(press));
press.erase(unique(ALL(press)), press.end());
auto get_key = [&](int i) { return (int)(lower_bound(ALL(press), i) - press.begin()); };
const int M = (int)press.size();
RIEPM hp(M);
vector<tuple<int, int, int, int>> event;
REP(i, N) {
event.push_back({A[i], 0, X[i], T[i]});
event.push_back({B[i] + 1, 1, X[i], T[i]});
}
REP(i, Q) event.push_back({Y[i], 2, L[i], i});
sort(ALL(event));
vector<multiset<int>> pd(K);
vector<int> res(Q, -1);
int cnt_zero = K;
for (const auto &[c, qt, p, i] : event) {
if (qt == 0) {
if (pd[i].empty()) --cnt_zero;
if (pd[i].find(p) != pd[i].end()) {
pd[i].insert(p);
continue;
}
auto itr = pd[i].insert(p);
auto itr_r = itr;
++itr_r;
if (itr_r == pd[i].end()) {
hp.push(get_key(p), M, p);
} else {
hp.push(get_key(p), get_key((p + *itr_r + 2) / 2), p);
}
if (itr == pd[i].begin()) continue;
auto itr_l = itr;
--itr_l;
if (itr_r != pd[i].end()) {
hp.erase(get_key(*itr_l), get_key((*itr_l + *itr_r + 2) / 2), *itr_l);
} else {
hp.erase(get_key(*itr_l), M, *itr_l);
}
hp.push(get_key(*itr_l), get_key((*itr_l + p + 2) / 2), *itr_l);
}
if (qt == 1) {
if (pd[i].size() == 1) ++cnt_zero;
pd[i].erase(pd[i].find(p));
if (pd[i].find(p) != pd[i].end()) {
continue;
}
auto itr_r = pd[i].lower_bound(p);
if (itr_r != pd[i].end()) {
hp.erase(get_key(p), get_key((p + *itr_r + 2) / 2), p);
} else {
hp.erase(get_key(p), M, p);
}
if (itr_r == pd[i].begin()) continue;
auto itr_l = itr_r;
--itr_l;
hp.erase(get_key(*itr_l), get_key((*itr_l + p + 2) / 2), *itr_l);
if (itr_r != pd[i].end()) {
hp.push(get_key(*itr_l), get_key((*itr_l + *itr_r + 2) / 2), *itr_l);
} else {
hp.push(get_key(*itr_l), M, *itr_l);
}
}
if (qt == 2) {
if (cnt_zero != 0) continue;
const int pi = get_key(p);
const int vi = hp.top(get_key(pi));
if (vi == inf) continue;
res[i] = p - vi;
}
}
return res;
};
const auto res1 = solve();
reverse_points();
const auto res2 = solve();
REP(i, Q) {
const int ans = max(res1[i], res2[i]);
cout << ans << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4759 ms |
290932 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5109 ms |
309456 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Correct |
1 ms |
320 KB |
Output is correct |
| 3 |
Correct |
1 ms |
212 KB |
Output is correct |
| 4 |
Incorrect |
1 ms |
316 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
