#include<bits/stdc++.h>
#define fr first
#define sc second
using namespace std;
typedef long long ll;
typedef long double ld;
template<class T>void umax(T &a,T b){if(a<b)a=b;}
template<class T>void umin(T &a,T b){if(b<a)a=b;}
#ifdef juggernaut
#define printl(args...) printf(args)
#else
#define printl(args...) 0
#endif
int h[200005];
int a[200005];
int b[200005];
int tree[800005];
const int inf=1e9;
int ans=-1;
void chmax(int v,int l,int r,int ql,int qr,int val){
if(ql<=l&&r<=qr){
umax(tree[v],val);
return;
}
if(qr<l||r<ql)return;
int mid=(l+r)>>1;
chmax(v<<1,l,mid,ql,qr,val);
chmax(v<<1|1,mid+1,r,ql,qr,val);
}
void upd(int v,int l,int r,int pos,int val=-inf){
umax(val,tree[v]);
if(l==r){
umax(ans,val-h[pos]);
return;
}
int mid=(l+r)>>1;
if(pos<=mid)upd(v<<1,l,mid,pos,val);
else upd(v<<1|1,mid+1,r,pos,val);
}
void st(int v,int l,int r,int pos){
if(l==r){
tree[v]=-inf;
return;
}else{
umax(tree[v<<1],tree[v]);
umax(tree[v<<1|1],tree[v]);
}
tree[v]=-inf;
int mid=(l+r)>>1;
if(pos<=mid)st(v<<1,l,mid,pos);
else st(v<<1|1,mid+1,r,pos);
}
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d%d%d",&h[i],&a[i],&b[i]);
if(n<=2000){
vector<vector<pair<int,int>>>query(n+1);
int q;
scanf("%d",&q);
vector<int>ans(q,0),arr(n+1,-1);
for(int i=0;i<q;i++){
int l,r;
scanf("%d%d",&l,&r);
query[l].emplace_back(r,i);
}
for(int i=n;i>0;i--){
for(int j=i+1;j<=n;j++){
if(max(a[i],a[j])<=j-i&&j-i<=min(b[i],b[j])){
umax(arr[j],abs(h[i]-h[j]));
}
umax(arr[j],arr[j-1]);
}
for(auto q:query[i])ans[q.sc]=arr[q.fr];
}
for(int i=0;i<q;i++)printf("%d\n",ans[i]);
}else{
{
vector<vector<int>>inc(n+1),exc(n+1);
for(int i=1;i<=n;i++){
if(i>a[i]){
exc[max(1,i-b[i])].push_back(i);
inc[i-a[i]].push_back(i);
}
}
for(int i=n;i;i--){
for(int idx:inc[i])st(1,1,n,idx);
if(i+a[i]<=n){
chmax(1,1,n,i+a[i],min(i+b[i],n),h[i]);
}
for(int idx:exc[i])upd(1,1,n,idx);
}
}
reverse(h+1,h+1+n);
reverse(a+1,a+1+n);
reverse(b+1,b+1+n);
memset(tree,0,sizeof tree);
{
vector<vector<int>>inc(n+1),exc(n+1);
for(int i=1;i<=n;i++){
if(i>a[i]){
exc[max(1,i-b[i])].push_back(i);
inc[i-a[i]].push_back(i);
}
}
for(int i=n;i;i--){
for(int idx:inc[i])st(1,1,n,idx);
if(i+a[i]<=n){
chmax(1,1,n,i+a[i],min(i+b[i],n),h[i]);
}
for(int idx:exc[i])upd(1,1,n,idx);
}
}
cout<<ans;
}
}
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:56:28: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | for(int i=1;i<=n;i++)scanf("%d%d%d",&h[i],&a[i],&b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
60 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
antennas.cpp:64:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
64 | scanf("%d%d",&l,&r);
| ~~~~~^~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
452 KB |
Output is correct |
6 |
Correct |
1 ms |
316 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
312 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
308 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
312 KB |
Output is correct |
22 |
Correct |
1 ms |
312 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
452 KB |
Output is correct |
6 |
Correct |
1 ms |
316 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
312 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
308 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
312 KB |
Output is correct |
22 |
Correct |
1 ms |
312 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
41 ms |
5224 KB |
Output is correct |
26 |
Correct |
10 ms |
980 KB |
Output is correct |
27 |
Correct |
57 ms |
7176 KB |
Output is correct |
28 |
Correct |
60 ms |
6976 KB |
Output is correct |
29 |
Correct |
49 ms |
5464 KB |
Output is correct |
30 |
Correct |
54 ms |
5112 KB |
Output is correct |
31 |
Correct |
49 ms |
6388 KB |
Output is correct |
32 |
Correct |
60 ms |
6988 KB |
Output is correct |
33 |
Correct |
54 ms |
6980 KB |
Output is correct |
34 |
Correct |
33 ms |
3724 KB |
Output is correct |
35 |
Correct |
55 ms |
7628 KB |
Output is correct |
36 |
Correct |
60 ms |
6980 KB |
Output is correct |
37 |
Correct |
34 ms |
3788 KB |
Output is correct |
38 |
Correct |
61 ms |
5944 KB |
Output is correct |
39 |
Correct |
15 ms |
1184 KB |
Output is correct |
40 |
Correct |
55 ms |
6032 KB |
Output is correct |
41 |
Correct |
50 ms |
4968 KB |
Output is correct |
42 |
Correct |
61 ms |
6016 KB |
Output is correct |
43 |
Correct |
22 ms |
2388 KB |
Output is correct |
44 |
Correct |
59 ms |
5976 KB |
Output is correct |
45 |
Correct |
17 ms |
1372 KB |
Output is correct |
46 |
Correct |
56 ms |
5952 KB |
Output is correct |
47 |
Correct |
18 ms |
1876 KB |
Output is correct |
48 |
Correct |
68 ms |
6020 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
210 ms |
17444 KB |
Output is correct |
2 |
Correct |
239 ms |
18900 KB |
Output is correct |
3 |
Correct |
179 ms |
14424 KB |
Output is correct |
4 |
Correct |
264 ms |
19076 KB |
Output is correct |
5 |
Correct |
95 ms |
10600 KB |
Output is correct |
6 |
Correct |
246 ms |
18972 KB |
Output is correct |
7 |
Correct |
219 ms |
16972 KB |
Output is correct |
8 |
Correct |
241 ms |
18876 KB |
Output is correct |
9 |
Correct |
36 ms |
5808 KB |
Output is correct |
10 |
Correct |
266 ms |
18956 KB |
Output is correct |
11 |
Correct |
143 ms |
13124 KB |
Output is correct |
12 |
Correct |
245 ms |
18900 KB |
Output is correct |
13 |
Correct |
125 ms |
17732 KB |
Output is correct |
14 |
Correct |
123 ms |
17320 KB |
Output is correct |
15 |
Correct |
118 ms |
16472 KB |
Output is correct |
16 |
Correct |
116 ms |
16924 KB |
Output is correct |
17 |
Correct |
143 ms |
17820 KB |
Output is correct |
18 |
Correct |
149 ms |
17056 KB |
Output is correct |
19 |
Correct |
139 ms |
17024 KB |
Output is correct |
20 |
Correct |
137 ms |
17248 KB |
Output is correct |
21 |
Correct |
131 ms |
17668 KB |
Output is correct |
22 |
Correct |
128 ms |
17212 KB |
Output is correct |
23 |
Correct |
133 ms |
17308 KB |
Output is correct |
24 |
Correct |
115 ms |
16716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
340 KB |
Output is correct |
5 |
Correct |
1 ms |
452 KB |
Output is correct |
6 |
Correct |
1 ms |
316 KB |
Output is correct |
7 |
Correct |
1 ms |
308 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
312 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
340 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
308 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
312 KB |
Output is correct |
22 |
Correct |
1 ms |
312 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
41 ms |
5224 KB |
Output is correct |
26 |
Correct |
10 ms |
980 KB |
Output is correct |
27 |
Correct |
57 ms |
7176 KB |
Output is correct |
28 |
Correct |
60 ms |
6976 KB |
Output is correct |
29 |
Correct |
49 ms |
5464 KB |
Output is correct |
30 |
Correct |
54 ms |
5112 KB |
Output is correct |
31 |
Correct |
49 ms |
6388 KB |
Output is correct |
32 |
Correct |
60 ms |
6988 KB |
Output is correct |
33 |
Correct |
54 ms |
6980 KB |
Output is correct |
34 |
Correct |
33 ms |
3724 KB |
Output is correct |
35 |
Correct |
55 ms |
7628 KB |
Output is correct |
36 |
Correct |
60 ms |
6980 KB |
Output is correct |
37 |
Correct |
34 ms |
3788 KB |
Output is correct |
38 |
Correct |
61 ms |
5944 KB |
Output is correct |
39 |
Correct |
15 ms |
1184 KB |
Output is correct |
40 |
Correct |
55 ms |
6032 KB |
Output is correct |
41 |
Correct |
50 ms |
4968 KB |
Output is correct |
42 |
Correct |
61 ms |
6016 KB |
Output is correct |
43 |
Correct |
22 ms |
2388 KB |
Output is correct |
44 |
Correct |
59 ms |
5976 KB |
Output is correct |
45 |
Correct |
17 ms |
1372 KB |
Output is correct |
46 |
Correct |
56 ms |
5952 KB |
Output is correct |
47 |
Correct |
18 ms |
1876 KB |
Output is correct |
48 |
Correct |
68 ms |
6020 KB |
Output is correct |
49 |
Correct |
210 ms |
17444 KB |
Output is correct |
50 |
Correct |
239 ms |
18900 KB |
Output is correct |
51 |
Correct |
179 ms |
14424 KB |
Output is correct |
52 |
Correct |
264 ms |
19076 KB |
Output is correct |
53 |
Correct |
95 ms |
10600 KB |
Output is correct |
54 |
Correct |
246 ms |
18972 KB |
Output is correct |
55 |
Correct |
219 ms |
16972 KB |
Output is correct |
56 |
Correct |
241 ms |
18876 KB |
Output is correct |
57 |
Correct |
36 ms |
5808 KB |
Output is correct |
58 |
Correct |
266 ms |
18956 KB |
Output is correct |
59 |
Correct |
143 ms |
13124 KB |
Output is correct |
60 |
Correct |
245 ms |
18900 KB |
Output is correct |
61 |
Correct |
125 ms |
17732 KB |
Output is correct |
62 |
Correct |
123 ms |
17320 KB |
Output is correct |
63 |
Correct |
118 ms |
16472 KB |
Output is correct |
64 |
Correct |
116 ms |
16924 KB |
Output is correct |
65 |
Correct |
143 ms |
17820 KB |
Output is correct |
66 |
Correct |
149 ms |
17056 KB |
Output is correct |
67 |
Correct |
139 ms |
17024 KB |
Output is correct |
68 |
Correct |
137 ms |
17248 KB |
Output is correct |
69 |
Correct |
131 ms |
17668 KB |
Output is correct |
70 |
Correct |
128 ms |
17212 KB |
Output is correct |
71 |
Correct |
133 ms |
17308 KB |
Output is correct |
72 |
Correct |
115 ms |
16716 KB |
Output is correct |
73 |
Incorrect |
223 ms |
21656 KB |
Output isn't correct |
74 |
Halted |
0 ms |
0 KB |
- |