#include <bits/stdc++.h>
using namespace std;
int h[200005];
int l[200005];
int r[200005];
vector<int> seg[524288];
int lb[524288];
int rb[524288];
void build(int c, int l, int r){
lb[c] = l;
rb[c] = r;
if(l == r) return;
int k = (l + r)/2;
build(2*c, l, k);
build(2*c+1, k+1, r);
}
void update(int c, int l, int r, int i){
// Left segment of i-th antenna is l to r
if(lb[c] == l && rb[c] == r){
seg[c].push_back(i);
return;
}
int k = (lb[c] + rb[c])/2;
if(l <= k && k < r){
update(2*c, l, k, i);
update(2*c+1, k+1, r, i);
}else if(r <= k){
update(2*c, l, r, i);
}else{
update(2*c+1, l, r, i);
}
}
void clean(int c){
sort(seg[c].begin(), seg[c].end());
if(lb[c] == rb[c]) return;
clean(2*c);
clean(2*c+1);
}
void query(int c, int i, int l, int r, vector<int>& ans){
auto beg = lower_bound(seg[c].begin(), seg[c].end(), l);
auto end = upper_bound(seg[c].begin(), seg[c].end(), r);
if(beg != end){
ans.push_back(*beg);
end--;
if(beg != end) ans.push_back(*end);
}
if(lb[c] == rb[c]) return;
int k = (lb[c] + rb[c])/2;
if(i <= k) query(2*c, i, l, r, ans);
else query(2*c+1, i, l, r, ans);
}
map<int, int> comms; // (r, d)
vector<pair<int,int> > queries[200005];
int ans[200005];
int main(){
int n;
scanf("%d",&n);
build(1, 1, n);
for(int i = 1; i <= n; i++){
scanf("%d%d%d",h+i,l+i,r+i);
int ll = i - r[i];
int rr = i - l[i];
if(rr < 1) continue;
ll = max(ll, 1);
rr = max(rr, 1);
update(1, ll, rr, i);
}
clean(1);
int q;
scanf("%d",&q);
for(int i = 1; i <= q; i++){
int l, r;
scanf("%d%d",&l,&r);
queries[l].emplace_back(r, i);
}
for(int i = n; i > 0; i--){
int ll = i + l[i];
int rr = i + r[i];
if(ll <= n){
vector<int> cur;
ll = min(ll, n);
rr = min(rr, n);
query(1, i, ll, rr, cur);
for(int x : cur){
// i -- x is a valid communication
int d = abs(h[i] - h[x]);
auto it = comms.lower_bound(x);
bool chk = false;
if(it != comms.begin()){
auto pit = it;
pit--;
if(pit->second < d) chk = true;
}else chk = true;
if(!chk) continue;
while(it != comms.end() && d >= it->second){
it = comms.erase(it);
}
if(it == comms.end() || it->first != x) comms[x] = d;
}
}
for(auto p : queries[i]){
int x = p.first;
int qidx = p.second;
auto it = comms.upper_bound(x);
if(it == comms.begin()){
ans[qidx] = -1;
continue;
}
it--;
ans[qidx] = it->second;
}
}
for(int i = 1; i <= q; i++){
printf("%d\n", ans[i]);
}
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:57:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
57 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
antennas.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
60 | scanf("%d%d%d",h+i,l+i,r+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
70 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
antennas.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
73 | scanf("%d%d",&l,&r);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
17408 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
17408 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
17408 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
17408 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
529 ms |
32504 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
12 ms |
17408 KB |
Output is correct |
| 2 |
Incorrect |
12 ms |
17408 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
