#include<bits/stdc++.h>
const int N=2e5+2;
const int inf=1e9+7;
using namespace std;
vector<int> que_lis[N];
vector<pair<int,bool> > event[N];
int c[4*N],d[4*N],lazy[4*N],ar[N],ans[N],ranl[N],ranr[N];
pair<int,int> que[N];
void init(int idx,int l,int r){
c[idx]=-inf;
d[idx]=-inf;
lazy[idx]=-inf;
if(l==r){
return;
}
int mid=(l+r)>>1;
init(idx<<1,l,mid);
init(idx<<1|1,mid+1,r);
}
void push(int idx,int l,int r){
lazy[idx<<1]=max(lazy[idx<<1],lazy[idx]);
lazy[idx<<1|1]=max(lazy[idx<<1|1],lazy[idx]);
d[idx<<1]=max(c[idx<<1]+lazy[idx<<1],d[idx<<1]);
d[idx<<1|1]=max(c[idx<<1|1]+lazy[idx<<1|1],d[idx<<1|1]);
lazy[idx]=-inf;
}
void upd(int idx,int l,int r,int pos,bool haiz){
if(l>pos||r<pos){
return;
}
if(l==r){
if(haiz){
c[idx]=ar[pos];
}
else{
d[idx]=max(d[idx],c[idx]+lazy[idx]);
c[idx]=-inf;
}
lazy[idx]=-inf;
return;
}
if(lazy[idx]!=-inf){
push(idx,l,r);
}
int mid=(l+r)>>1;
upd(idx<<1,l,mid,pos,haiz);
upd(idx<<1|1,mid+1,r,pos,haiz);
c[idx]=max(c[idx<<1],c[idx<<1|1]);
d[idx]=max(max(c[idx]+lazy[idx],d[idx]),max(d[idx<<1],d[idx<<1|1]));
}
void upd1(int idx,int l,int r,int lef,int rig,int val){
if(l>rig||r<lef){
return;
}
if(l>=lef&&r<=rig){
lazy[idx]=max(lazy[idx],val);
val=-inf;
if(l!=r){
val=max(d[idx<<1],d[idx<<1|1]);
}
d[idx]=max(max(c[idx]+lazy[idx],d[idx]),val);
return;
}
if(lazy[idx]!=-inf){
push(idx,l,r);
}
int mid=(l+r)>>1;
upd1(idx<<1,l,mid,lef,rig,val);
upd1(idx<<1|1,mid+1,r,lef,rig,val);
d[idx]=max(max(c[idx]+lazy[idx],d[idx]),max(d[idx<<1],d[idx<<1|1]));
}
int getmax(int idx,int l,int r,int lef,int rig){
if(l>rig||r<lef){
return -inf;
}
if(l>=lef&&r<=rig){
return d[idx];
}
if(lazy[idx]!=-inf){
push(idx,l,r);
}
int mid=(l+r)>>1;
return max(getmax(idx<<1,l,mid,lef,rig),getmax(idx<<1|1,mid+1,r,lef,rig));
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
int n,i,j,k,l,q;
cin>>n;
init(1,1,n);
for(i=1;i<=n;i++){
cin>>ar[i]>>ranl[i]>>ranr[i];
ranr[i]++;
if(i+ranl[i]<=n){
event[i+ranl[i]].push_back({i,true});
}
if(i+ranr[i]<=n){
event[i+ranr[i]].push_back({i,false});
}
}
cin>>q;
for(i=1;i<=q;i++){
ans[i]=-1;
cin>>que[i].first>>que[i].second;
que_lis[que[i].second].push_back(i);
}
for(i=1;i<=n;i++){
for(j=0;j<event[i].size();j++){
upd(1,1,n,event[i][j].first,event[i][j].second);
}
if(i-ranl[i]>0){
upd1(1,1,n,max(1,i-ranr[i]+1),i-ranl[i],-ar[i]);
}
for(j=0;j<que_lis[i].size();j++){
// cout<<que_lis[i][j]<<' '<<getmax(1,1,n,que[que_lis[i][j]].first,i)<<endl;
ans[que_lis[i][j]]=max(ans[que_lis[i][j]],getmax(1,1,n,que[que_lis[i][j]].first,i));
}
event[i].clear();
que_lis[i].clear();
}
init(1,1,n);
for(i=n;i>=1;i--){
if(i-ranl[i]>0){
event[i-ranl[i]].push_back({i,true});
}
if(i-ranr[i]>0){
event[i-ranr[i]].push_back({i,false});
}
}
for(i=1;i<=q;i++){
que_lis[que[i].first].push_back(i);
}
for(i=n;i>=1;i--){
for(j=0;j<event[i].size();j++){
upd(1,1,n,event[i][j].first,event[i][j].second);
}
if(i+ranl[i]<=n){
upd1(1,1,n,i+ranl[i],min(i+ranr[i]-1,n),-ar[i]);
}
for(j=0;j<que_lis[i].size();j++){
ans[que_lis[i][j]]=max(ans[que_lis[i][j]],getmax(1,1,n,i,que[que_lis[i][j]].second));
}
}
for(i=1;i<=q;i++){
cout<<ans[i]<<'\n';
}
}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
5
1 2
2 3
1 3
1 4
1 5
*/
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:108:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<event[i].size();j++){
~^~~~~~~~~~~~~~~~
antennas.cpp:114:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<que_lis[i].size();j++){
~^~~~~~~~~~~~~~~~~~
antennas.cpp:134:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<event[i].size();j++){
~^~~~~~~~~~~~~~~~
antennas.cpp:140:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(j=0;j<que_lis[i].size();j++){
~^~~~~~~~~~~~~~~~~~
antennas.cpp:88:12: warning: unused variable 'k' [-Wunused-variable]
int n,i,j,k,l,q;
^
antennas.cpp:88:14: warning: unused variable 'l' [-Wunused-variable]
int n,i,j,k,l,q;
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
Output is correct |
2 |
Correct |
10 ms |
9848 KB |
Output is correct |
3 |
Correct |
11 ms |
9848 KB |
Output is correct |
4 |
Correct |
10 ms |
9848 KB |
Output is correct |
5 |
Correct |
11 ms |
9836 KB |
Output is correct |
6 |
Correct |
11 ms |
9848 KB |
Output is correct |
7 |
Correct |
11 ms |
9848 KB |
Output is correct |
8 |
Correct |
11 ms |
9848 KB |
Output is correct |
9 |
Correct |
12 ms |
9848 KB |
Output is correct |
10 |
Correct |
11 ms |
9848 KB |
Output is correct |
11 |
Correct |
11 ms |
9720 KB |
Output is correct |
12 |
Correct |
11 ms |
9852 KB |
Output is correct |
13 |
Correct |
11 ms |
9820 KB |
Output is correct |
14 |
Correct |
13 ms |
9772 KB |
Output is correct |
15 |
Correct |
11 ms |
9848 KB |
Output is correct |
16 |
Correct |
11 ms |
9848 KB |
Output is correct |
17 |
Correct |
10 ms |
9848 KB |
Output is correct |
18 |
Correct |
12 ms |
9976 KB |
Output is correct |
19 |
Correct |
11 ms |
9848 KB |
Output is correct |
20 |
Correct |
11 ms |
9868 KB |
Output is correct |
21 |
Correct |
10 ms |
9852 KB |
Output is correct |
22 |
Correct |
11 ms |
9848 KB |
Output is correct |
23 |
Correct |
11 ms |
9848 KB |
Output is correct |
24 |
Correct |
10 ms |
9848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
Output is correct |
2 |
Correct |
10 ms |
9848 KB |
Output is correct |
3 |
Correct |
11 ms |
9848 KB |
Output is correct |
4 |
Correct |
10 ms |
9848 KB |
Output is correct |
5 |
Correct |
11 ms |
9836 KB |
Output is correct |
6 |
Correct |
11 ms |
9848 KB |
Output is correct |
7 |
Correct |
11 ms |
9848 KB |
Output is correct |
8 |
Correct |
11 ms |
9848 KB |
Output is correct |
9 |
Correct |
12 ms |
9848 KB |
Output is correct |
10 |
Correct |
11 ms |
9848 KB |
Output is correct |
11 |
Correct |
11 ms |
9720 KB |
Output is correct |
12 |
Correct |
11 ms |
9852 KB |
Output is correct |
13 |
Correct |
11 ms |
9820 KB |
Output is correct |
14 |
Correct |
13 ms |
9772 KB |
Output is correct |
15 |
Correct |
11 ms |
9848 KB |
Output is correct |
16 |
Correct |
11 ms |
9848 KB |
Output is correct |
17 |
Correct |
10 ms |
9848 KB |
Output is correct |
18 |
Correct |
12 ms |
9976 KB |
Output is correct |
19 |
Correct |
11 ms |
9848 KB |
Output is correct |
20 |
Correct |
11 ms |
9868 KB |
Output is correct |
21 |
Correct |
10 ms |
9852 KB |
Output is correct |
22 |
Correct |
11 ms |
9848 KB |
Output is correct |
23 |
Correct |
11 ms |
9848 KB |
Output is correct |
24 |
Correct |
10 ms |
9848 KB |
Output is correct |
25 |
Correct |
116 ms |
15304 KB |
Output is correct |
26 |
Correct |
26 ms |
10616 KB |
Output is correct |
27 |
Correct |
172 ms |
17444 KB |
Output is correct |
28 |
Correct |
177 ms |
17436 KB |
Output is correct |
29 |
Correct |
118 ms |
15224 KB |
Output is correct |
30 |
Correct |
123 ms |
15080 KB |
Output is correct |
31 |
Correct |
138 ms |
16764 KB |
Output is correct |
32 |
Correct |
186 ms |
17380 KB |
Output is correct |
33 |
Correct |
161 ms |
17144 KB |
Output is correct |
34 |
Correct |
95 ms |
13716 KB |
Output is correct |
35 |
Correct |
175 ms |
17500 KB |
Output is correct |
36 |
Correct |
178 ms |
17364 KB |
Output is correct |
37 |
Correct |
100 ms |
13688 KB |
Output is correct |
38 |
Correct |
173 ms |
16520 KB |
Output is correct |
39 |
Correct |
35 ms |
10872 KB |
Output is correct |
40 |
Correct |
170 ms |
16376 KB |
Output is correct |
41 |
Correct |
125 ms |
14840 KB |
Output is correct |
42 |
Correct |
169 ms |
16376 KB |
Output is correct |
43 |
Correct |
64 ms |
12124 KB |
Output is correct |
44 |
Correct |
177 ms |
16504 KB |
Output is correct |
45 |
Correct |
40 ms |
11128 KB |
Output is correct |
46 |
Correct |
174 ms |
16504 KB |
Output is correct |
47 |
Correct |
57 ms |
11640 KB |
Output is correct |
48 |
Correct |
177 ms |
16532 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
468 ms |
26976 KB |
Output is correct |
2 |
Correct |
533 ms |
28196 KB |
Output is correct |
3 |
Correct |
364 ms |
24620 KB |
Output is correct |
4 |
Correct |
529 ms |
28184 KB |
Output is correct |
5 |
Correct |
216 ms |
18424 KB |
Output is correct |
6 |
Correct |
541 ms |
28204 KB |
Output is correct |
7 |
Correct |
449 ms |
26488 KB |
Output is correct |
8 |
Correct |
516 ms |
28284 KB |
Output is correct |
9 |
Correct |
70 ms |
12408 KB |
Output is correct |
10 |
Correct |
514 ms |
28280 KB |
Output is correct |
11 |
Correct |
465 ms |
20424 KB |
Output is correct |
12 |
Correct |
512 ms |
28304 KB |
Output is correct |
13 |
Correct |
340 ms |
27884 KB |
Output is correct |
14 |
Correct |
315 ms |
27544 KB |
Output is correct |
15 |
Correct |
312 ms |
26512 KB |
Output is correct |
16 |
Correct |
291 ms |
26568 KB |
Output is correct |
17 |
Correct |
355 ms |
28180 KB |
Output is correct |
18 |
Correct |
358 ms |
27436 KB |
Output is correct |
19 |
Correct |
336 ms |
27372 KB |
Output is correct |
20 |
Correct |
325 ms |
27340 KB |
Output is correct |
21 |
Correct |
301 ms |
27372 KB |
Output is correct |
22 |
Correct |
320 ms |
27140 KB |
Output is correct |
23 |
Correct |
326 ms |
27356 KB |
Output is correct |
24 |
Correct |
295 ms |
26220 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
9848 KB |
Output is correct |
2 |
Correct |
10 ms |
9848 KB |
Output is correct |
3 |
Correct |
11 ms |
9848 KB |
Output is correct |
4 |
Correct |
10 ms |
9848 KB |
Output is correct |
5 |
Correct |
11 ms |
9836 KB |
Output is correct |
6 |
Correct |
11 ms |
9848 KB |
Output is correct |
7 |
Correct |
11 ms |
9848 KB |
Output is correct |
8 |
Correct |
11 ms |
9848 KB |
Output is correct |
9 |
Correct |
12 ms |
9848 KB |
Output is correct |
10 |
Correct |
11 ms |
9848 KB |
Output is correct |
11 |
Correct |
11 ms |
9720 KB |
Output is correct |
12 |
Correct |
11 ms |
9852 KB |
Output is correct |
13 |
Correct |
11 ms |
9820 KB |
Output is correct |
14 |
Correct |
13 ms |
9772 KB |
Output is correct |
15 |
Correct |
11 ms |
9848 KB |
Output is correct |
16 |
Correct |
11 ms |
9848 KB |
Output is correct |
17 |
Correct |
10 ms |
9848 KB |
Output is correct |
18 |
Correct |
12 ms |
9976 KB |
Output is correct |
19 |
Correct |
11 ms |
9848 KB |
Output is correct |
20 |
Correct |
11 ms |
9868 KB |
Output is correct |
21 |
Correct |
10 ms |
9852 KB |
Output is correct |
22 |
Correct |
11 ms |
9848 KB |
Output is correct |
23 |
Correct |
11 ms |
9848 KB |
Output is correct |
24 |
Correct |
10 ms |
9848 KB |
Output is correct |
25 |
Correct |
116 ms |
15304 KB |
Output is correct |
26 |
Correct |
26 ms |
10616 KB |
Output is correct |
27 |
Correct |
172 ms |
17444 KB |
Output is correct |
28 |
Correct |
177 ms |
17436 KB |
Output is correct |
29 |
Correct |
118 ms |
15224 KB |
Output is correct |
30 |
Correct |
123 ms |
15080 KB |
Output is correct |
31 |
Correct |
138 ms |
16764 KB |
Output is correct |
32 |
Correct |
186 ms |
17380 KB |
Output is correct |
33 |
Correct |
161 ms |
17144 KB |
Output is correct |
34 |
Correct |
95 ms |
13716 KB |
Output is correct |
35 |
Correct |
175 ms |
17500 KB |
Output is correct |
36 |
Correct |
178 ms |
17364 KB |
Output is correct |
37 |
Correct |
100 ms |
13688 KB |
Output is correct |
38 |
Correct |
173 ms |
16520 KB |
Output is correct |
39 |
Correct |
35 ms |
10872 KB |
Output is correct |
40 |
Correct |
170 ms |
16376 KB |
Output is correct |
41 |
Correct |
125 ms |
14840 KB |
Output is correct |
42 |
Correct |
169 ms |
16376 KB |
Output is correct |
43 |
Correct |
64 ms |
12124 KB |
Output is correct |
44 |
Correct |
177 ms |
16504 KB |
Output is correct |
45 |
Correct |
40 ms |
11128 KB |
Output is correct |
46 |
Correct |
174 ms |
16504 KB |
Output is correct |
47 |
Correct |
57 ms |
11640 KB |
Output is correct |
48 |
Correct |
177 ms |
16532 KB |
Output is correct |
49 |
Correct |
468 ms |
26976 KB |
Output is correct |
50 |
Correct |
533 ms |
28196 KB |
Output is correct |
51 |
Correct |
364 ms |
24620 KB |
Output is correct |
52 |
Correct |
529 ms |
28184 KB |
Output is correct |
53 |
Correct |
216 ms |
18424 KB |
Output is correct |
54 |
Correct |
541 ms |
28204 KB |
Output is correct |
55 |
Correct |
449 ms |
26488 KB |
Output is correct |
56 |
Correct |
516 ms |
28284 KB |
Output is correct |
57 |
Correct |
70 ms |
12408 KB |
Output is correct |
58 |
Correct |
514 ms |
28280 KB |
Output is correct |
59 |
Correct |
465 ms |
20424 KB |
Output is correct |
60 |
Correct |
512 ms |
28304 KB |
Output is correct |
61 |
Correct |
340 ms |
27884 KB |
Output is correct |
62 |
Correct |
315 ms |
27544 KB |
Output is correct |
63 |
Correct |
312 ms |
26512 KB |
Output is correct |
64 |
Correct |
291 ms |
26568 KB |
Output is correct |
65 |
Correct |
355 ms |
28180 KB |
Output is correct |
66 |
Correct |
358 ms |
27436 KB |
Output is correct |
67 |
Correct |
336 ms |
27372 KB |
Output is correct |
68 |
Correct |
325 ms |
27340 KB |
Output is correct |
69 |
Correct |
301 ms |
27372 KB |
Output is correct |
70 |
Correct |
320 ms |
27140 KB |
Output is correct |
71 |
Correct |
326 ms |
27356 KB |
Output is correct |
72 |
Correct |
295 ms |
26220 KB |
Output is correct |
73 |
Correct |
763 ms |
36392 KB |
Output is correct |
74 |
Correct |
567 ms |
29552 KB |
Output is correct |
75 |
Correct |
793 ms |
35400 KB |
Output is correct |
76 |
Correct |
961 ms |
40312 KB |
Output is correct |
77 |
Correct |
469 ms |
26204 KB |
Output is correct |
78 |
Correct |
799 ms |
37240 KB |
Output is correct |
79 |
Correct |
866 ms |
38208 KB |
Output is correct |
80 |
Correct |
969 ms |
40360 KB |
Output is correct |
81 |
Correct |
349 ms |
20956 KB |
Output is correct |
82 |
Correct |
758 ms |
35248 KB |
Output is correct |
83 |
Correct |
681 ms |
31096 KB |
Output is correct |
84 |
Correct |
1031 ms |
40396 KB |
Output is correct |
85 |
Correct |
575 ms |
35000 KB |
Output is correct |
86 |
Correct |
732 ms |
38332 KB |
Output is correct |
87 |
Correct |
385 ms |
28752 KB |
Output is correct |
88 |
Correct |
666 ms |
37696 KB |
Output is correct |
89 |
Correct |
649 ms |
36848 KB |
Output is correct |
90 |
Correct |
705 ms |
38340 KB |
Output is correct |
91 |
Correct |
469 ms |
31980 KB |
Output is correct |
92 |
Correct |
698 ms |
38252 KB |
Output is correct |
93 |
Correct |
402 ms |
29928 KB |
Output is correct |
94 |
Correct |
694 ms |
38128 KB |
Output is correct |
95 |
Correct |
437 ms |
31336 KB |
Output is correct |
96 |
Correct |
727 ms |
37248 KB |
Output is correct |