#include <bits/stdc++.h>
using namespace std;
using qt = array<int, 6>;
const int N = 310000;
const int M = (int)(1e8);
struct chash {
int operator()(array<int, 2> tt) const {
return tt[0] * 3049034234 + tt[1];
}
};
int n, k, q, x[N], t[N], a[N], b[N], ans[N];
multiset<int> st[N];
unordered_map<array<int, 2>, vector<int>, chash> bw, fw; // pos; val; time
vector<array<int, 3>> ev;
vector<qt> qq;
/*
type = 0; pos; dir (bw = 0, fw = 1); val; time_left; time_right;
type = 1; pos; time; query_id; 0; 0;
*/
void solve(int l, int r, vector<qt> qq) {
if (qq.empty()) return;
int last = -M, val = 0;
for (int i = 0; i < (int) qq.size(); i++) {
if (qq[i][0] == 0) {
if (qq[i][4] > l || qq[i][5] < r || qq[i][2] == 0)
continue;
val -= qq[i][1] - last;
last = qq[i][1];
val = max(val, qq[i][3]);
} else {
val -= qq[i][1] - last;
last = qq[i][1];
ans[qq[i][3]] = max(ans[qq[i][3]], val);
}
}
last = M + M, val = 0;
for (int i = qq.size() - 1; i >= 0; i--) {
if (qq[i][0] == 0) {
if (qq[i][4] > l || qq[i][5] < r || qq[i][2] == 1)
continue;
val -= last - qq[i][1];
last = qq[i][1];
val = max(val, qq[i][3]);
} else {
val -= last - qq[i][1];
last = qq[i][1];
ans[qq[i][3]] = max(ans[qq[i][3]], val);
}
}
if (l == r) return;
vector<qt> ql, qr;
int mid = (l + r) / 2;
for (auto tt : qq) {
if (tt[0] == 0) {
if (tt[4] <= l && tt[5] >= r)
continue;
if (tt[4] <= mid)
ql.push_back(tt);
if (tt[5] >= mid + 1)
qr.push_back(tt);
} else {
if (tt[2] <= mid)
ql.push_back(tt);
if (tt[2] >= mid + 1)
qr.push_back(tt);
}
}
qq.clear();
qq.shrink_to_fit();
solve(l, mid, ql);
solve(mid + 1, r, qr);
}
void fin(int l, int r, int t) {
int mid = (l + r + M + M) / 2 - M;
int val1 = mid - l;
int t1 = bw[{mid, val1}].back();
bw[{mid, val1}].pop_back();
if (t1 <= t) qq.push_back({0, mid, 0, val1, t1, t});
int val2 = r - mid - 1;
int t2 = fw[{mid + 1, val2}].back();
fw[{mid + 1, val2}].pop_back();
if (t2 <= t) qq.push_back({0, mid + 1, 1, val2, t2, t});
}
void beg(int l, int r, int t) {
int mid = (l + r + M + M) / 2 - M;
bw[{mid, mid - l}].push_back(t);
fw[{mid + 1, r - mid - 1}].push_back(t);
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
cin >> n >> k >> q;
for (int i = 1; i <= n; i++) {
cin >> x[i] >> t[i] >> a[i] >> b[i];
ev.push_back({a[i], x[i], t[i]});
ev.push_back({-b[i], x[i], t[i]});
}
sort(begin(ev), end(ev), [&] (auto x, auto y) {
return abs(x[0]) < abs(y[0]) || (abs(x[0]) == abs(y[0]) && x[0] > y[0]);
});
for (int i = 1; i <= k; i++) {
st[i].insert(-M);
st[i].insert(M + M);
beg(-M, M + M, 0);
}
for (auto [a, x, t] : ev) {
if (a > 0) {
int pl = -1, pr = -1;
auto it = st[t].lower_bound(x);
pr = *it;
pl = *prev(it);
fin(pl, pr, a - 1);
beg(pl, x, a);
beg(x, pr, a);
st[t].insert(x);
} else {
int pl = -1, pr = -1;
auto it = st[t].lower_bound(x);
pr = *next(it);
pl = *prev(it);
fin(pl, x, -a);
fin(x, pr, -a);
beg(pl, pr, -a + 1);
st[t].extract(x);
}
}
for (int i = 1; i <= k; i++)
fin(-M, M + M, M);
for (int i = 1; i <= q; i++) {
int l, y; cin >> l >> y;
qq.push_back({1, l, y, i, 0, 0});
ans[i] = 0;
}
sort(begin(qq), end(qq), [&](auto i, auto j) {
int tpi = (i[0] == 1 ? 1 : (i[2] == 1 ? 0 : 2));
int tpj = (j[0] == 1 ? 1 : (j[2] == 1 ? 0 : 2));
return i[1] < j[1] || (i[1] == j[1] && tpi < tpj);
});
solve(1, M, qq);
for (int i = 1; i <= q; i++) {
if (ans[i] >= M) ans[i] = -1;
cout << ans[i] << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |