///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
const int N = 3e5 + 5;
const int inf = 1e9 + 7;
int n, k, q, ans[N], t[8*N], M;
vector<int> v = {0}, tree;
multiset<int> pos[N], Q;
struct event {
int x, y, t, id;
event(int x = 0, int y = 0, int t = 0, int id = 0) :
x(x), y(y), t(t), id(id) {}
bool operator < (const event &e) const {
return y == e.y ? id < e.id : y < e.y;
}
};
vector<event> E;
void update(int node, int l, int r, int i, int x) {
if(l == r) return void(t[node] = x);
int m = l + r >> 1;
if(i <= m) update(node << 1, l, m, i, x);
else update(node << 1 | 1, m + 1, r, i, x);
t[node] = max(t[node << 1], t[node << 1 | 1]);
}
int query(int node, int l, int r, int i, int j) {
if(r < i || l > j) return 0;
if(i <= l && r <= j) return t[node];
int m = l + r >> 1;
return max(query(node << 1, l, m, i, j),
query(node << 1 | 1, m + 1, r, i, j));
}
void addPoint(int x, int t) {
int idx = lower_bound(v.begin(), v.end(), x) - v.begin();
auto it = pos[t].insert(x);
int nxt = *next(it);
if(it == pos[t].begin()) {
Q.erase(Q.find(nxt));
Q.insert(x);
}
update(1, 0, M, idx, nxt);
if(it != pos[t].begin()) {
int prv = *prev(it);
idx = lower_bound(v.begin(), v.end(), prv) - v.begin();
update(1, 0, M, idx, x);
}
}
void removePoint(int x, int t) {
int idx = lower_bound(v.begin(), v.end(), x) - v.begin();
auto it = pos[t].find(x);
int nxt = *next(it);
if(it == pos[t].begin()) {
Q.erase(Q.find(x));
Q.insert(nxt);
}
update(1, 0, M, idx, 0);
if(it != pos[t].begin()) {
int prv = *prev(it);
idx = lower_bound(v.begin(), v.end(), prv) - v.begin();
update(1, 0, M, idx, nxt);
}
pos[t].erase(it);
}
bool check(int l, int r) {
if(l < 1) return 1;
int idx = lower_bound(v.begin(), v.end(), l) - v.begin();
while(v[idx] >= l) --idx;
return query(1, 0, M, 0, idx) <= r;
}
int solve(int x) {
int fmax = *Q.rbegin();
if(fmax == inf) return -1;
int lo = max(0, fmax - x), hi = max(x - 1, v.back() - x), ans = -1;
while(lo <= hi) {
int m = lo + hi >> 1;
if(check(x - m, x + m))
ans = m, hi = m - 1;
else lo = m + 1;
}
return ans;
}
int main(int argc, char const *argv[]) {
scanf("%d %d %d", &n, &k, &q);
for(int i = 1; i <= n; ++i) {
int x, a, b, t;
scanf("%d %d %d %d", &x, &t, &a, &b);
E.emplace_back(x, a, t, 0);
E.emplace_back(x, b + 1, t, -1);
v.push_back(x);
}
for(int i = 1; i <= q; ++i) {
int l, y;
scanf("%d %d", &l, &y);
E.emplace_back(l, y, -1, i);
v.push_back(l);
}
sort(v.begin(), v.end());
sort(E.begin(), E.end());
v.erase(unique(v.begin(), v.end()), v.end());
M = v.size() + 2;
tree = vector<int>(4 * M, 0);
for(int i = 1; i <= k; ++i) {
pos[i].insert(inf);
Q.insert(inf);
}
for(auto e : E) {
if(e.id == 0) {
addPoint(e.x, e.t);
} else if(e.id == -1) {
removePoint(e.x, e.t);
} else {
ans[e.id] = solve(e.x);
}
}
for(int i = 1; i <= q; i++) {
printf("%d\n", ans[i]);
}
}
Compilation message
new_home.cpp: In function 'void update(int, int, int, int, int)':
new_home.cpp:27:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
new_home.cpp: In function 'int query(int, int, int, int, int)':
new_home.cpp:36:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = l + r >> 1;
~~^~~
new_home.cpp: In function 'int solve(int)':
new_home.cpp:96:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
int m = lo + hi >> 1;
~~~^~~~
new_home.cpp: In function 'int main(int, const char**)':
new_home.cpp:106:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d", &n, &k, &q);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d %d", &x, &t, &a, &b);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:116:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &l, &y);
~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 5 |
Incorrect |
19 ms |
14464 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 5 |
Incorrect |
19 ms |
14464 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2830 ms |
76512 KB |
Output is correct |
| 2 |
Incorrect |
4662 ms |
69668 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3612 ms |
70816 KB |
Output is correct |
| 2 |
Correct |
576 ms |
50980 KB |
Output is correct |
| 3 |
Incorrect |
4739 ms |
69412 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 5 |
Incorrect |
19 ms |
14464 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
14 ms |
14592 KB |
Output is correct |
| 2 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 3 |
Correct |
14 ms |
14464 KB |
Output is correct |
| 4 |
Correct |
15 ms |
14464 KB |
Output is correct |
| 5 |
Incorrect |
19 ms |
14464 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
