#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>
using namespace std;
// using namespace __gnu_cxx;
// using namespace __gnu_pbds;
void Hollwo_Pelw();
signed main(){
#ifndef hollwo_pelw_local
if (fopen(".inp", "r"))
assert(freopen(".inp", "r", stdin)), assert(freopen(".out", "w", stdout));
#else
using namespace chrono;
auto start = steady_clock::now();
#endif
cin.tie(0), cout.tie(0) -> sync_with_stdio(0);
int testcases = 1;
// cin >> testcases;
for (int test = 1; test <= testcases; test++){
// cout << "Case #" << test << ": ";
Hollwo_Pelw();
}
#ifdef hollwo_pelw_local
auto end = steady_clock::now();
cout << "\nExecution time : " << duration_cast<milliseconds> (end - start).count() << "[ms]" << endl;
#endif
}
const int N = 3e5 + 5, M = 9e5 + 5;
vector<int> xval, yval;
int n, k, q, px[N], py[N], res[N], cnt_type;
vector<pair<int, int>> stores[N];
map<int, int> st[N];
vector<pair<int, int>> upd[M], que[M];
#define tm ((tl + tr) >> 1)
#define left id << 1, tl, tm
#define right id << 1 | 1, tm + 1, tr
struct segtree {
multiset<int> st[N << 3];
void update(int l, int r, int v, int s, int id = 1, int tl = 1, int tr = xval.size()) {
// if (id == 1) cout << "MAX " << l << ' ' << r << " : " << (s < 0 ? "DEL " : "ADD ") << v << '\n';
if (l > tr || tl > r) return ;
if (l <= tl && tr <= r) {
// cout << id << " -> " << v << '\n';
if (s < 0)
st[id].erase(st[id].find(v));
else
st[id].insert(v);
return ;
}
update(l, r, v, s, left), update(l, r, v, s, right);
}
int query(int p, int id = 1, int tl = 1, int tr = xval.size()) {
int res = st[id].empty() ? 0 : max(xval[p] - *st[id].begin(), *--st[id].end() - xval[p]);
// cout << "get " << p << '\n';
// cout << " --> " << res << '\n';
// cout << st[id].size() << '\n';
if (tl < tr)
res = max(res, (p > tm ? query(p, right) : query(p, left)));
return res;
}
} T;
inline void addseg(int l, int r, int v) {
// cout << "add seg " << l << ' ' << r << ' ' << v << '\n';
if (l < 1 && r > n) { // empty ?
// cout << "sus \n";
cnt_type -= v;
return ;
}
if (l < 1) {
T.update(1, r - 1, xval[r], v);
return ;
}
if (r > n) {
T.update(l + 1, n, xval[l], v);
return ;
}
int ml = (l + r) >> 1, mr = ml + 1;
T.update(l + 1, ml, xval[l], v);
T.update(mr, r - 1, xval[r], v);
}
void add(int x, map<int, int> &st) {
if ((++ st[x]) == 1) {
auto it = st.find(x);
int l = prev(it) -> first, r = next(it) -> first;
// cout << x << '\n';
// cout << l << ' ' << r << '\n';
addseg(l, r, -1);
addseg(l, x, +1);
addseg(x, r, +1);
}
}
void del(int x, map<int, int> &st) {
if ((-- st[x]) == 0) {
auto it = st.find(x);
int l = prev(it) -> first, r = next(it) -> first;
addseg(l, r, +1);
addseg(l, x, -1);
addseg(x, r, -1);
st.erase(x);
}
}
void Hollwo_Pelw(){
cin >> n >> k >> q;
for (int i = 1, x, a, b, t; i <= n; i++) {
cin >> x >> t >> a >> b, ++ b;
xval.push_back(x);
yval.push_back(a);
yval.push_back(b);
stores[t].emplace_back(a, +x);
stores[t].emplace_back(b, -x);
}
for (int i = 1; i <= q; i++) {
cin >> px[i] >> py[i];
xval.push_back(px[i]);
yval.push_back(py[i]);
}
xval.push_back(0);
yval.push_back(0);
sort(xval.begin(), xval.end());
sort(yval.begin(), yval.end());
xval.erase(unique(xval.begin(), xval.end()), xval.end());
yval.erase(unique(yval.begin(), yval.end()), yval.end());
for (int i = 1; i <= q; i++) {
px[i] = lower_bound(xval.begin(), xval.end(), px[i]) - xval.begin();
py[i] = lower_bound(yval.begin(), yval.end(), py[i]) - yval.begin();
que[py[i]].emplace_back(px[i], i);
}
n = xval.size();
for (int t = 1; t <= k; t++) {
st[t][0] = st[t][n + 1] = 1;
for (auto &[y, x] : stores[t]) {
y = lower_bound(yval.begin(), yval.end(), y) - yval.begin();
x = (x < 0 ? -1 : +1) * (lower_bound(xval.begin(), xval.end(), abs(x)) - xval.begin());
upd[y].emplace_back(t, x);
}
}
for (int y = 1; y < (int) yval.size(); y++) {
// cout << "TIME LINE y = " << yval[y] << '\n';
// cout << "---------------------------------\n";
for (auto [t, x] : upd[y]) {
if (x < 0) {
// cout << "DEL " << -x << ' ' << t << '\n';
del(-x, st[t]);
}
else {
// cout << "ADD " << +x << ' ' << t << '\n';
add(+x, st[t]);
}
}
// cout << "cnt = " << cnt_type << '\n';
for (auto [p, i] : que[y]) {
// cout << "QUERY " << p << ' ' << i << '\n';
if (cnt_type == k) {
res[i] = T.query(p);
}
else {
res[i] = -1;
}
}
// cout << "---------------------------------\n";
}
for (int i = 1; i <= q; i++) {
cout << res[i] << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
176448 KB |
Output is correct |
| 2 |
Correct |
79 ms |
176392 KB |
Output is correct |
| 3 |
Correct |
83 ms |
176376 KB |
Output is correct |
| 4 |
Incorrect |
81 ms |
176332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
176448 KB |
Output is correct |
| 2 |
Correct |
79 ms |
176392 KB |
Output is correct |
| 3 |
Correct |
83 ms |
176376 KB |
Output is correct |
| 4 |
Incorrect |
81 ms |
176332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5077 ms |
520992 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5039 ms |
459552 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
176448 KB |
Output is correct |
| 2 |
Correct |
79 ms |
176392 KB |
Output is correct |
| 3 |
Correct |
83 ms |
176376 KB |
Output is correct |
| 4 |
Incorrect |
81 ms |
176332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
89 ms |
176448 KB |
Output is correct |
| 2 |
Correct |
79 ms |
176392 KB |
Output is correct |
| 3 |
Correct |
83 ms |
176376 KB |
Output is correct |
| 4 |
Incorrect |
81 ms |
176332 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
