#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);
for(auto it = beg; it != end; it++){
ans.push_back(*it);
}
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:55:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
55 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
antennas.cpp:58:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
58 | scanf("%d%d%d",h+i,l+i,r+i);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
68 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
antennas.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
71 | scanf("%d%d",&l,&r);
| ~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
17408 KB |
Output is correct |
2 |
Correct |
12 ms |
17408 KB |
Output is correct |
3 |
Correct |
13 ms |
17408 KB |
Output is correct |
4 |
Correct |
12 ms |
17408 KB |
Output is correct |
5 |
Correct |
13 ms |
17408 KB |
Output is correct |
6 |
Correct |
12 ms |
17408 KB |
Output is correct |
7 |
Correct |
12 ms |
17408 KB |
Output is correct |
8 |
Correct |
12 ms |
17408 KB |
Output is correct |
9 |
Correct |
12 ms |
17408 KB |
Output is correct |
10 |
Correct |
12 ms |
17408 KB |
Output is correct |
11 |
Correct |
12 ms |
17408 KB |
Output is correct |
12 |
Correct |
13 ms |
17440 KB |
Output is correct |
13 |
Correct |
12 ms |
17408 KB |
Output is correct |
14 |
Correct |
13 ms |
17408 KB |
Output is correct |
15 |
Correct |
14 ms |
17408 KB |
Output is correct |
16 |
Correct |
12 ms |
17408 KB |
Output is correct |
17 |
Correct |
12 ms |
17408 KB |
Output is correct |
18 |
Correct |
12 ms |
17408 KB |
Output is correct |
19 |
Correct |
12 ms |
17408 KB |
Output is correct |
20 |
Correct |
13 ms |
17408 KB |
Output is correct |
21 |
Correct |
12 ms |
17408 KB |
Output is correct |
22 |
Correct |
12 ms |
17408 KB |
Output is correct |
23 |
Correct |
12 ms |
17408 KB |
Output is correct |
24 |
Correct |
12 ms |
17408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
17408 KB |
Output is correct |
2 |
Correct |
12 ms |
17408 KB |
Output is correct |
3 |
Correct |
13 ms |
17408 KB |
Output is correct |
4 |
Correct |
12 ms |
17408 KB |
Output is correct |
5 |
Correct |
13 ms |
17408 KB |
Output is correct |
6 |
Correct |
12 ms |
17408 KB |
Output is correct |
7 |
Correct |
12 ms |
17408 KB |
Output is correct |
8 |
Correct |
12 ms |
17408 KB |
Output is correct |
9 |
Correct |
12 ms |
17408 KB |
Output is correct |
10 |
Correct |
12 ms |
17408 KB |
Output is correct |
11 |
Correct |
12 ms |
17408 KB |
Output is correct |
12 |
Correct |
13 ms |
17440 KB |
Output is correct |
13 |
Correct |
12 ms |
17408 KB |
Output is correct |
14 |
Correct |
13 ms |
17408 KB |
Output is correct |
15 |
Correct |
14 ms |
17408 KB |
Output is correct |
16 |
Correct |
12 ms |
17408 KB |
Output is correct |
17 |
Correct |
12 ms |
17408 KB |
Output is correct |
18 |
Correct |
12 ms |
17408 KB |
Output is correct |
19 |
Correct |
12 ms |
17408 KB |
Output is correct |
20 |
Correct |
13 ms |
17408 KB |
Output is correct |
21 |
Correct |
12 ms |
17408 KB |
Output is correct |
22 |
Correct |
12 ms |
17408 KB |
Output is correct |
23 |
Correct |
12 ms |
17408 KB |
Output is correct |
24 |
Correct |
12 ms |
17408 KB |
Output is correct |
25 |
Correct |
73 ms |
22392 KB |
Output is correct |
26 |
Correct |
23 ms |
18048 KB |
Output is correct |
27 |
Correct |
97 ms |
24184 KB |
Output is correct |
28 |
Correct |
104 ms |
24184 KB |
Output is correct |
29 |
Correct |
71 ms |
22520 KB |
Output is correct |
30 |
Correct |
82 ms |
22264 KB |
Output is correct |
31 |
Correct |
89 ms |
23416 KB |
Output is correct |
32 |
Correct |
98 ms |
24060 KB |
Output is correct |
33 |
Correct |
92 ms |
24056 KB |
Output is correct |
34 |
Correct |
58 ms |
20728 KB |
Output is correct |
35 |
Correct |
99 ms |
24696 KB |
Output is correct |
36 |
Correct |
99 ms |
24188 KB |
Output is correct |
37 |
Correct |
59 ms |
20856 KB |
Output is correct |
38 |
Correct |
90 ms |
23032 KB |
Output is correct |
39 |
Correct |
25 ms |
18344 KB |
Output is correct |
40 |
Correct |
90 ms |
23032 KB |
Output is correct |
41 |
Correct |
85 ms |
22008 KB |
Output is correct |
42 |
Correct |
91 ms |
23144 KB |
Output is correct |
43 |
Correct |
40 ms |
19448 KB |
Output is correct |
44 |
Correct |
91 ms |
23032 KB |
Output is correct |
45 |
Correct |
27 ms |
18552 KB |
Output is correct |
46 |
Correct |
92 ms |
23064 KB |
Output is correct |
47 |
Correct |
35 ms |
19072 KB |
Output is correct |
48 |
Correct |
90 ms |
23032 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3019 ms |
32964 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
12 ms |
17408 KB |
Output is correct |
2 |
Correct |
12 ms |
17408 KB |
Output is correct |
3 |
Correct |
13 ms |
17408 KB |
Output is correct |
4 |
Correct |
12 ms |
17408 KB |
Output is correct |
5 |
Correct |
13 ms |
17408 KB |
Output is correct |
6 |
Correct |
12 ms |
17408 KB |
Output is correct |
7 |
Correct |
12 ms |
17408 KB |
Output is correct |
8 |
Correct |
12 ms |
17408 KB |
Output is correct |
9 |
Correct |
12 ms |
17408 KB |
Output is correct |
10 |
Correct |
12 ms |
17408 KB |
Output is correct |
11 |
Correct |
12 ms |
17408 KB |
Output is correct |
12 |
Correct |
13 ms |
17440 KB |
Output is correct |
13 |
Correct |
12 ms |
17408 KB |
Output is correct |
14 |
Correct |
13 ms |
17408 KB |
Output is correct |
15 |
Correct |
14 ms |
17408 KB |
Output is correct |
16 |
Correct |
12 ms |
17408 KB |
Output is correct |
17 |
Correct |
12 ms |
17408 KB |
Output is correct |
18 |
Correct |
12 ms |
17408 KB |
Output is correct |
19 |
Correct |
12 ms |
17408 KB |
Output is correct |
20 |
Correct |
13 ms |
17408 KB |
Output is correct |
21 |
Correct |
12 ms |
17408 KB |
Output is correct |
22 |
Correct |
12 ms |
17408 KB |
Output is correct |
23 |
Correct |
12 ms |
17408 KB |
Output is correct |
24 |
Correct |
12 ms |
17408 KB |
Output is correct |
25 |
Correct |
73 ms |
22392 KB |
Output is correct |
26 |
Correct |
23 ms |
18048 KB |
Output is correct |
27 |
Correct |
97 ms |
24184 KB |
Output is correct |
28 |
Correct |
104 ms |
24184 KB |
Output is correct |
29 |
Correct |
71 ms |
22520 KB |
Output is correct |
30 |
Correct |
82 ms |
22264 KB |
Output is correct |
31 |
Correct |
89 ms |
23416 KB |
Output is correct |
32 |
Correct |
98 ms |
24060 KB |
Output is correct |
33 |
Correct |
92 ms |
24056 KB |
Output is correct |
34 |
Correct |
58 ms |
20728 KB |
Output is correct |
35 |
Correct |
99 ms |
24696 KB |
Output is correct |
36 |
Correct |
99 ms |
24188 KB |
Output is correct |
37 |
Correct |
59 ms |
20856 KB |
Output is correct |
38 |
Correct |
90 ms |
23032 KB |
Output is correct |
39 |
Correct |
25 ms |
18344 KB |
Output is correct |
40 |
Correct |
90 ms |
23032 KB |
Output is correct |
41 |
Correct |
85 ms |
22008 KB |
Output is correct |
42 |
Correct |
91 ms |
23144 KB |
Output is correct |
43 |
Correct |
40 ms |
19448 KB |
Output is correct |
44 |
Correct |
91 ms |
23032 KB |
Output is correct |
45 |
Correct |
27 ms |
18552 KB |
Output is correct |
46 |
Correct |
92 ms |
23064 KB |
Output is correct |
47 |
Correct |
35 ms |
19072 KB |
Output is correct |
48 |
Correct |
90 ms |
23032 KB |
Output is correct |
49 |
Execution timed out |
3019 ms |
32964 KB |
Time limit exceeded |
50 |
Halted |
0 ms |
0 KB |
- |