#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n, k, q;
cin >> n >> k >> q;
vector<int> x(n);
vector<int> t(n);
vector<int> a(n);
vector<int> b(n);
map<pair<int, int>, vector<pair<int, int>>> mp;
for (int i = 0; i < n; i++) {
cin >> x[i] >> t[i] >> a[i] >> b[i];
--t[i]; ++b[i];
mp[{x[i], t[i]}].emplace_back(a[i], b[i]);
}
vector<int> new_x;
vector<int> new_t;
vector<int> new_a;
vector<int> new_b;
for (auto& p : mp) {
vector<pair<int, int>> v = p.second;
sort(v.begin(), v.end());
int sz = (int) v.size();
for (int i = 0; i < sz; i++) {
int ptr = i;
int mx = v[i].second;
while (ptr + 1 < sz && v[ptr + 1].first < mx) {
ptr += 1;
mx = max(mx, v[ptr + 1].second);
}
new_x.push_back(p.first.first);
new_t.push_back(p.first.second);
new_a.push_back(v[i].first);
new_b.push_back(mx);
i = ptr;
}
}
x = new_x;
t = new_t;
a = new_a;
b = new_b;
n = (int) x.size();
vector<int> l(q);
vector<int> y(q);
for (int i = 0; i < n; i++) {
cin >> l[i] >> y[i];
}
vector<int> xs(1, 1e9);
for (int i = 0; i < n; i++) {
xs.push_back(a[i]);
xs.push_back(b[i]);
}
for (int i = 0; i < q; i++) {
xs.push_back(y[i]);
}
sort(xs.begin(), xs.end());
xs.erase(unique(xs.begin(), xs.end()), xs.end());
for (int i = 0; i < n; i++) {
a[i] = (int) (lower_bound(xs.begin(), xs.end(), a[i]) - xs.begin());
b[i] = (int) (lower_bound(xs.begin(), xs.end(), b[i]) - xs.begin());
}
for (int i = 0; i < q; i++) {
y[i] = (int) (lower_bound(xs.begin(), xs.end(), y[i]) - xs.begin());
}
int T = (int) xs.size();
vector<vector<int>> ids(T);
for (int i = 0; i < n; i++) {
ids[a[i]].push_back(i);
ids[b[i]].push_back(~i);
}
const int inf = (int) 1e9;
multiset<tuple<int, int, int>> open;
vector<array<int, 4>> ev;
vector<multiset<int>> my(k);
auto Insert = [&](int t, int x, int y) {
auto ptr = my[t].lower_bound(x);
if (ptr != my[t].begin() && ptr != my[t].end()) {
auto it = open.lower_bound({*prev(ptr), *ptr, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open.erase(it);
} else if (ptr != my[t].begin()) {
auto it = open.lower_bound({*prev(ptr), inf, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open.erase(it);
} else if (ptr != my[t].end()) {
auto it = open.lower_bound({-inf, *ptr, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open.erase(it);
}
if (ptr != my[t].end()) {
open.emplace(x, *ptr, y);
} else {
open.emplace(x, inf, y);
}
if (ptr != my[t].begin()) {
ptr = prev(ptr);
open.emplace(*ptr, x, y);
} else {
open.emplace(-inf, x, y);
}
my[t].insert(x);
};
auto Remove = [&](int t, int x, int y) {
auto ptr = my[t].lower_bound(x);
if (ptr != prev(my[t].end())) {
auto it = open.lower_bound({x, *next(ptr), -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open.erase(it);
} else {
auto it = open.lower_bound({x, inf, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open.erase(it);
}
if (ptr != my[t].begin()) {
auto it = open.lower_bound({*prev(ptr), x, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open.erase(it);
} else {
auto it = open.lower_bound({-inf, x, -1});
ev.push_back({get<0>(*it), get<1>(*it), get<2>(*it), y});
open.erase(it);
}
if (ptr != my[t].begin() && ptr != prev(my[t].end())) {
open.emplace(*prev(ptr), *next(ptr), y);
} else if (ptr != my[t].begin()) {
open.emplace(*prev(ptr), inf, y);
} else if (ptr != prev(my[t].end())) {
open.emplace(-inf, *next(ptr), y);
}
my[t].erase(my[t].find(x));
};
for (int i = 0; i < T; i++) {
for (int j : ids[i]) {
if (j >= 0) {
Insert(t[j], x[j], i);
} else {
j = ~j;
Remove(t[j], x[j], i);
}
}
}
for (auto& p : open) {
ev.push_back({get<0>(p), get<1>(p), get<2>(p), T - 1});
}
vector<vector<int>> qs(T);
for (int i = 0; i < q; i++) {
qs[y[i]].push_back(i);
}
vector<pair<int, int>> min_with;
vector<pair<int, int>> max_with;
for (auto& p : ev) {
int L = p[0];
int R = p[1];
int mid = (L + R) / 2;
min_with.emplace_back(L, mid);
max_with.emplace_back(R, mid + (L % 2 != R % 2));
}
sort(min_with.begin(), min_with.end(), [&](pair<int, int> p, pair<int, int> q) {
return p.second > q.second;
});
sort(max_with.begin(), max_with.end(), [&](pair<int, int> p, pair<int, int> q) {
return p.second < q.second;
});
map<pair<int, int>, int> idx_mn;
map<pair<int, int>, int> idx_mx;
int sz = (int) ev.size();
for (int i = 0; i < sz; i++) {
idx_mn[min_with[i]] = i;
}
for (int i = 0; i < sz; i++) {
idx_mx[max_with[i]] = i;
}
vector<vector<int>> qs_mn(T);
vector<vector<int>> qs_mx(T);
for (int i = 0; i < sz; i++) {
int L = ev[i][0];
int R = ev[i][1];
int from = ev[i][2];
int to = ev[i][3];
int mid = (L + R) / 2;
{
int idx = idx_mn[{L, mid}];
qs_mn[from].push_back(idx);
qs_mn[to].push_back(~idx);
}
{
int idx = idx_mx[{R, mid + (L % 2 != R % 2)}];
qs_mx[from].push_back(idx);
qs_mx[to].push_back(~idx);
}
}
vector<int> mn(4 * sz);
vector<int> mx(4 * sz);
function<void(int, int, int)> Build = [&](int x, int l, int r) {
mn[x] = inf;
mx[x] = -inf;
if (l == r) {
return;
}
int mid = l + r >> 1;
Build(x << 1, l, mid);
Build(x << 1 | 1, mid + 1, r);
};
function<void(int, int, int, int, int)> ModifyMin = [&](int x, int l, int r, int p, int v) {
if (l == r) {
mn[x] = v;
return;
}
int mid = l + r >> 1;
if (p <= mid) {
ModifyMin(x << 1, l, mid, p, v);
} else {
ModifyMin(x << 1 | 1, mid + 1, r, p, v);
}
mn[x] = min(mn[x << 1], mn[x << 1 | 1]);
};
function<void(int, int, int, int, int)> ModifyMax = [&](int x, int l, int r, int p, int v) {
if (l == r) {
mx[x] = v;
return;
}
int mid = l + r >> 1;
if (p <= mid) {
ModifyMax(x << 1, l, mid, p, v);
} else {
ModifyMax(x << 1 | 1, mid + 1, r, p, v);
}
mx[x] = max(mx[x << 1], mx[x << 1 | 1]);
};
auto ChangeMin = [&](int p, int v) {
ModifyMin(1, 0, sz - 1, p, v);
};
auto ChangeMax = [&](int p, int v) {
ModifyMax(1, 0, sz - 1, p, v);
};
function<int(int, int, int, int, int)> query_max = [&](int x, int l, int r, int ll, int rr) {
if (l > r || l > rr || r < ll) {
return -inf;
}
if (ll <= l && r <= rr) {
return mx[x];
}
int mid = l + r >> 1;
return max(query_max(x << 1, l, mid, ll, rr), query_max(x << 1 | 1, mid + 1, r, ll, rr));
};
function<int(int, int, int, int, int)> query_min = [&](int x, int l, int r, int ll, int rr) {
if (l > r || l > rr || r < ll) {
return inf;
}
if (ll <= l && r <= rr) {
return mn[x];
}
int mid = l + r >> 1;
return min(query_min(x << 1, l, mid, ll, rr), query_min(x << 1 | 1, mid + 1, r, ll, rr));
};
auto get_max = [&](int l, int r) {
return query_max(1, 0, sz - 1, l, r);
};
auto get_min = [&](int l, int r) {
return query_min(1, 0, sz - 1, l, r);
};
Build(1, 0, sz - 1);
vector<int> res(q);
for (int i = 0; i < T; i++) {
for (int j : qs_mn[i]) {
if (j >= 0) {
ChangeMin(j, min_with[j].first);
} else {
j = ~j;
ChangeMin(j, inf);
}
}
for (int j : qs_mx[i]) {
if (j >= 0) {
ChangeMax(j, max_with[j].first);
} else {
j = ~j;
ChangeMax(j, -inf);
}
}
for (int j : qs[i]) {
{
int low = 0, high = sz - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (min_with[mid].second >= l[j]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
res[j] = max(res[j], l[j] - get_min(0, pos));
}
}
{
int low = 0, high = sz - 1, pos = -1;
while (low <= high) {
int mid = low + high >> 1;
if (max_with[mid].second <= l[j]) {
pos = mid;
low = mid + 1;
} else {
high = mid - 1;
}
}
if (pos != -1) {
res[j] = max(res[j], get_max(0, pos) - l[j]);
}
}
}
}
vector<vector<int>> qs_type(T);
for (int i = 0; i < n; i++) {
qs_type[a[i]].push_back(t[i]);
qs_type[b[i]].push_back(~t[i]);
}
int bal = 0;
vector<int> cnt(k);
for (int i = 0; i < T; i++) {
for (int j : qs_type[i]) {
if (j >= 0) {
cnt[j] += 1;
if (cnt[j] == 1) {
bal += 1;
}
} else {
j = ~j;
cnt[j] -= 1;
if (cnt[j] == 0) {
bal -= 1;
}
}
}
for (int j : qs[i]) {
if (bal != k) {
res[j] = -1;
}
}
}
for (int i = 0; i < q; i++) {
cout << res[i] << '\n';
}
return 0;
}
Compilation message
new_home.cpp: In lambda function:
new_home.cpp:204:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
204 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:213:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
213 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:226:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
226 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:247:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
247 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In lambda function:
new_home.cpp:257:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
257 | int mid = l + r >> 1;
| ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:289:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
289 | int mid = low + high >> 1;
| ~~~~^~~~~~
new_home.cpp:304:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
304 | int mid = low + high >> 1;
| ~~~~^~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3124 ms |
282932 KB |
Output is correct |
| 2 |
Incorrect |
2439 ms |
292436 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5059 ms |
344520 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
