#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double db;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef pair<db,db> pdb;
typedef tuple<int,int,int,int> TP;
typedef vector<vector<ll>> mat;
const ll mod=1e9+7;
const int N=2e5+5,INF=1e9+5;
int n,q,h[N],a[N],b[N],qs[N],qe[N],ans[N];
struct node{
int lazy,mxd,mnh;
node(){
lazy=-INF; mxd=-INF; mnh=INF;
}
};
int ANS=806460109;
struct seg{
node tree[4*N];
void pushdown(int nd,int l,int r){
tree[nd].mxd=max(tree[nd].mxd,tree[nd].lazy-tree[nd].mnh);
if(l!=r){
tree[nd<<1].lazy=max(tree[nd<<1].lazy,tree[nd].lazy);
tree[nd<<1|1].lazy=max(tree[nd<<1|1].lazy,tree[nd].lazy);
}
tree[nd].lazy=-INF;
}
void upd1(int nd,int l,int r,int s,int e,int v){
pushdown(nd,l,r);
if(r<s||e<l) return;
if(s<=l&&r<=e){
tree[nd].lazy=v;
pushdown(nd,l,r);
return;
}
int m=(l+r)>>1;
upd1(nd<<1,l,m,s,e,v); upd1(nd<<1|1,m+1,r,s,e,v);
tree[nd].mxd=max(tree[nd<<1].mxd,tree[nd<<1|1].mxd); tree[nd].mnh=min(tree[nd<<1].mnh,tree[nd<<1|1].mnh);
}
void upd2(int nd,int l,int r,int x,int v){
pushdown(nd,l,r);
if(r<x||x<l) return;
if(l==r){
tree[nd].mnh=v;
return;
}
int m=(l+r)>>1;
upd2(nd<<1,l,m,x,v); upd2(nd<<1|1,m+1,r,x,v);
tree[nd].mxd=max(tree[nd<<1].mxd,tree[nd<<1|1].mxd); tree[nd].mnh=min(tree[nd<<1].mnh,tree[nd<<1|1].mnh);
}
int qry(int nd,int l,int r,int s,int e){
pushdown(nd,l,r);
if(r<s||e<l) return -INF;
if(s<=l&&r<=e) return tree[nd].mxd;
int m=(l+r)>>1;
return max(qry(nd<<1,l,m,s,e),qry(nd<<1|1,m+1,r,s,e));
}
};
void solve(){
vector<pii> events;
vector<int> queries[N];
seg tree;
for(int i=1;i<=n;i++){
events.emplace_back(i+a[i],i);
events.emplace_back(i+b[i]+1,-i);
}
for(int i=1;i<=q;i++){
queries[qe[i]].emplace_back(i);
}
sort(events.begin(),events.end());
for(int i=1,j=0;i<=n;i++){
while(j<events.size()&&events[j].fi==i){
int p=events[j].se; j++;
if(p>0) tree.upd2(1,1,n,p,h[p]);
else tree.upd2(1,1,n,-p,INF);
}
if(i-a[i]>=1) tree.upd1(1,1,n,max(1,i-b[i]),i-a[i],h[i]);
for(auto &it : queries[i]) ans[it]=max(ans[it],tree.qry(1,1,n,qs[it],qe[it]));
}
}
int main(){
ios::sync_with_stdio(0); cin.tie(0);
cin>>n;
for(int i=1;i<=n;i++) cin>>h[i]>>a[i]>>b[i];
cin>>q;
for(int i=1;i<=q;i++){
cin>>qs[i]>>qe[i];
ans[i]=-1;
}
solve();
for(int i=1;i<=q;i++){
qs[i]=n+1-qs[i];
qe[i]=n+1-qe[i];
swap(qs[i],qe[i]);
}
reverse(h+1,h+1+n); reverse(a+1,a+1+n); reverse(b+1,b+1+n);
solve();
for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
return 0;
}
Compilation message
antennas.cpp: In function 'void solve()':
antennas.cpp:76:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while(j<events.size()&&events[j].fi==i){
~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
14480 KB |
Output is correct |
2 |
Correct |
17 ms |
14456 KB |
Output is correct |
3 |
Correct |
16 ms |
14456 KB |
Output is correct |
4 |
Correct |
16 ms |
14456 KB |
Output is correct |
5 |
Correct |
16 ms |
14456 KB |
Output is correct |
6 |
Correct |
16 ms |
14472 KB |
Output is correct |
7 |
Correct |
17 ms |
14456 KB |
Output is correct |
8 |
Correct |
17 ms |
14456 KB |
Output is correct |
9 |
Correct |
17 ms |
14456 KB |
Output is correct |
10 |
Correct |
17 ms |
14428 KB |
Output is correct |
11 |
Correct |
16 ms |
14504 KB |
Output is correct |
12 |
Correct |
16 ms |
14456 KB |
Output is correct |
13 |
Correct |
16 ms |
14480 KB |
Output is correct |
14 |
Correct |
17 ms |
14408 KB |
Output is correct |
15 |
Correct |
16 ms |
14456 KB |
Output is correct |
16 |
Correct |
16 ms |
14456 KB |
Output is correct |
17 |
Correct |
17 ms |
14456 KB |
Output is correct |
18 |
Correct |
17 ms |
14456 KB |
Output is correct |
19 |
Correct |
16 ms |
14456 KB |
Output is correct |
20 |
Correct |
16 ms |
14456 KB |
Output is correct |
21 |
Correct |
16 ms |
14456 KB |
Output is correct |
22 |
Correct |
16 ms |
14456 KB |
Output is correct |
23 |
Correct |
17 ms |
14432 KB |
Output is correct |
24 |
Correct |
17 ms |
14456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
14480 KB |
Output is correct |
2 |
Correct |
17 ms |
14456 KB |
Output is correct |
3 |
Correct |
16 ms |
14456 KB |
Output is correct |
4 |
Correct |
16 ms |
14456 KB |
Output is correct |
5 |
Correct |
16 ms |
14456 KB |
Output is correct |
6 |
Correct |
16 ms |
14472 KB |
Output is correct |
7 |
Correct |
17 ms |
14456 KB |
Output is correct |
8 |
Correct |
17 ms |
14456 KB |
Output is correct |
9 |
Correct |
17 ms |
14456 KB |
Output is correct |
10 |
Correct |
17 ms |
14428 KB |
Output is correct |
11 |
Correct |
16 ms |
14504 KB |
Output is correct |
12 |
Correct |
16 ms |
14456 KB |
Output is correct |
13 |
Correct |
16 ms |
14480 KB |
Output is correct |
14 |
Correct |
17 ms |
14408 KB |
Output is correct |
15 |
Correct |
16 ms |
14456 KB |
Output is correct |
16 |
Correct |
16 ms |
14456 KB |
Output is correct |
17 |
Correct |
17 ms |
14456 KB |
Output is correct |
18 |
Correct |
17 ms |
14456 KB |
Output is correct |
19 |
Correct |
16 ms |
14456 KB |
Output is correct |
20 |
Correct |
16 ms |
14456 KB |
Output is correct |
21 |
Correct |
16 ms |
14456 KB |
Output is correct |
22 |
Correct |
16 ms |
14456 KB |
Output is correct |
23 |
Correct |
17 ms |
14432 KB |
Output is correct |
24 |
Correct |
17 ms |
14456 KB |
Output is correct |
25 |
Correct |
148 ms |
18700 KB |
Output is correct |
26 |
Correct |
34 ms |
15084 KB |
Output is correct |
27 |
Correct |
216 ms |
20420 KB |
Output is correct |
28 |
Correct |
219 ms |
20592 KB |
Output is correct |
29 |
Correct |
145 ms |
18768 KB |
Output is correct |
30 |
Correct |
149 ms |
18520 KB |
Output is correct |
31 |
Correct |
164 ms |
19852 KB |
Output is correct |
32 |
Correct |
219 ms |
20484 KB |
Output is correct |
33 |
Correct |
195 ms |
20112 KB |
Output is correct |
34 |
Correct |
114 ms |
17472 KB |
Output is correct |
35 |
Correct |
219 ms |
20408 KB |
Output is correct |
36 |
Correct |
214 ms |
20572 KB |
Output is correct |
37 |
Correct |
131 ms |
17672 KB |
Output is correct |
38 |
Correct |
221 ms |
19860 KB |
Output is correct |
39 |
Correct |
46 ms |
15400 KB |
Output is correct |
40 |
Correct |
215 ms |
19948 KB |
Output is correct |
41 |
Correct |
161 ms |
18648 KB |
Output is correct |
42 |
Correct |
224 ms |
20044 KB |
Output is correct |
43 |
Correct |
81 ms |
16440 KB |
Output is correct |
44 |
Correct |
219 ms |
19964 KB |
Output is correct |
45 |
Correct |
51 ms |
15480 KB |
Output is correct |
46 |
Correct |
209 ms |
19960 KB |
Output is correct |
47 |
Correct |
67 ms |
16024 KB |
Output is correct |
48 |
Correct |
212 ms |
19968 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
394 ms |
25408 KB |
Output is correct |
2 |
Correct |
443 ms |
25804 KB |
Output is correct |
3 |
Correct |
302 ms |
24220 KB |
Output is correct |
4 |
Correct |
444 ms |
25880 KB |
Output is correct |
5 |
Correct |
196 ms |
20760 KB |
Output is correct |
6 |
Correct |
432 ms |
25848 KB |
Output is correct |
7 |
Correct |
373 ms |
24908 KB |
Output is correct |
8 |
Correct |
438 ms |
25876 KB |
Output is correct |
9 |
Correct |
71 ms |
16564 KB |
Output is correct |
10 |
Correct |
437 ms |
25916 KB |
Output is correct |
11 |
Correct |
261 ms |
21680 KB |
Output is correct |
12 |
Correct |
440 ms |
25584 KB |
Output is correct |
13 |
Correct |
351 ms |
25684 KB |
Output is correct |
14 |
Correct |
331 ms |
25748 KB |
Output is correct |
15 |
Correct |
328 ms |
25808 KB |
Output is correct |
16 |
Correct |
312 ms |
25796 KB |
Output is correct |
17 |
Correct |
360 ms |
25788 KB |
Output is correct |
18 |
Correct |
340 ms |
25880 KB |
Output is correct |
19 |
Correct |
348 ms |
25920 KB |
Output is correct |
20 |
Correct |
340 ms |
25816 KB |
Output is correct |
21 |
Correct |
315 ms |
25752 KB |
Output is correct |
22 |
Correct |
333 ms |
25808 KB |
Output is correct |
23 |
Correct |
339 ms |
25536 KB |
Output is correct |
24 |
Correct |
303 ms |
25404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
14480 KB |
Output is correct |
2 |
Correct |
17 ms |
14456 KB |
Output is correct |
3 |
Correct |
16 ms |
14456 KB |
Output is correct |
4 |
Correct |
16 ms |
14456 KB |
Output is correct |
5 |
Correct |
16 ms |
14456 KB |
Output is correct |
6 |
Correct |
16 ms |
14472 KB |
Output is correct |
7 |
Correct |
17 ms |
14456 KB |
Output is correct |
8 |
Correct |
17 ms |
14456 KB |
Output is correct |
9 |
Correct |
17 ms |
14456 KB |
Output is correct |
10 |
Correct |
17 ms |
14428 KB |
Output is correct |
11 |
Correct |
16 ms |
14504 KB |
Output is correct |
12 |
Correct |
16 ms |
14456 KB |
Output is correct |
13 |
Correct |
16 ms |
14480 KB |
Output is correct |
14 |
Correct |
17 ms |
14408 KB |
Output is correct |
15 |
Correct |
16 ms |
14456 KB |
Output is correct |
16 |
Correct |
16 ms |
14456 KB |
Output is correct |
17 |
Correct |
17 ms |
14456 KB |
Output is correct |
18 |
Correct |
17 ms |
14456 KB |
Output is correct |
19 |
Correct |
16 ms |
14456 KB |
Output is correct |
20 |
Correct |
16 ms |
14456 KB |
Output is correct |
21 |
Correct |
16 ms |
14456 KB |
Output is correct |
22 |
Correct |
16 ms |
14456 KB |
Output is correct |
23 |
Correct |
17 ms |
14432 KB |
Output is correct |
24 |
Correct |
17 ms |
14456 KB |
Output is correct |
25 |
Correct |
148 ms |
18700 KB |
Output is correct |
26 |
Correct |
34 ms |
15084 KB |
Output is correct |
27 |
Correct |
216 ms |
20420 KB |
Output is correct |
28 |
Correct |
219 ms |
20592 KB |
Output is correct |
29 |
Correct |
145 ms |
18768 KB |
Output is correct |
30 |
Correct |
149 ms |
18520 KB |
Output is correct |
31 |
Correct |
164 ms |
19852 KB |
Output is correct |
32 |
Correct |
219 ms |
20484 KB |
Output is correct |
33 |
Correct |
195 ms |
20112 KB |
Output is correct |
34 |
Correct |
114 ms |
17472 KB |
Output is correct |
35 |
Correct |
219 ms |
20408 KB |
Output is correct |
36 |
Correct |
214 ms |
20572 KB |
Output is correct |
37 |
Correct |
131 ms |
17672 KB |
Output is correct |
38 |
Correct |
221 ms |
19860 KB |
Output is correct |
39 |
Correct |
46 ms |
15400 KB |
Output is correct |
40 |
Correct |
215 ms |
19948 KB |
Output is correct |
41 |
Correct |
161 ms |
18648 KB |
Output is correct |
42 |
Correct |
224 ms |
20044 KB |
Output is correct |
43 |
Correct |
81 ms |
16440 KB |
Output is correct |
44 |
Correct |
219 ms |
19964 KB |
Output is correct |
45 |
Correct |
51 ms |
15480 KB |
Output is correct |
46 |
Correct |
209 ms |
19960 KB |
Output is correct |
47 |
Correct |
67 ms |
16024 KB |
Output is correct |
48 |
Correct |
212 ms |
19968 KB |
Output is correct |
49 |
Correct |
394 ms |
25408 KB |
Output is correct |
50 |
Correct |
443 ms |
25804 KB |
Output is correct |
51 |
Correct |
302 ms |
24220 KB |
Output is correct |
52 |
Correct |
444 ms |
25880 KB |
Output is correct |
53 |
Correct |
196 ms |
20760 KB |
Output is correct |
54 |
Correct |
432 ms |
25848 KB |
Output is correct |
55 |
Correct |
373 ms |
24908 KB |
Output is correct |
56 |
Correct |
438 ms |
25876 KB |
Output is correct |
57 |
Correct |
71 ms |
16564 KB |
Output is correct |
58 |
Correct |
437 ms |
25916 KB |
Output is correct |
59 |
Correct |
261 ms |
21680 KB |
Output is correct |
60 |
Correct |
440 ms |
25584 KB |
Output is correct |
61 |
Correct |
351 ms |
25684 KB |
Output is correct |
62 |
Correct |
331 ms |
25748 KB |
Output is correct |
63 |
Correct |
328 ms |
25808 KB |
Output is correct |
64 |
Correct |
312 ms |
25796 KB |
Output is correct |
65 |
Correct |
360 ms |
25788 KB |
Output is correct |
66 |
Correct |
340 ms |
25880 KB |
Output is correct |
67 |
Correct |
348 ms |
25920 KB |
Output is correct |
68 |
Correct |
340 ms |
25816 KB |
Output is correct |
69 |
Correct |
315 ms |
25752 KB |
Output is correct |
70 |
Correct |
333 ms |
25808 KB |
Output is correct |
71 |
Correct |
339 ms |
25536 KB |
Output is correct |
72 |
Correct |
303 ms |
25404 KB |
Output is correct |
73 |
Correct |
761 ms |
31172 KB |
Output is correct |
74 |
Correct |
476 ms |
28952 KB |
Output is correct |
75 |
Correct |
744 ms |
30420 KB |
Output is correct |
76 |
Correct |
920 ms |
33536 KB |
Output is correct |
77 |
Correct |
495 ms |
24744 KB |
Output is correct |
78 |
Correct |
783 ms |
31784 KB |
Output is correct |
79 |
Correct |
829 ms |
32100 KB |
Output is correct |
80 |
Correct |
926 ms |
33504 KB |
Output is correct |
81 |
Correct |
378 ms |
22288 KB |
Output is correct |
82 |
Correct |
691 ms |
30896 KB |
Output is correct |
83 |
Correct |
680 ms |
28692 KB |
Output is correct |
84 |
Correct |
947 ms |
33516 KB |
Output is correct |
85 |
Correct |
656 ms |
31340 KB |
Output is correct |
86 |
Correct |
809 ms |
33548 KB |
Output is correct |
87 |
Correct |
408 ms |
29164 KB |
Output is correct |
88 |
Correct |
793 ms |
33436 KB |
Output is correct |
89 |
Correct |
748 ms |
32092 KB |
Output is correct |
90 |
Correct |
840 ms |
33440 KB |
Output is correct |
91 |
Correct |
521 ms |
30020 KB |
Output is correct |
92 |
Correct |
842 ms |
33428 KB |
Output is correct |
93 |
Correct |
408 ms |
29244 KB |
Output is correct |
94 |
Correct |
850 ms |
33528 KB |
Output is correct |
95 |
Correct |
474 ms |
29748 KB |
Output is correct |
96 |
Correct |
788 ms |
33408 KB |
Output is correct |