#include <bits/stdc++.h>
using namespace std;
using ari2 = array<int, 2>;
using ari3 = array<int, 3>;
using ari4 = array<int, 4>;
#define vt vector
#define size(x) (int((x).size()))
#define all(x) begin(x), end(x)
#define REP(a, b, c, d) for (int a = (b); (d) > 0 ? a <= (c) : a >= (c); a += (d))
#define FOR(a, b, c) REP(a, b, c, 1)
#define ROF(a, b, c) REP(a, b, c, -1)
constexpr int mxN = 300000;
int N, K, Q;
vt<int> cmp;
struct ST {
multiset<int> st[mxN<<2];
#define lc i << 1
#define rc lc | 1
void insert(int ql, int qr, int v, int i = 1, int tl = 0, int tr = size(cmp)-1) {
if (tl > qr || tr < ql)
return;
if (ql <= tl && tr <= qr) {
if (size(st[i]) < 2)
st[i].insert(v);
else {
int first = *begin(st[i]), last = *prev(end(st[i]));
if (v > last) {
while (size(st[i]) > 1)
st[i].erase(prev(end(st[i])));
st[i].insert(v);
} else if (v < first) {
while (size(st[i]) > 1)
st[i].erase(begin(st[i]));
st[i].insert(v);
}
}
} else {
int tm = tl + tr >> 1;
insert(ql, qr, v, lc, tl, tm);
insert(ql, qr, v, rc, tm+1, tr);
}
}
void erase(int ql, int qr, int v, int i = 1, int tl = 0, int tr = size(cmp)-1) {
if (tl > qr || tr < ql)
return;
if (ql <= tl && tr <= qr) {
if (st[i].count(v))
st[i].erase(st[i].find(v));
} else {
int tm = tl + tr >> 1;
erase(ql, qr, v, lc, tl, tm);
erase(ql, qr, v, rc, tm+1, tr);
}
}
int qry(int p, bool last, int i = 1, int tl = 0, int tr = size(cmp)-1) {
int ret = last ? -1 : INT_MAX;
while (tl < tr) {
if (size(st[i])) {
if (last)
ret = max(ret, *prev(end(st[i])));
else
ret = min(ret, *begin(st[i]));
}
int tm = tl + tr >> 1;
if (p <= tm)
i = lc, tr = tm;
else
i = rc, tl = tm + 1;
}
if (size(st[i])) {
if (last)
ret = max(ret, *prev(end(st[i])));
else
ret = min(ret, *begin(st[i]));
}
return ret;
}
#undef lc
#undef rc
} st_left, st_right;
signed main() {
#ifndef DEBUG
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
cin >> N >> K >> Q;
vt<ari4> events;
bool sub3 = true;
FOR(i, 0, N-1) {
int x, t, a, b;
cin >> x >> t >> a >> b, t--;
events.push_back({a, 0, x, t}); // time, (0 = insert, 1 = remove, 2 = is year), location, type
events.push_back({b+1, 1, x, t});
}
FOR(i, 0, Q-1) {
int year, x;
cin >> x >> year;
events.push_back({year, 2, x, i}); // time, is year, location, query index
cmp.push_back(x);
}
sort(all(cmp));
cmp.erase(unique(all(cmp)), end(cmp));
sort(all(events));
auto ind = [&](int v) {
return lower_bound(all(cmp), v) - begin(cmp);
};
auto erase = [&](int l, int r) {
assert(l + r + 1 >= 0);
int m = l + r + 1 >> 1;
int li = ind(l), ri = ind(r), mi = ind(m);
ri -= cmp[ri] > r;
if (mi - 1 >= li)
st_left.erase(li, mi-1, l);
if (ri >= mi)
st_right.erase(mi, ri, r);
};
auto insert = [&](int l, int r) {
assert(l + r + 1 >= 0);
int m = l + r + 1 >> 1;
int li = ind(l), ri = ind(r), mi = ind(m);
ri -= cmp[ri] > r;
if (mi - 1 >= li)
st_left.insert(li, mi-1, l);
if (ri >= mi)
st_right.insert(mi, ri, r);
};
vt<int> ans(Q), present(K);
vt<map<int, int>> positions(K);
int present_cnt = 0;
for (auto &[t, is_query, x, type] : events) {
if (is_query == 2) {
if (present_cnt < K) {
ans[type] = -1;
continue;
}
int i = ind(x);
int l = min(x, st_left.qry(i, false));
int r = max(x, st_right.qry(i, true));
ans[type] = max(r - x, x - l);
#ifdef DEBUG
cout << "at time " << t << " answer for " << x << " is:\n";
cout << "L: " << l << '\n';
cout << "R: " << r << '\n';
#endif
} else if (is_query) {
auto &xs = positions[type];
if (xs[x] == 1) {
auto it = xs.find(x);
int l = it != begin(xs) ? prev(it)->first : -1;
int r = next(it) != end(xs) ? next(it)->first : INT_MAX;
xs.erase(it);
if (l >= 0)
erase(l, x);
else
erase(-x, x);
if (r < INT_MAX)
erase(x, r);
else
erase(x, INT_MAX - x - 1);
if (l >= 0 && r < INT_MAX)
insert(l, r);
else if (l >= 0)
insert(l, INT_MAX - l - 1);
else if (r < INT_MAX)
insert(-r, r);
} else {
xs[x]--;
}
present_cnt -= --present[type] == 0;
} else {
auto &xs = positions[type];
if (xs[x])
xs[x]++;
else {
xs[x] = 1;
auto it = xs.find(x);
int l = it != begin(xs) ? prev(it)->first : -1;
int r = next(it) != end(xs) ? next(it)->first : INT_MAX;
if (l >= 0 && r < INT_MAX)
erase(l, r);
else if (l >= 0)
erase(l, INT_MAX - l - 1);
else if (r < INT_MAX)
erase(-r, r);
if (l >= 0)
insert(l, x);
else
insert(-x, x);
if (r < INT_MAX)
insert(x, r);
else
insert(x, INT_MAX - x - 1);
}
present_cnt += ++present[type] == 1;
}
}
for (int &i : ans)
cout << i << '\n';
}
Compilation message
new_home.cpp: In member function 'void ST::insert(int, int, int, int, int, int)':
new_home.cpp:42:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
42 | int tm = tl + tr >> 1;
| ~~~^~~~
new_home.cpp: In member function 'void ST::erase(int, int, int, int, int, int)':
new_home.cpp:54:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
54 | int tm = tl + tr >> 1;
| ~~~^~~~
new_home.cpp: In member function 'int ST::qry(int, bool, int, int, int)':
new_home.cpp:68:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
68 | int tm = tl + tr >> 1;
| ~~~^~~~
new_home.cpp: In lambda function:
new_home.cpp:115:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
115 | int m = l + r + 1 >> 1;
| ~~~~~~^~~
new_home.cpp: In lambda function:
new_home.cpp:125:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
125 | int m = l + r + 1 >> 1;
| ~~~~~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:93:8: warning: unused variable 'sub3' [-Wunused-variable]
93 | bool sub3 = true;
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
112976 KB |
Output is correct |
| 2 |
Correct |
24 ms |
112984 KB |
Output is correct |
| 3 |
Correct |
24 ms |
113108 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
112988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
112976 KB |
Output is correct |
| 2 |
Correct |
24 ms |
112984 KB |
Output is correct |
| 3 |
Correct |
24 ms |
113108 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
112988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2690 ms |
212408 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4961 ms |
213300 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
112976 KB |
Output is correct |
| 2 |
Correct |
24 ms |
112984 KB |
Output is correct |
| 3 |
Correct |
24 ms |
113108 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
112988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
43 ms |
112976 KB |
Output is correct |
| 2 |
Correct |
24 ms |
112984 KB |
Output is correct |
| 3 |
Correct |
24 ms |
113108 KB |
Output is correct |
| 4 |
Incorrect |
24 ms |
112988 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
