#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;
};
struct U {
int l, r;
pair<int, pair<int, int>> p;
};
const int N = 3e5 + 5, INF = 1e9, MAX = 1e8;
int n, q, k, cq, cc;
int ans[N];
pair<int, int> lt[N], tmp[N];
map<pair<int, int>, vector<int>> mp[N];
bool ok[N];
vector<int> vx;
multiset<int> occ[N];
vector<pair<int, pair<int, int>>> t[N * 4];
vector<U> updates;
void upd(int l, int r, pair<int, 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);
}
}
bool dummy(int y) {
return abs(y) == INF || abs(INF - y) == INF;
}
void startSeg(int x, pair<int, int> y) {
if (dummy(y.first))
return;
mp[x][y].push_back(cq);
}
void endSeg(int x, pair<int, int> y) {
if (dummy(y.first))
return;
auto &v = mp[x][y];
if (v.size() == 1)
updates.push_back({v.back(), cq - 1, {x, y}});
v.pop_back();
}
void updBetween(int x, int y, bool add) {
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, INF - x});
else
endSeg(m1, {y, INF - x});
}
void calcAns(int v, int L, int R) {
if (L == R) {
tmp[0] = lt[L];
}
else {
int m = (L + R) >> 1;
calcAns(v * 2, L, m);
calcAns(v * 2 + 1, m + 1, R);
int x = L, y = m + 1, z = 0;
while (x <= m || y <= R) {
if (x <= m && (y == R + 1 || lt[x].first < lt[y].first))
tmp[z] = lt[x++];
else
tmp[z] = lt[y++];
z++;
}
for (int i = L; i <= R; i++)
lt[i] = tmp[i - L];
}
int i = 0, mx = -INF;
for (int j = 0; j <= R - L; j++) {
while (i < t[v].size() && t[v][i].first <= tmp[j].first) {
mx = max(mx, t[v][i].second.first);
i++;
}
ans[tmp[j].second] = max(ans[tmp[j].second], mx - vx[tmp[j].first]);
}
reverse(tmp, tmp + R - L + 1);
for (int j = 0; j <= R - L; j++)
tmp[j].first = cc - 1 - tmp[j].first;
// for (auto p : t[v]) {
// cout << p.first << " " << p.second << "\n";
// }
reverse(all(t[v]));
for (auto &p : t[v]) {
p.first = cc - p.first;
}
i = 0, mx = -INF;
for (int j = 0; j <= R - L; j++) {
while (i < t[v].size() && t[v][i].first <= tmp[j].first) {
mx = max(mx, t[v][i].second.second);
i++;
}
ans[tmp[j].second] = max(ans[tmp[j].second], mx - INF + vx[cc - 1 - tmp[j].first]);
}
}
void calcUpdates(vector<E> &evs) {
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;
int types_on = 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);
updBetween(*prev(it), *it, false);
if (occ[e.y].size() == 2)
types_on++;
it = occ[e.y].insert(e.x);
updBetween(*prev(it), e.x, true);
updBetween(e.x, *next(it), true);
}
else if (e.t == 1) {
auto it = occ[e.y].find(e.x);
updBetween(*prev(it), *it, false);
updBetween(*it, *next(it), false);
updBetween(*prev(it), *next(it), true);
occ[e.y].erase(it);
if (occ[e.y].size() == 2)
types_on--;
}
else {
ok[e.y] = (types_on == k);
lt[cq++] = {lower_bound(all(vx), e.x) - vx.begin(), e.y};
}
}
sort(all(updates), [](const U &a, const U &b) {
return a.p.first < b.p.first;
});
}
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});
}
for (int i = 0; i < q; i++) {
int x, y;
cin >> x >> y;
evs.push_back({y, 2, x, i});
}
for (int i = 0; i < k; i++) {
occ[i].insert(-INF);
occ[i].insert(INF);
}
sort(all(evs), [](const E &a, const E &b) {
return a.p == b.p ? a.t < b.t : a.p < b.p;
});
calcUpdates(evs);
for (U &u : updates) {
upd(u.l, u.r, u.p, 1, 0, q - 1);
}
calcAns(1, 0, q - 1);
for (int i = 0; i < q; i++) {
if (ok[i]) {
cout << ans[i] << "\n";
}
else {
cout << "-1\n";
}
}
return 0;
}
Compilation message
new_home.cpp: In function 'void calcAns(int, int, int)':
new_home.cpp:99:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i < t[v].size() && t[v][i].first <= tmp[j].first) {
~~^~~~~~~~~~~~~
new_home.cpp:124:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (i < t[v].size() && t[v][i].first <= tmp[j].first) {
~~^~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
56696 KB |
Output is correct |
| 2 |
Correct |
55 ms |
56824 KB |
Output is correct |
| 3 |
Correct |
54 ms |
56696 KB |
Output is correct |
| 4 |
Incorrect |
56 ms |
56696 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
56696 KB |
Output is correct |
| 2 |
Correct |
55 ms |
56824 KB |
Output is correct |
| 3 |
Correct |
54 ms |
56696 KB |
Output is correct |
| 4 |
Incorrect |
56 ms |
56696 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2373 ms |
183392 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4312 ms |
301380 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
56696 KB |
Output is correct |
| 2 |
Correct |
55 ms |
56824 KB |
Output is correct |
| 3 |
Correct |
54 ms |
56696 KB |
Output is correct |
| 4 |
Incorrect |
56 ms |
56696 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
55 ms |
56696 KB |
Output is correct |
| 2 |
Correct |
55 ms |
56824 KB |
Output is correct |
| 3 |
Correct |
54 ms |
56696 KB |
Output is correct |
| 4 |
Incorrect |
56 ms |
56696 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
