#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;
const int M = 3e8 + 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 * 10];
vector <int> dta;
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;
if (u <= mid) {
go(st[id].lhs);
upd(st[id].lhs, L, mid, u, v, a, b, mode);
}
if (v > mid) {
go(st[id].rhs);
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, dta[x] + *(--st[id].rgt.end()));
if (st[id].lft.size()) ans = max(ans, - dta[x] + *(--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 fake_add(int t, int x) {
int L = *(--s[t].upper_bound(x));
int R = *s[t].upper_bound(x);
dta.push_back(L);
dta.push_back(R);
dta.push_back(x);
dta.push_back((L + R) / 2);
dta.push_back((L + x) / 2);
dta.push_back((x + R) / 2);
s[t].insert(x);
}
void fake_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);
dta.push_back(L);
dta.push_back(R);
dta.push_back(x);
dta.push_back((L + R) / 2);
dta.push_back((L + x) / 2);
dta.push_back((x + R) / 2);
}
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);
int l = lower_bound(dta.begin(), dta.end(), L) - dta.begin();
int r = lower_bound(dta.begin(), dta.end(), R) - dta.begin();
int x = lower_bound(dta.begin(), dta.end(), X) - dta.begin();
int lr = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
int lx = lower_bound(dta.begin(), dta.end(), (L + X) / 2) - dta.begin();
int rx = lower_bound(dta.begin(), dta.end(), (X + R) / 2) - dta.begin();
upd(1, 0, dta.size() - 1, l, lr, 1, - L, -1);
upd(1, 0, dta.size() - 1, lr + 1, r, - 1, R, -1);
upd(1, 0, dta.size() - 1, l, lx, 1, - L, 1);
upd(1, 0, dta.size() - 1, lx + 1, x, - 1, X, 1);
upd(1, 0, dta.size() - 1, x, rx, 1, - X, 1);
upd(1, 0, dta.size() - 1, rx + 1, r, - 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);
int l = lower_bound(dta.begin(), dta.end(), L) - dta.begin();
int r = lower_bound(dta.begin(), dta.end(), R) - dta.begin();
int x = lower_bound(dta.begin(), dta.end(), X) - dta.begin();
int lr = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
int lx = lower_bound(dta.begin(), dta.end(), (L + X) / 2) - dta.begin();
int rx = lower_bound(dta.begin(), dta.end(), (X + R) / 2) - dta.begin();
upd(1, 0, dta.size() - 1, l, lr, 1, - L, 1);
upd(1, 0, dta.size() - 1, lr + 1, r, - 1, R, 1);
upd(1, 0, dta.size() - 1, l, lx, 1, - L, -1);
upd(1, 0, dta.size() - 1, lx + 1, x, - 1, X, -1);
upd(1, 0, dta.size() - 1, x, rx, 1, - X, -1);
upd(1, 0, dta.size() - 1, rx + 1, r, - 1, R, -1);
cnt += (s[t].size() == 2);
}
int main() {
// freopen("test.inp", "r", stdin);
// freopen("test.out", "w", stdout);
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;
x += 1e8 + 5;
events.push_back({a, -1, x, t});
events.push_back({b + 1, 1, x, t});
}
for (int i = 1; i <= k; ++i) {
s[i].insert(0), s[i].insert(M);
int L = 0, R = M;
dta.push_back(L), dta.push_back(R);
dta.push_back((L + R) / 2);
}
for (auto [_, cmd, x, t]: events) {
if (cmd == -1) fake_add(t, x);
else fake_rev(t, x);
}
cnt = k;
vector <tuple <int, int, int> > work;
for (int i = 1; i <= q; ++i) {
int x, y;
cin >> x >> y;
x += 1e8 + 5;
work.push_back({y, x, i});
dta.push_back(x);
}
sort(dta.begin(), dta.end());
dta.erase(unique(dta.begin(), dta.end()), dta.end());
for (int i = 1; i <= k; ++i) {
int L = 0, R = M;
int l = 0, r = dta.size() - 1;
int m = lower_bound(dta.begin(), dta.end(), (L + R) / 2) - dta.begin();
upd(1, 0, dta.size() - 1, l, m, 1, - L, 1);
upd(1, 0, dta.size() - 1, m + 1, r, - 1, R, 1);
}
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;
}
x = lower_bound(dta.begin(), dta.end(), x) - dta.begin();
if (cnt) ans[id] = -1;
else solve(1, 0, dta.size() - 1, 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:44:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
44 | int mid = L + R >> 1;
| ~~^~~
new_home.cpp: In function 'void solve(int, int, int, int, int&)':
new_home.cpp:59:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
59 | int mid = L + R >> 1;
| ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:153:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
153 | for (auto [_, cmd, x, t]: events) {
| ^
new_home.cpp:178:15: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
178 | for (auto [y, x, id]: work) {
| ^
new_home.cpp:179: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]
179 | while (i < events.size() && get<0>(events[i]) <= y) {
| ~~^~~~~~~~~~~~~~~
new_home.cpp:180:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
180 | auto [_, cmd, x, t] = events[i];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
168 ms |
319748 KB |
Output is correct |
| 2 |
Correct |
144 ms |
319700 KB |
Output is correct |
| 3 |
Correct |
176 ms |
319612 KB |
Output is correct |
| 4 |
Correct |
140 ms |
319708 KB |
Output is correct |
| 5 |
Correct |
146 ms |
319768 KB |
Output is correct |
| 6 |
Incorrect |
148 ms |
319760 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
168 ms |
319748 KB |
Output is correct |
| 2 |
Correct |
144 ms |
319700 KB |
Output is correct |
| 3 |
Correct |
176 ms |
319612 KB |
Output is correct |
| 4 |
Correct |
140 ms |
319708 KB |
Output is correct |
| 5 |
Correct |
146 ms |
319768 KB |
Output is correct |
| 6 |
Incorrect |
148 ms |
319760 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5057 ms |
644424 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5060 ms |
589288 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
168 ms |
319748 KB |
Output is correct |
| 2 |
Correct |
144 ms |
319700 KB |
Output is correct |
| 3 |
Correct |
176 ms |
319612 KB |
Output is correct |
| 4 |
Correct |
140 ms |
319708 KB |
Output is correct |
| 5 |
Correct |
146 ms |
319768 KB |
Output is correct |
| 6 |
Incorrect |
148 ms |
319760 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
168 ms |
319748 KB |
Output is correct |
| 2 |
Correct |
144 ms |
319700 KB |
Output is correct |
| 3 |
Correct |
176 ms |
319612 KB |
Output is correct |
| 4 |
Correct |
140 ms |
319708 KB |
Output is correct |
| 5 |
Correct |
146 ms |
319768 KB |
Output is correct |
| 6 |
Incorrect |
148 ms |
319760 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
