#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 {
priority_queue<int> st[mxN<<2], die[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;
while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
st[i].pop(), die[i].pop();
if (ql <= tl && tr <= qr) {
st[i].push(v);
while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
st[i].pop(), die[i].pop();
} 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;
while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
st[i].pop(), die[i].pop();
if (ql <= tl && tr <= qr) {
die[i].push(v);
while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
st[i].pop(), die[i].pop();
} 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, int i = 1, int tl = 0, int tr = size(cmp)-1) {
int ret = INT_MIN;
while (tl < tr) {
while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
st[i].pop(), die[i].pop();
assert(!size(st[i]) || !size(die[i]) || st[i].top() > die[i].top());
if (size(st[i]))
ret = max(ret, st[i].top());
int tm = tl + tr >> 1;
if (p <= tm)
i = lc, tr = tm;
else
i = rc, tl = tm + 1;
}
while (size(st[i]) && size(die[i]) && st[i].top() == die[i].top())
st[i].pop(), die[i].pop();
if (size(st[i]))
ret = max(ret, st[i].top());
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;
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 = st_left.qry(i);
if (l == INT_MIN)
l = x;
int r = st_right.qry(i);
if (r != INT_MIN)
r = -r;
r = max(r, x);
l = min(l, x);
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:33:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
33 | int tm = tl + tr >> 1;
| ~~~^~~~
new_home.cpp: In member function 'void ST::erase(int, int, int, int, int, int)':
new_home.cpp:48:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
48 | int tm = tl + tr >> 1;
| ~~~^~~~
new_home.cpp: In member function 'int ST::qry(int, int, int, int)':
new_home.cpp:61:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
61 | int tm = tl + tr >> 1;
| ~~~^~~~
new_home.cpp: In lambda function:
new_home.cpp:105:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
105 | int m = l + r + 1 >> 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;
| ~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
150580 KB |
Output is correct |
| 2 |
Correct |
79 ms |
150608 KB |
Output is correct |
| 3 |
Correct |
70 ms |
150608 KB |
Output is correct |
| 4 |
Incorrect |
80 ms |
150532 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
150580 KB |
Output is correct |
| 2 |
Correct |
79 ms |
150608 KB |
Output is correct |
| 3 |
Correct |
70 ms |
150608 KB |
Output is correct |
| 4 |
Incorrect |
80 ms |
150532 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5097 ms |
320760 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
5085 ms |
323860 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
150580 KB |
Output is correct |
| 2 |
Correct |
79 ms |
150608 KB |
Output is correct |
| 3 |
Correct |
70 ms |
150608 KB |
Output is correct |
| 4 |
Incorrect |
80 ms |
150532 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
69 ms |
150580 KB |
Output is correct |
| 2 |
Correct |
79 ms |
150608 KB |
Output is correct |
| 3 |
Correct |
70 ms |
150608 KB |
Output is correct |
| 4 |
Incorrect |
80 ms |
150532 KB |
Output isn't correct |
| 5 |
Halted |
0 ms |
0 KB |
- |
