This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
#define all(aaa) aaa.begin(), aaa.end()
using namespace std;
struct E {
int p, t, x, y;
};
const int N = 3e5 + 5, INF = 1e9, MAX = 1e8;
int n, q, k, cc, cq;
int ans[N], loc[N], num[N];
vector<int> vx;
multiset<int> occ[N];
map<pair<int, int>, vector<int>> mp;
vector<pair<int, int>> t[N * 4];
struct ST {
vector<int> t[N];
ST() {
fill(t, t + N, vector<int>{-INF});
}
void upd(int x, int y) {
for (; x < N; x |= x + 1)
t[x].push_back(max(t[x].back(), y));
}
int que(int x) {
int ans = -INF;
for (; x >= 0; x = (x & (x + 1)) - 1)
ans = max(ans, t[x].back());
return ans;
}
void del(int x) {
for (; x < N; x |= x + 1)
t[x].pop_back();
}
} fent;
void upd(int l, int r, pair<int, int> p, int v, int L, int R) {
if (l > r)
return;
if (L == l && R == r) {
t[v].push_back(p);
}
else {
int m = (L + R) >> 1;
upd(l, min(m, r), p, v * 2, L, m);
upd(max(m + 1, l), r, p, v * 2 + 1, m + 1, R);
}
}
void startSeg(int x, int y) {
mp[{x, y}].push_back(cq);
}
void endSeg(int x, int y) {
// cout << "!" << x << " " << y << "\n";
auto p = make_pair(x, y);
upd(mp[{x, y}].back(), cq - 1, p, 1, 0, q - 1);
// cout << "SEG_END " << mp[{x, y}].back() << " " << cq - 1 << " " << x << " " << y << "\n";
mp[{x, y}].pop_back();
}
void updBeg(int x, bool add) {
// cout << "BEG " << x << " " << add << "\n";
if (add)
startSeg(0, x);
else
endSeg(0, x);
}
void updBetween(int x, int y, bool add) {
// cout << "BET " << x << " " << y << " " << add << "\n";
if (x == y)
return;
int m = (x + y) / 2;
if ((x + y) % 2)
m++;
int m1 = lower_bound(all(vx), m) - vx.begin();
if (add)
startSeg(m1, y);
else
endSeg(m1, y);
}
void calcAns(int v, int L, int R) {
for (auto &p : t[v]) {
fent.upd(p.first, p.second);
}
if (L == R) {
ans[num[L]] = max(ans[num[L]], fent.que(loc[L]) - vx[loc[L]]);
}
else {
int m = (L + R) >> 1;
calcAns(v * 2, L, m);
calcAns(v * 2 + 1, m + 1, R);
}
for (auto &p : t[v]) {
fent.del(p.first);
}
}
void solve(vector<E> evs) {
vx.clear();
mp.clear();
for (int i = 0; i < N; i++) {
occ[i].clear();
}
for (int i = 0; i < N * 4; i++) {
t[i].clear();
}
for (E e : evs) {
if (e.t == 2)
vx.push_back(e.x);
}
sort(all(vx));
vx.erase(unique(all(vx)), vx.end());
cc = vx.size();
cq = 0;
for (E e : evs) {
// cout << e.p << " " << e.t << " " << e.x << " " << e.y << "\n";
if (e.t == 0) {
auto it = occ[e.y].upper_bound(e.x);
if (!occ[e.y].empty()) {
if (it != occ[e.y].begin() && it != occ[e.y].end()) {
updBetween(*prev(it), *it, false);
}
if (it == occ[e.y].begin()) {
updBeg(*it, false);
}
}
it = occ[e.y].insert(e.x);
if (it == occ[e.y].begin())
updBeg(*it, true);
else
updBetween(*prev(it), *it, true);
if (next(it) != occ[e.y].end())
updBetween(*it, *next(it), true);
}
else if (e.t == 1) {
auto it = occ[e.y].find(e.x);
if (it == occ[e.y].begin())
updBeg(*it, false);
else
updBetween(*prev(it), *it, false);
if (next(it) != occ[e.y].end())
updBetween(*it, *next(it), false);
if (it != occ[e.y].begin() && next(it) != occ[e.y].end())
updBetween(*prev(it), *next(it), true);
if (it == occ[e.y].begin() && occ[e.y].size() > 1)
updBeg(*next(it), true);
occ[e.y].erase(it);
}
else {
loc[cq] = lower_bound(all(vx), e.x) - vx.begin();
num[cq] = e.y;
cq++;
}
}
calcAns(1, 0, q - 1);
}
signed main() {
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cin >> n >> k >> q;
vector<E> evs;
for (int i = 0; i < n; i++) {
int x, t, a, b;
cin >> x >> t >> a >> b;
t--;
evs.push_back({a, 0, x, t});
evs.push_back({b + 1, 1, x, t});
vx.push_back(x);
}
for (int i = 0; i < k; i++) {
evs.push_back({1, 0, INF, i});
evs.push_back({MAX, 1, INF, i});
}
for (int i = 0; i < q; i++) {
int x, y;
cin >> x >> y;
evs.push_back({y, 2, x, i});
}
sort(all(evs), [](const E &a, const E &b) {
return a.p == b.p ? a.t < b.t : a.p < b.p;
});
solve(evs);
for (E &e : evs)
e.x = INF - e.x;
solve(evs);
for (int i = 0; i < q; i++) {
if (ans[i] < INF / 2) {
cout << ans[i] << "\n";
}
else {
cout << "-1\n";
}
}
return 0;
}
# | 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... |