#include <bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree <T, null_type, less <T>, rb_tree_tag, tree_order_statistics_node_update>;
const int N = 3e5 + 10;
int n, k, q;
multiset <int> s[N];
int ans[N];
int cnt, nNode = 1;
void go(int& x) {
if (!x) x = ++nNode;
}
struct node {
int lhs, rhs;
multiset <int> lft, rgt;
} st[N * 50];
int ok;
void upd(int id, int L, int R, int u, int v, int a, int b, int mode) {
if (u > R || L > v) return;
if (u <= L && R <= v) {
if (a < 0) {
if (mode > 0) st[id].lft.insert(b);
else st[id].lft.erase(st[id].lft.find(b));
} else {
if (mode > 0) st[id].rgt.insert(b);
else st[id].rgt.erase(st[id].rgt.find(b));
}
return;
}
int mid = L + R >> 1;
go(st[id].lhs), go(st[id].rhs);
upd(st[id].lhs, L, mid, u, v, a, b, mode);
upd(st[id].rhs, mid + 1, R, u, v, a, b, mode);
}
void solve(int id, int L, int R, int x, int &ans) {
if (st[id].rgt.size()) ans = max(ans, x / 2 + *(--st[id].rgt.end()));
if (st[id].lft.size()) ans = max(ans, - x / 2 + *(--st[id].lft.end()));
if (L == R) return;
int mid = L + R >> 1;
if (x <= mid) {
if (st[id].lhs) solve(st[id].lhs, L, mid, x, ans);
} else {
if (st[id].rhs) solve(st[id].rhs, mid + 1, R, x, ans);
}
}
void add(int t, int x) {
cnt -= (s[t].size() == 2);
int L = *(--s[t].upper_bound(x));
int R = *s[t].upper_bound(x);
upd(1, - 4e8, 4e8, L * 2, L + R, 1, - L, -1);
upd(1, - 4e8, 4e8, L + R, R * 2, -1, R, -1);
upd(1, - 4e8, 4e8, L * 2, L + x, 1, - L, 1);
upd(1, - 4e8, 4e8, L + x, x * 2, -1, x, 1);
upd(1, - 4e8, 4e8, x * 2, x + R, 1, - x, 1);
upd(1, - 4e8, 4e8, x + R, R * 2, -1, R, 1);
s[t].insert(x);
}
void rev(int t, int x) {
s[t].erase(s[t].find(x));
int L = *(--s[t].upper_bound(x));
int R = *s[t].upper_bound(x);
upd(1, - 4e8, 4e8, L * 2, L + R, 1, - L, 1);
upd(1, - 4e8, 4e8, L + R, R * 2, -1, R, 1);
upd(1, - 4e8, 4e8, L * 2, L + x, 1, - L, -1);
upd(1, - 4e8, 4e8, L + x, x * 2, -1, x, -1);
upd(1, - 4e8, 4e8, x * 2, x + R, 1, - x, -1);
upd(1, - 4e8, 4e8, x + R, R * 2, -1, R, -1);
cnt += (s[t].size() == 2);
}
int main() {
ios :: sync_with_stdio(0); cin.tie(0);
vector <tuple <int, int, int, int> > events;
cin >> n >> k >> q;
for (int i = 0; i < n; ++i) {
int x, t, a, b;
cin >> x >> t >> a >> b;
events.push_back({a, -1, x, t});
events.push_back({b + 1, 1, x, t});
}
for (int i = 1; i <= k; ++i) {
int L = - 2e8, R = 2e8;
s[i].insert(L), s[i].insert(R);
upd(1, - 4e8, 4e8, L * 2, L + R, 1, - L, 1);
upd(1, - 4e8, 4e8, L + R, R * 2, - 1, R, 1);
}
cnt = k;
vector <tuple <int, int, int> > work;
for (int i = 1; i <= q; ++i) {
int x, y;
cin >> x >> y;
work.push_back({y, x * 2, i});
}
sort(events.begin(), events.end());
sort(work.begin(), work.end());
int i = 0;
for (auto [y, x, id]: work) {
while (i < events.size() && get<0>(events[i]) <= y) {
auto [_, cmd, x, t] = events[i];
if (cmd == -1) add(t, x);
else rev(t, x);
++i;
}
if (cnt) ans[id] = -1;
else solve(1, - 4e8, 4e8, x, ans[id]);
}
for (int i = 1; i <= q; ++i) cout << ans[i] << '\n';
}
Compilation message
new_home.cpp: In function 'void upd(int, int, int, int, int, int, int, int)':
new_home.cpp:43:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
43 | int mid = L + R >> 1;
| ~~^~~
new_home.cpp: In function 'void solve(int, int, int, int, int&)':
new_home.cpp:53:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
53 | int mid = L + R >> 1;
| ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:113:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
113 | for (auto [y, x, id]: work) {
| ^
new_home.cpp:114:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::tuple<int, int, int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
114 | while (i < events.size() && get<0>(events[i]) <= y) {
| ~~^~~~~~~~~~~~~~~
new_home.cpp:115:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
115 | auto [_, cmd, x, t] = events[i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
392 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
392 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
411 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
411 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
392 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
392 ms |
1048576 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
