#pragma GCC target("avx2")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#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;
}
};
int cnt_sp[2000000];
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 replace(int l, int r1, int r2, int v) {
assert(0 <= l and l <= r1 and l <= r2 and r1 <= n and r2 <= n);
vector<int> vs;
for (int li = l + siz, ri = r1 + siz; li < ri; li >>= 1, ri >>= 1) {
if (li & 1) {
++cnt_sp[li++];
vs.push_back(li - 1);
}
if (ri & 1) {
++cnt_sp[--ri];
vs.push_back(ri);
}
}
for (int li = l + siz, ri = r2 + siz; li < ri; li >>= 1, ri >>= 1) {
if (li & 1) {
--cnt_sp[li++];
vs.push_back(li - 1);
}
if (ri & 1) {
--cnt_sp[--ri];
vs.push_back(ri);
}
}
for (const int i : vs) {
if (cnt_sp[i] == 1) data[i].push(v);
if (cnt_sp[i] == -1) data[i].erase(v);
cnt_sp[i] = 0;
}
}
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);
fill(cnt_sp, cnt_sp + 2000000, 0);
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, Q) 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<map<int, 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;
auto [itr, vld] = pd[i].insert({p, 1});
if (not vld) {
++itr->second;
continue;
}
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->first + 2) / 2), p);
}
if (itr == pd[i].begin()) continue;
auto itr_l = itr;
--itr_l;
const int l_id = get_key(itr_l->first);
if (itr_r != pd[i].end()) {
hp.replace(l_id, get_key((itr_l->first + p + 2) / 2),
get_key((itr_l->first + itr_r->first + 2) / 2), itr_l->first);
} else {
hp.replace(l_id, get_key((itr_l->first + p + 2) / 2), M, itr_l->first);
}
}
if (qt == 1) {
auto itr = pd[i].find(p);
if (--(itr->second) != 0) {
continue;
}
pd[i].erase(p);
if (pd[i].empty()) ++cnt_zero;
auto itr_r = pd[i].upper_bound(p);
if (itr_r != pd[i].end()) {
hp.erase(get_key(p), get_key((p + itr_r->first + 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;
const int l_id = get_key(itr_l->first);
if (itr_r != pd[i].end()) {
hp.replace(l_id, get_key((itr_l->first + itr_r->first + 2) / 2),
get_key((itr_l->first + p + 2) / 2), itr_l->first);
} else {
hp.replace(l_id, M, get_key((itr_l->first + p + 2) / 2), itr_l->first);
}
}
if (qt == 2) {
if (cnt_zero != 0) continue;
const int pi = get_key(p);
const int vi = hp.top(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 |
4 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
8148 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
8148 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3640 ms |
205636 KB |
Output is correct |
| 2 |
Incorrect |
3165 ms |
178996 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5042 ms |
203440 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
8148 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
4 ms |
8020 KB |
Output is correct |
| 2 |
Correct |
4 ms |
8148 KB |
Output is correct |
| 3 |
Correct |
3 ms |
8148 KB |
Output is correct |
| 4 |
Incorrect |
9 ms |
8148 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
