#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int NMAX = 2e5;
const int QMAX = 2e5;
const int NASPA = 1e9 + 5;
int n,q;
int h[NMAX + 5];
int a[NMAX + 5];
int b[NMAX + 5];
int ans[QMAX + 5];
vector<pair<int,int> > queries[NMAX + 5];
vector<int> add[NMAX + 5];
vector<int> rem[NMAX + 5];
struct node_t{
int ma_lazy;
int mi_lazy;
int best_ans;
int mi_val;
int ma_val;
node_t operator + (const node_t &other)const{
node_t ans;
ans.ma_lazy = ans.mi_lazy = NASPA;
ans.best_ans = max(this->best_ans,other.best_ans);
ans.mi_val = (this->mi_val == NASPA ? other.mi_val:(other.mi_val == NASPA ? this->mi_val:min(this->mi_val,other.mi_val)));
ans.ma_val = (this->ma_val == NASPA ? other.ma_val:(other.ma_val == NASPA ? this->ma_val:max(this->ma_val,other.ma_val)));
return ans;
}
void recalc_best_ans(){
if(mi_val != NASPA){
if(mi_lazy != NASPA){
best_ans = max(best_ans,abs(mi_val - mi_lazy));
}
if(ma_lazy != NASPA){
best_ans = max(best_ans,abs(mi_val - ma_lazy));
}
}
if(ma_val != NASPA){
if(mi_lazy != NASPA){
best_ans = max(best_ans,abs(ma_val - mi_lazy));
}
if(ma_lazy != NASPA){
best_ans = max(best_ans,abs(ma_val - ma_lazy));
}
}
}
}aint[4 * NMAX + 5];
void init(int nod,int st,int dr){
aint[nod].ma_lazy = NASPA;
aint[nod].mi_lazy = NASPA;
aint[nod].best_ans = -1;
aint[nod].mi_val = NASPA;
aint[nod].ma_val = NASPA;
if(st == dr){
return ;
}
int mid = (st + dr) / 2;
init(nod * 2,st,mid);
init(nod * 2 + 1,mid + 1,dr);
}
void propag(int nod,int st,int dr){
if(st == dr || aint[nod].mi_lazy == NASPA){
aint[nod].mi_lazy = NASPA;
aint[nod].ma_lazy = NASPA;
return ;
}
aint[nod * 2].mi_lazy = (aint[nod * 2].mi_lazy == NASPA ? aint[nod].mi_lazy:min(aint[nod * 2].mi_lazy,aint[nod].mi_lazy));
aint[nod * 2].ma_lazy = (aint[nod * 2].ma_lazy == NASPA ? aint[nod].ma_lazy:max(aint[nod * 2].ma_lazy,aint[nod].ma_lazy));
aint[nod * 2 + 1].mi_lazy = (aint[nod * 2 + 1].mi_lazy == NASPA ? aint[nod].mi_lazy:min(aint[nod * 2 + 1].mi_lazy,aint[nod].mi_lazy));
aint[nod * 2 + 1].ma_lazy = (aint[nod * 2 + 1].ma_lazy == NASPA ? aint[nod].ma_lazy:max(aint[nod * 2 + 1].ma_lazy,aint[nod].ma_lazy));
aint[nod * 2].recalc_best_ans();
aint[nod * 2 + 1].recalc_best_ans();
aint[nod].mi_lazy = NASPA;
aint[nod].ma_lazy = NASPA;
}
void update_best_ans(int nod,int st,int dr,int l,int r,int val){
propag(nod,st,dr);
if(r < st || l > dr){
return ;
}
if(l <= st && dr <= r){
aint[nod].mi_lazy = val;
aint[nod].ma_lazy = val;
aint[nod].recalc_best_ans();
return ;
}
int mid = (st + dr) / 2;
update_best_ans(nod * 2,st,mid,l,r,val);
update_best_ans(nod * 2 + 1,mid + 1,dr,l,r,val);
aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}
void update(int nod,int st,int dr,int pos,int val){
propag(nod,st,dr);
if(pos > dr || pos < st){
return ;
}
if(st == dr){
aint[nod].mi_val = aint[nod].ma_val = val;
return ;
}
int mid = (st + dr) / 2;
update(nod * 2,st,mid,pos,val);
update(nod * 2 + 1,mid + 1,dr,pos,val);
aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}
int query(int nod,int st,int dr,int l,int r){
propag(nod,st,dr);
if(r < st || l > dr){
return -1;
}
if(l <= st && dr <= r){
return aint[nod].best_ans;
}
int mid = (st + dr) / 2;
return max(query(nod * 2,st,mid,l,r),query(nod * 2 + 1,mid + 1,dr,l,r));
}
int main(){
scanf("%d",&n);
for(int i = 1;i <= n;i++){
scanf("%d %d %d",&h[i],&a[i],&b[i]);
}
scanf("%d",&q);
for(int i = 1;i <= q;i++){
int l,r;
scanf("%d %d",&l,&r);
queries[r].push_back({l,i});
}
for(int i = 1;i <= n;i++){
if(i + a[i] <= n){
add[i + a[i]].push_back(i);
}
if(i + b[i] + 1 <= n){
rem[i + b[i] + 1].push_back(i);
}
}
init(1,1,n);
for(int i = 1;i <= n;i++){
for(auto it:add[i]){
update(1,1,n,it,h[it]);
}
for(auto it:rem[i]){
update(1,1,n,it,NASPA);
}
if(max(i - b[i],1) <= i - a[i]){
update_best_ans(1,1,n,max(i - b[i],1),i - a[i],h[i]);
}
for(auto it:queries[i]){
ans[it.second] = query(1,1,n,it.first,i);
}
}
for(int i = 1;i <= q;i++){
printf("%d\n",ans[i]);
}
return 0;
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:152:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&n);
~~~~~^~~~~~~~~
antennas.cpp:155:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d %d",&h[i],&a[i],&b[i]);
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:158:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&q);
~~~~~^~~~~~~~~
antennas.cpp:162:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d",&l,&r);
~~~~~^~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14372 KB |
Output is correct |
2 |
Correct |
15 ms |
14460 KB |
Output is correct |
3 |
Correct |
15 ms |
14456 KB |
Output is correct |
4 |
Correct |
15 ms |
14456 KB |
Output is correct |
5 |
Correct |
17 ms |
14456 KB |
Output is correct |
6 |
Correct |
15 ms |
14460 KB |
Output is correct |
7 |
Correct |
15 ms |
14456 KB |
Output is correct |
8 |
Correct |
18 ms |
14388 KB |
Output is correct |
9 |
Correct |
15 ms |
14456 KB |
Output is correct |
10 |
Correct |
17 ms |
14460 KB |
Output is correct |
11 |
Correct |
15 ms |
14456 KB |
Output is correct |
12 |
Correct |
14 ms |
14464 KB |
Output is correct |
13 |
Correct |
15 ms |
14584 KB |
Output is correct |
14 |
Correct |
15 ms |
14456 KB |
Output is correct |
15 |
Correct |
15 ms |
14584 KB |
Output is correct |
16 |
Correct |
15 ms |
14456 KB |
Output is correct |
17 |
Correct |
15 ms |
14456 KB |
Output is correct |
18 |
Correct |
14 ms |
14456 KB |
Output is correct |
19 |
Correct |
13 ms |
14456 KB |
Output is correct |
20 |
Correct |
14 ms |
14456 KB |
Output is correct |
21 |
Correct |
15 ms |
14456 KB |
Output is correct |
22 |
Correct |
14 ms |
14460 KB |
Output is correct |
23 |
Correct |
14 ms |
14456 KB |
Output is correct |
24 |
Correct |
15 ms |
14492 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14372 KB |
Output is correct |
2 |
Correct |
15 ms |
14460 KB |
Output is correct |
3 |
Correct |
15 ms |
14456 KB |
Output is correct |
4 |
Correct |
15 ms |
14456 KB |
Output is correct |
5 |
Correct |
17 ms |
14456 KB |
Output is correct |
6 |
Correct |
15 ms |
14460 KB |
Output is correct |
7 |
Correct |
15 ms |
14456 KB |
Output is correct |
8 |
Correct |
18 ms |
14388 KB |
Output is correct |
9 |
Correct |
15 ms |
14456 KB |
Output is correct |
10 |
Correct |
17 ms |
14460 KB |
Output is correct |
11 |
Correct |
15 ms |
14456 KB |
Output is correct |
12 |
Correct |
14 ms |
14464 KB |
Output is correct |
13 |
Correct |
15 ms |
14584 KB |
Output is correct |
14 |
Correct |
15 ms |
14456 KB |
Output is correct |
15 |
Correct |
15 ms |
14584 KB |
Output is correct |
16 |
Correct |
15 ms |
14456 KB |
Output is correct |
17 |
Correct |
15 ms |
14456 KB |
Output is correct |
18 |
Correct |
14 ms |
14456 KB |
Output is correct |
19 |
Correct |
13 ms |
14456 KB |
Output is correct |
20 |
Correct |
14 ms |
14456 KB |
Output is correct |
21 |
Correct |
15 ms |
14456 KB |
Output is correct |
22 |
Correct |
14 ms |
14460 KB |
Output is correct |
23 |
Correct |
14 ms |
14456 KB |
Output is correct |
24 |
Correct |
15 ms |
14492 KB |
Output is correct |
25 |
Correct |
110 ms |
19188 KB |
Output is correct |
26 |
Correct |
31 ms |
15096 KB |
Output is correct |
27 |
Correct |
159 ms |
21240 KB |
Output is correct |
28 |
Correct |
166 ms |
21368 KB |
Output is correct |
29 |
Correct |
111 ms |
19192 KB |
Output is correct |
30 |
Correct |
120 ms |
18948 KB |
Output is correct |
31 |
Correct |
125 ms |
20344 KB |
Output is correct |
32 |
Correct |
178 ms |
21364 KB |
Output is correct |
33 |
Correct |
151 ms |
20856 KB |
Output is correct |
34 |
Correct |
94 ms |
17784 KB |
Output is correct |
35 |
Correct |
157 ms |
21232 KB |
Output is correct |
36 |
Correct |
166 ms |
21296 KB |
Output is correct |
37 |
Correct |
100 ms |
17912 KB |
Output is correct |
38 |
Correct |
160 ms |
20344 KB |
Output is correct |
39 |
Correct |
36 ms |
15352 KB |
Output is correct |
40 |
Correct |
159 ms |
20444 KB |
Output is correct |
41 |
Correct |
116 ms |
18680 KB |
Output is correct |
42 |
Correct |
156 ms |
20392 KB |
Output is correct |
43 |
Correct |
62 ms |
16532 KB |
Output is correct |
44 |
Correct |
152 ms |
20348 KB |
Output is correct |
45 |
Correct |
41 ms |
15608 KB |
Output is correct |
46 |
Correct |
151 ms |
20344 KB |
Output is correct |
47 |
Correct |
55 ms |
15992 KB |
Output is correct |
48 |
Correct |
153 ms |
20364 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
643 ms |
30100 KB |
Output is correct |
2 |
Correct |
659 ms |
35192 KB |
Output is correct |
3 |
Correct |
444 ms |
32092 KB |
Output is correct |
4 |
Correct |
676 ms |
35236 KB |
Output is correct |
5 |
Correct |
297 ms |
24188 KB |
Output is correct |
6 |
Correct |
681 ms |
35164 KB |
Output is correct |
7 |
Correct |
597 ms |
33792 KB |
Output is correct |
8 |
Correct |
679 ms |
35176 KB |
Output is correct |
9 |
Correct |
95 ms |
17272 KB |
Output is correct |
10 |
Correct |
675 ms |
35136 KB |
Output is correct |
11 |
Correct |
395 ms |
26104 KB |
Output is correct |
12 |
Correct |
677 ms |
35116 KB |
Output is correct |
13 |
Correct |
290 ms |
32596 KB |
Output is correct |
14 |
Correct |
269 ms |
32596 KB |
Output is correct |
15 |
Correct |
267 ms |
32636 KB |
Output is correct |
16 |
Correct |
244 ms |
33336 KB |
Output is correct |
17 |
Correct |
292 ms |
32780 KB |
Output is correct |
18 |
Correct |
266 ms |
33104 KB |
Output is correct |
19 |
Correct |
287 ms |
32596 KB |
Output is correct |
20 |
Correct |
277 ms |
32496 KB |
Output is correct |
21 |
Correct |
259 ms |
32364 KB |
Output is correct |
22 |
Correct |
362 ms |
32568 KB |
Output is correct |
23 |
Correct |
278 ms |
32628 KB |
Output is correct |
24 |
Correct |
244 ms |
32916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
15 ms |
14372 KB |
Output is correct |
2 |
Correct |
15 ms |
14460 KB |
Output is correct |
3 |
Correct |
15 ms |
14456 KB |
Output is correct |
4 |
Correct |
15 ms |
14456 KB |
Output is correct |
5 |
Correct |
17 ms |
14456 KB |
Output is correct |
6 |
Correct |
15 ms |
14460 KB |
Output is correct |
7 |
Correct |
15 ms |
14456 KB |
Output is correct |
8 |
Correct |
18 ms |
14388 KB |
Output is correct |
9 |
Correct |
15 ms |
14456 KB |
Output is correct |
10 |
Correct |
17 ms |
14460 KB |
Output is correct |
11 |
Correct |
15 ms |
14456 KB |
Output is correct |
12 |
Correct |
14 ms |
14464 KB |
Output is correct |
13 |
Correct |
15 ms |
14584 KB |
Output is correct |
14 |
Correct |
15 ms |
14456 KB |
Output is correct |
15 |
Correct |
15 ms |
14584 KB |
Output is correct |
16 |
Correct |
15 ms |
14456 KB |
Output is correct |
17 |
Correct |
15 ms |
14456 KB |
Output is correct |
18 |
Correct |
14 ms |
14456 KB |
Output is correct |
19 |
Correct |
13 ms |
14456 KB |
Output is correct |
20 |
Correct |
14 ms |
14456 KB |
Output is correct |
21 |
Correct |
15 ms |
14456 KB |
Output is correct |
22 |
Correct |
14 ms |
14460 KB |
Output is correct |
23 |
Correct |
14 ms |
14456 KB |
Output is correct |
24 |
Correct |
15 ms |
14492 KB |
Output is correct |
25 |
Correct |
110 ms |
19188 KB |
Output is correct |
26 |
Correct |
31 ms |
15096 KB |
Output is correct |
27 |
Correct |
159 ms |
21240 KB |
Output is correct |
28 |
Correct |
166 ms |
21368 KB |
Output is correct |
29 |
Correct |
111 ms |
19192 KB |
Output is correct |
30 |
Correct |
120 ms |
18948 KB |
Output is correct |
31 |
Correct |
125 ms |
20344 KB |
Output is correct |
32 |
Correct |
178 ms |
21364 KB |
Output is correct |
33 |
Correct |
151 ms |
20856 KB |
Output is correct |
34 |
Correct |
94 ms |
17784 KB |
Output is correct |
35 |
Correct |
157 ms |
21232 KB |
Output is correct |
36 |
Correct |
166 ms |
21296 KB |
Output is correct |
37 |
Correct |
100 ms |
17912 KB |
Output is correct |
38 |
Correct |
160 ms |
20344 KB |
Output is correct |
39 |
Correct |
36 ms |
15352 KB |
Output is correct |
40 |
Correct |
159 ms |
20444 KB |
Output is correct |
41 |
Correct |
116 ms |
18680 KB |
Output is correct |
42 |
Correct |
156 ms |
20392 KB |
Output is correct |
43 |
Correct |
62 ms |
16532 KB |
Output is correct |
44 |
Correct |
152 ms |
20348 KB |
Output is correct |
45 |
Correct |
41 ms |
15608 KB |
Output is correct |
46 |
Correct |
151 ms |
20344 KB |
Output is correct |
47 |
Correct |
55 ms |
15992 KB |
Output is correct |
48 |
Correct |
153 ms |
20364 KB |
Output is correct |
49 |
Correct |
643 ms |
30100 KB |
Output is correct |
50 |
Correct |
659 ms |
35192 KB |
Output is correct |
51 |
Correct |
444 ms |
32092 KB |
Output is correct |
52 |
Correct |
676 ms |
35236 KB |
Output is correct |
53 |
Correct |
297 ms |
24188 KB |
Output is correct |
54 |
Correct |
681 ms |
35164 KB |
Output is correct |
55 |
Correct |
597 ms |
33792 KB |
Output is correct |
56 |
Correct |
679 ms |
35176 KB |
Output is correct |
57 |
Correct |
95 ms |
17272 KB |
Output is correct |
58 |
Correct |
675 ms |
35136 KB |
Output is correct |
59 |
Correct |
395 ms |
26104 KB |
Output is correct |
60 |
Correct |
677 ms |
35116 KB |
Output is correct |
61 |
Correct |
290 ms |
32596 KB |
Output is correct |
62 |
Correct |
269 ms |
32596 KB |
Output is correct |
63 |
Correct |
267 ms |
32636 KB |
Output is correct |
64 |
Correct |
244 ms |
33336 KB |
Output is correct |
65 |
Correct |
292 ms |
32780 KB |
Output is correct |
66 |
Correct |
266 ms |
33104 KB |
Output is correct |
67 |
Correct |
287 ms |
32596 KB |
Output is correct |
68 |
Correct |
277 ms |
32496 KB |
Output is correct |
69 |
Correct |
259 ms |
32364 KB |
Output is correct |
70 |
Correct |
362 ms |
32568 KB |
Output is correct |
71 |
Correct |
278 ms |
32628 KB |
Output is correct |
72 |
Correct |
244 ms |
32916 KB |
Output is correct |
73 |
Correct |
952 ms |
41060 KB |
Output is correct |
74 |
Correct |
721 ms |
35924 KB |
Output is correct |
75 |
Correct |
878 ms |
40588 KB |
Output is correct |
76 |
Correct |
1111 ms |
44280 KB |
Output is correct |
77 |
Correct |
576 ms |
30440 KB |
Output is correct |
78 |
Correct |
1071 ms |
41480 KB |
Output is correct |
79 |
Correct |
999 ms |
42596 KB |
Output is correct |
80 |
Correct |
1108 ms |
44252 KB |
Output is correct |
81 |
Correct |
387 ms |
24568 KB |
Output is correct |
82 |
Correct |
959 ms |
39828 KB |
Output is correct |
83 |
Correct |
788 ms |
34544 KB |
Output is correct |
84 |
Correct |
1101 ms |
44240 KB |
Output is correct |
85 |
Correct |
454 ms |
37336 KB |
Output is correct |
86 |
Correct |
599 ms |
40596 KB |
Output is correct |
87 |
Correct |
314 ms |
34040 KB |
Output is correct |
88 |
Correct |
561 ms |
41168 KB |
Output is correct |
89 |
Correct |
494 ms |
38772 KB |
Output is correct |
90 |
Correct |
551 ms |
41068 KB |
Output is correct |
91 |
Correct |
380 ms |
35408 KB |
Output is correct |
92 |
Correct |
627 ms |
40668 KB |
Output is correct |
93 |
Correct |
311 ms |
33876 KB |
Output is correct |
94 |
Correct |
542 ms |
40536 KB |
Output is correct |
95 |
Correct |
386 ms |
34928 KB |
Output is correct |
96 |
Correct |
533 ms |
40692 KB |
Output is correct |