#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int mxn=6e5+5;
const int inf=1e9;
const int MX = 3e5 + 1;
struct segtree {
int tree[4*mxn];
void update(int node,int b,int e,int p,int v) {
if(e < p || b > p)return;
if(b == e) {
tree[node] = v;
return;
}
int mid=b+e>>1;
int left=node<<1;
int right=left|1;
update(left,b,mid,p,v);
update(right,mid+1,e,p,v);
tree[node]=max(tree[left],tree[right]);
}
int query(int node, int b, int e, int l, int r) {
if(e < l || b > r) return 0;
if(b >= l && e <= r) return tree[node];
int mid = b + e >> 1;
int left = node << 1;
int right = left | 1;
return max(query(left, b, mid, l, r), query(right, mid + 1, e , l, r));
}
} st;
ll x[mxn];
int tp[mxn];
ll p[mxn], y[mxn];
multiset<ll> con[mxn];
vector<ll> v;
int main() {
int n, k, q;
cin >> n >> k >> q;
for(int i = 1; i <= k; i++) {
x[i] = -inf + i;
tp[i] = i;
v.push_back(x[i]);
con[tp[i]].insert(x[i]);
con[tp[i]].insert(inf);
}
for(int i = k; i < n + k; i++) {
int a, b;
scanf("%lld %d%d%d", &x[i], &tp[i], &a, &b);
v.push_back(x[i]);
con[tp[i]].insert(x[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
for(int i = 1; i <= k; i++) {
auto it = con[i].begin();
it++;
for(;it != con[i].end(); it++) {
int prv = *prev(it);
int cr = *it;
int lp = lower_bound(v.begin(), v.end(), prv) - v.begin() + 1;
st.update(1, 1, MX, lp, cr);
}
}
for(int i = 1; i <= q; i++) {
scanf("%lld %lld", &p[i], &y[i]);
int lo = 0;
int hi = (int) inf;
ll ans = -1;
while(lo <= hi) {
int mid = lo + hi >> 1;
int pos = p[i] - mid;
int d = lower_bound(v.begin(), v.end(), pos) - v.begin();
if(st.query(1, 1, MX, 1, d) <= p[i] + mid) {
ans = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
cout<<ans<<endl;
}
}
Compilation message
new_home.cpp: In member function 'void segtree::update(int, int, int, int, int)':
new_home.cpp:17:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
17 | int mid=b+e>>1;
| ~^~
new_home.cpp: In member function 'int segtree::query(int, int, int, int, int)':
new_home.cpp:30:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
30 | int mid = b + e >> 1;
| ~~^~~
new_home.cpp: In function 'int main()':
new_home.cpp:98:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
98 | int mid = lo + hi >> 1;
| ~~~^~~~
new_home.cpp:62:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
62 | scanf("%lld %d%d%d", &x[i], &tp[i], &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
new_home.cpp:89:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
89 | scanf("%lld %lld", &p[i], &y[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28536 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
28488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28536 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
28488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1772 ms |
80692 KB |
Output is correct |
| 2 |
Incorrect |
2528 ms |
71456 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2458 ms |
73432 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28536 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
28488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
15 ms |
28536 KB |
Output is correct |
| 2 |
Incorrect |
14 ms |
28488 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
