//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
void setIO(string s) {
freopen((s + ".in").c_str(), "r", stdin);
freopen((s + ".out").c_str(), "w", stdout);
}
struct node{
int d,c;
};
const int mxn=2e5+5;
node segtree[mxn*4];
int lazy[mxn*4];
int n,q;
int h[mxn];
int a[mxn],b[mxn];
vector<int> st[mxn],en[mxn],enq[mxn];
int L[mxn],R[mxn];
int ans[mxn];
int inf=1e9+1;
void push(int v){
lazy[v*2]=min(lazy[v*2],lazy[v]);
lazy[v*2+1]=min(lazy[v*2+1],lazy[v]);
segtree[v*2].d=max(segtree[v*2].d,segtree[v*2].c-lazy[v]);
segtree[v*2+1].d=max(segtree[v*2+1].d,segtree[v*2+1].c-lazy[v]);
lazy[v]=inf;
}
void pull(int v){
segtree[v].c=max(segtree[v*2].c,segtree[v*2+1].c);
segtree[v].d=max(segtree[v*2].d,segtree[v*2+1].d);
}
void update(int pos,int l=1,int r=n,int v=1){
if(l==r){
segtree[v].c=h[pos];
return;
}
push(v);
int mid=(l+r)/2;
if(pos<=mid) update(pos,l,mid,v*2);
else update(pos,mid+1,r,v*2+1);
pull(v);
}
void erase(int pos,int l=1,int r=n,int v=1){
if(l==r){
segtree[v].c=-inf;
return;
}
push(v);
int mid=(l+r)/2;
if(pos<=mid) erase(pos,l,mid,v*2);
else erase(pos,mid+1,r,v*2+1);
pull(v);
}
void update2(int tl,int tr,int val,int l=1,int r=n,int v=1){
if(r<tl or tr<l){
return;
}
if(tl<=l and r<=tr){
segtree[v].d=max(segtree[v].d,segtree[v].c-val);
lazy[v]=min(lazy[v],val);
return;
}
push(v);
int mid=(l+r)/2;
update2(tl,min(mid,tr),val,l,mid,v*2);
update2(max(mid+1,tl),tr,val,mid+1,r,v*2+1);
pull(v);
}
int query(int tl,int tr,int l=1,int r=n,int v=1){
if(r<tl or tr<l){
return -1;
}
if(tl<=l and r<=tr){
return segtree[v].d;
}
push(v);
int mid=(l+r)/2;
return max(query(tl,min(mid,tr),l,mid,v*2),query(max(mid+1,tl),tr,mid+1,r,v*2+1));
}
void solve(){
for(int i=0;i<mxn*4;i++){
segtree[i].c=-inf;
lazy[i]=inf;
segtree[i].d=-1;
}
for(int i=1;i<=n;i++){
for(auto v:st[i]){
update(v);
}
for(auto v:en[i]){
erase(v);
}
int l=i-b[i];
int r=i-a[i];
if(r>=1){
l=max(l,1);
update2(l,r,h[i]);
}
for(auto v:enq[i]){
ans[v]=max(ans[v],query(L[v],R[v]));
}
}
}
int main() {_
cin>>n;
for(int i=1;i<=n;i++){
cin>>h[i]>>a[i]>>b[i];
}
cin>>q;
for(int i=0;i<q;i++){
int l,r;
cin>>l>>r;
L[i]=l,R[i]=r;
enq[r].push_back(i);
ans[i]=-1;
}
for(int i=1;i<=n;i++){
int l=i+a[i];
int r=i+b[i];
if(l>n) continue;
r=min(r,n);
st[l].push_back(i);
en[r+1].push_back(i);
}
solve();
for(int i=1;i<=n;i++){
h[i]=inf-h[i];
}
solve();
for(int i=0;i<q;i++){
cout<<max(-1,ans[i])<<'\n';
}
return 0;
}
//maybe its multiset not set
Compilation message
antennas.cpp: In function 'void setIO(std::string)':
antennas.cpp:12:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
12 | freopen((s + ".in").c_str(), "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
13 | freopen((s + ".out").c_str(), "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
28400 KB |
Output is correct |
2 |
Correct |
7 ms |
28400 KB |
Output is correct |
3 |
Correct |
7 ms |
28248 KB |
Output is correct |
4 |
Correct |
7 ms |
28400 KB |
Output is correct |
5 |
Correct |
7 ms |
28252 KB |
Output is correct |
6 |
Correct |
7 ms |
28440 KB |
Output is correct |
7 |
Correct |
7 ms |
28252 KB |
Output is correct |
8 |
Correct |
7 ms |
28252 KB |
Output is correct |
9 |
Correct |
7 ms |
28264 KB |
Output is correct |
10 |
Correct |
7 ms |
28252 KB |
Output is correct |
11 |
Correct |
7 ms |
28252 KB |
Output is correct |
12 |
Correct |
7 ms |
28400 KB |
Output is correct |
13 |
Correct |
7 ms |
28252 KB |
Output is correct |
14 |
Correct |
7 ms |
28252 KB |
Output is correct |
15 |
Correct |
7 ms |
28440 KB |
Output is correct |
16 |
Correct |
7 ms |
28400 KB |
Output is correct |
17 |
Correct |
7 ms |
28252 KB |
Output is correct |
18 |
Correct |
7 ms |
28252 KB |
Output is correct |
19 |
Correct |
7 ms |
28336 KB |
Output is correct |
20 |
Correct |
7 ms |
28252 KB |
Output is correct |
21 |
Correct |
7 ms |
28480 KB |
Output is correct |
22 |
Correct |
7 ms |
28252 KB |
Output is correct |
23 |
Correct |
7 ms |
28252 KB |
Output is correct |
24 |
Correct |
7 ms |
28416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
28400 KB |
Output is correct |
2 |
Correct |
7 ms |
28400 KB |
Output is correct |
3 |
Correct |
7 ms |
28248 KB |
Output is correct |
4 |
Correct |
7 ms |
28400 KB |
Output is correct |
5 |
Correct |
7 ms |
28252 KB |
Output is correct |
6 |
Correct |
7 ms |
28440 KB |
Output is correct |
7 |
Correct |
7 ms |
28252 KB |
Output is correct |
8 |
Correct |
7 ms |
28252 KB |
Output is correct |
9 |
Correct |
7 ms |
28264 KB |
Output is correct |
10 |
Correct |
7 ms |
28252 KB |
Output is correct |
11 |
Correct |
7 ms |
28252 KB |
Output is correct |
12 |
Correct |
7 ms |
28400 KB |
Output is correct |
13 |
Correct |
7 ms |
28252 KB |
Output is correct |
14 |
Correct |
7 ms |
28252 KB |
Output is correct |
15 |
Correct |
7 ms |
28440 KB |
Output is correct |
16 |
Correct |
7 ms |
28400 KB |
Output is correct |
17 |
Correct |
7 ms |
28252 KB |
Output is correct |
18 |
Correct |
7 ms |
28252 KB |
Output is correct |
19 |
Correct |
7 ms |
28336 KB |
Output is correct |
20 |
Correct |
7 ms |
28252 KB |
Output is correct |
21 |
Correct |
7 ms |
28480 KB |
Output is correct |
22 |
Correct |
7 ms |
28252 KB |
Output is correct |
23 |
Correct |
7 ms |
28252 KB |
Output is correct |
24 |
Correct |
7 ms |
28416 KB |
Output is correct |
25 |
Correct |
81 ms |
31828 KB |
Output is correct |
26 |
Correct |
16 ms |
28920 KB |
Output is correct |
27 |
Correct |
124 ms |
33404 KB |
Output is correct |
28 |
Correct |
118 ms |
33364 KB |
Output is correct |
29 |
Correct |
92 ms |
31764 KB |
Output is correct |
30 |
Correct |
81 ms |
31824 KB |
Output is correct |
31 |
Correct |
90 ms |
32588 KB |
Output is correct |
32 |
Correct |
126 ms |
33284 KB |
Output is correct |
33 |
Correct |
114 ms |
33016 KB |
Output is correct |
34 |
Correct |
62 ms |
30820 KB |
Output is correct |
35 |
Correct |
114 ms |
33184 KB |
Output is correct |
36 |
Correct |
119 ms |
33364 KB |
Output is correct |
37 |
Correct |
70 ms |
30804 KB |
Output is correct |
38 |
Correct |
122 ms |
32592 KB |
Output is correct |
39 |
Correct |
23 ms |
29016 KB |
Output is correct |
40 |
Correct |
121 ms |
32504 KB |
Output is correct |
41 |
Correct |
89 ms |
31216 KB |
Output is correct |
42 |
Correct |
124 ms |
32500 KB |
Output is correct |
43 |
Correct |
44 ms |
29780 KB |
Output is correct |
44 |
Correct |
117 ms |
32508 KB |
Output is correct |
45 |
Correct |
27 ms |
29296 KB |
Output is correct |
46 |
Correct |
120 ms |
32340 KB |
Output is correct |
47 |
Correct |
36 ms |
29548 KB |
Output is correct |
48 |
Correct |
117 ms |
32516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
187 ms |
35788 KB |
Output is correct |
2 |
Correct |
236 ms |
36680 KB |
Output is correct |
3 |
Correct |
142 ms |
34072 KB |
Output is correct |
4 |
Correct |
215 ms |
36560 KB |
Output is correct |
5 |
Correct |
100 ms |
32140 KB |
Output is correct |
6 |
Correct |
207 ms |
36568 KB |
Output is correct |
7 |
Correct |
181 ms |
35540 KB |
Output is correct |
8 |
Correct |
220 ms |
36692 KB |
Output is correct |
9 |
Correct |
32 ms |
29532 KB |
Output is correct |
10 |
Correct |
222 ms |
36704 KB |
Output is correct |
11 |
Correct |
144 ms |
33428 KB |
Output is correct |
12 |
Correct |
208 ms |
36556 KB |
Output is correct |
13 |
Correct |
178 ms |
34072 KB |
Output is correct |
14 |
Correct |
160 ms |
34256 KB |
Output is correct |
15 |
Correct |
161 ms |
34256 KB |
Output is correct |
16 |
Correct |
136 ms |
34524 KB |
Output is correct |
17 |
Correct |
192 ms |
34208 KB |
Output is correct |
18 |
Correct |
164 ms |
34644 KB |
Output is correct |
19 |
Correct |
164 ms |
33868 KB |
Output is correct |
20 |
Correct |
166 ms |
34156 KB |
Output is correct |
21 |
Correct |
154 ms |
33880 KB |
Output is correct |
22 |
Correct |
171 ms |
34252 KB |
Output is correct |
23 |
Correct |
164 ms |
33880 KB |
Output is correct |
24 |
Correct |
137 ms |
34104 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
28400 KB |
Output is correct |
2 |
Correct |
7 ms |
28400 KB |
Output is correct |
3 |
Correct |
7 ms |
28248 KB |
Output is correct |
4 |
Correct |
7 ms |
28400 KB |
Output is correct |
5 |
Correct |
7 ms |
28252 KB |
Output is correct |
6 |
Correct |
7 ms |
28440 KB |
Output is correct |
7 |
Correct |
7 ms |
28252 KB |
Output is correct |
8 |
Correct |
7 ms |
28252 KB |
Output is correct |
9 |
Correct |
7 ms |
28264 KB |
Output is correct |
10 |
Correct |
7 ms |
28252 KB |
Output is correct |
11 |
Correct |
7 ms |
28252 KB |
Output is correct |
12 |
Correct |
7 ms |
28400 KB |
Output is correct |
13 |
Correct |
7 ms |
28252 KB |
Output is correct |
14 |
Correct |
7 ms |
28252 KB |
Output is correct |
15 |
Correct |
7 ms |
28440 KB |
Output is correct |
16 |
Correct |
7 ms |
28400 KB |
Output is correct |
17 |
Correct |
7 ms |
28252 KB |
Output is correct |
18 |
Correct |
7 ms |
28252 KB |
Output is correct |
19 |
Correct |
7 ms |
28336 KB |
Output is correct |
20 |
Correct |
7 ms |
28252 KB |
Output is correct |
21 |
Correct |
7 ms |
28480 KB |
Output is correct |
22 |
Correct |
7 ms |
28252 KB |
Output is correct |
23 |
Correct |
7 ms |
28252 KB |
Output is correct |
24 |
Correct |
7 ms |
28416 KB |
Output is correct |
25 |
Correct |
81 ms |
31828 KB |
Output is correct |
26 |
Correct |
16 ms |
28920 KB |
Output is correct |
27 |
Correct |
124 ms |
33404 KB |
Output is correct |
28 |
Correct |
118 ms |
33364 KB |
Output is correct |
29 |
Correct |
92 ms |
31764 KB |
Output is correct |
30 |
Correct |
81 ms |
31824 KB |
Output is correct |
31 |
Correct |
90 ms |
32588 KB |
Output is correct |
32 |
Correct |
126 ms |
33284 KB |
Output is correct |
33 |
Correct |
114 ms |
33016 KB |
Output is correct |
34 |
Correct |
62 ms |
30820 KB |
Output is correct |
35 |
Correct |
114 ms |
33184 KB |
Output is correct |
36 |
Correct |
119 ms |
33364 KB |
Output is correct |
37 |
Correct |
70 ms |
30804 KB |
Output is correct |
38 |
Correct |
122 ms |
32592 KB |
Output is correct |
39 |
Correct |
23 ms |
29016 KB |
Output is correct |
40 |
Correct |
121 ms |
32504 KB |
Output is correct |
41 |
Correct |
89 ms |
31216 KB |
Output is correct |
42 |
Correct |
124 ms |
32500 KB |
Output is correct |
43 |
Correct |
44 ms |
29780 KB |
Output is correct |
44 |
Correct |
117 ms |
32508 KB |
Output is correct |
45 |
Correct |
27 ms |
29296 KB |
Output is correct |
46 |
Correct |
120 ms |
32340 KB |
Output is correct |
47 |
Correct |
36 ms |
29548 KB |
Output is correct |
48 |
Correct |
117 ms |
32516 KB |
Output is correct |
49 |
Correct |
187 ms |
35788 KB |
Output is correct |
50 |
Correct |
236 ms |
36680 KB |
Output is correct |
51 |
Correct |
142 ms |
34072 KB |
Output is correct |
52 |
Correct |
215 ms |
36560 KB |
Output is correct |
53 |
Correct |
100 ms |
32140 KB |
Output is correct |
54 |
Correct |
207 ms |
36568 KB |
Output is correct |
55 |
Correct |
181 ms |
35540 KB |
Output is correct |
56 |
Correct |
220 ms |
36692 KB |
Output is correct |
57 |
Correct |
32 ms |
29532 KB |
Output is correct |
58 |
Correct |
222 ms |
36704 KB |
Output is correct |
59 |
Correct |
144 ms |
33428 KB |
Output is correct |
60 |
Correct |
208 ms |
36556 KB |
Output is correct |
61 |
Correct |
178 ms |
34072 KB |
Output is correct |
62 |
Correct |
160 ms |
34256 KB |
Output is correct |
63 |
Correct |
161 ms |
34256 KB |
Output is correct |
64 |
Correct |
136 ms |
34524 KB |
Output is correct |
65 |
Correct |
192 ms |
34208 KB |
Output is correct |
66 |
Correct |
164 ms |
34644 KB |
Output is correct |
67 |
Correct |
164 ms |
33868 KB |
Output is correct |
68 |
Correct |
166 ms |
34156 KB |
Output is correct |
69 |
Correct |
154 ms |
33880 KB |
Output is correct |
70 |
Correct |
171 ms |
34252 KB |
Output is correct |
71 |
Correct |
164 ms |
33880 KB |
Output is correct |
72 |
Correct |
137 ms |
34104 KB |
Output is correct |
73 |
Correct |
381 ms |
41872 KB |
Output is correct |
74 |
Correct |
238 ms |
37396 KB |
Output is correct |
75 |
Correct |
364 ms |
41464 KB |
Output is correct |
76 |
Correct |
485 ms |
44536 KB |
Output is correct |
77 |
Correct |
236 ms |
37204 KB |
Output is correct |
78 |
Correct |
392 ms |
42416 KB |
Output is correct |
79 |
Correct |
461 ms |
43188 KB |
Output is correct |
80 |
Correct |
499 ms |
44660 KB |
Output is correct |
81 |
Correct |
196 ms |
35380 KB |
Output is correct |
82 |
Correct |
361 ms |
40944 KB |
Output is correct |
83 |
Correct |
328 ms |
40624 KB |
Output is correct |
84 |
Correct |
429 ms |
44632 KB |
Output is correct |
85 |
Correct |
339 ms |
38432 KB |
Output is correct |
86 |
Correct |
383 ms |
41044 KB |
Output is correct |
87 |
Correct |
201 ms |
35536 KB |
Output is correct |
88 |
Correct |
345 ms |
41268 KB |
Output is correct |
89 |
Correct |
353 ms |
39748 KB |
Output is correct |
90 |
Correct |
366 ms |
41492 KB |
Output is correct |
91 |
Correct |
252 ms |
36684 KB |
Output is correct |
92 |
Correct |
367 ms |
40732 KB |
Output is correct |
93 |
Correct |
192 ms |
35376 KB |
Output is correct |
94 |
Correct |
381 ms |
41028 KB |
Output is correct |
95 |
Correct |
238 ms |
36300 KB |
Output is correct |
96 |
Correct |
376 ms |
40944 KB |
Output is correct |