#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt,sse4")
#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>
#define int ll
const int mxn = 2e5+10;
const ll inf = 2e9+10;
#define ls now*2+1
#define rs now*2+2
#define mid ((l+r)>>1)
struct SEG1{
struct node{
int mn,mx,val;
node(){
mn = inf,mx = -inf,val = -1;
}
};
node seg[mxn*4];
SEG1(){}
node pull(node a,node b){
node re;
re.mn = min(a.mn,b.mn);
re.mx = -inf;
re.val = max(a.val,b.val);
return re;
}
void push(int now,int l,int r){
seg[ls].mx = max(seg[ls].mx,seg[now].mx);
seg[rs].mx = max(seg[rs].mx,seg[now].mx);
seg[ls].val = max(seg[ls].val,seg[ls].mx-seg[ls].mn);
seg[rs].val = max(seg[rs].val,seg[rs].mx-seg[rs].mn);
seg[now].mx = -inf;
return;
}
void chmax(int now,int l,int r,int s,int e,int v){
if(l>=s&&e>=r){
seg[now].mx = max(seg[now].mx,v);
seg[now].val = max(seg[now].val,seg[now].mx-seg[now].mn);
return;
}
push(now,l,r);
if(mid>=s)chmax(ls,l,mid,s,e,v);
if(mid<e)chmax(rs,mid+1,r,s,e,v);
seg[now].mn = min(seg[ls].mn,seg[rs].mn);
seg[now].val = max(seg[ls].val,seg[rs].val);
return;
}
void chmin(int now,int l,int r,int p,int v){
if(l == r){
seg[now].mn = v;seg[now].mx = -inf;
seg[now].val = seg[now].mx-seg[now].mn;
return;
}
push(now,l,r);
if(mid>=p)chmin(ls,l,mid,p,v);
else chmin(rs,mid+1,r,p,v);
seg[now] = pull(seg[ls],seg[rs]);
return;
}
node getval(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now];
push(now,l,r);
if(mid>=e)return getval(ls,l,mid,s,e);
else if(mid<s)return getval(rs,mid+1,r,s,e);
else return pull(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
}
void init(){
for(auto &i:seg)i.mn = inf,i.mx = -inf,i.val = -1;
return;
}
};
struct SEG2{
int seg[mxn*4];
SEG2(){
for(auto &i:seg)i = -1;
}
void modify(int now,int l,int r,int p,int v){
if(l == r){
seg[now] = max(seg[now],v);
return;
}
if(mid>=p)modify(ls,l,mid,p,v);
else modify(rs,mid+1,r,p,v);
seg[now] = max(seg[ls],seg[rs]);
return;
}
int getval(int now,int l,int r,int s,int e){
if(l>=s&&e>=r)return seg[now];
if(mid>=e)return getval(ls,l,mid,s,e);
else if(mid<s)return getval(rs,mid+1,r,s,e);
else return max(getval(ls,l,mid,s,e),getval(rs,mid+1,r,s,e));
}
void init(){
for(auto &i:seg)i = -1;
return;
}
};
#undef ls
#undef rs
#undef mid
struct D{
int tp,id,pos;
D(){}
D(int tt,int ii,int pp):tp(tt),id(ii),pos(pp){}
bool operator<(D b)const{
return pos == b.pos?tp<b.tp:pos<b.pos;
}
};
SEG1 seg1;
SEG2 seg2;
pii req[mxn];
pii range[mxn];
int H[mxn];
int N,Q;
vector<D> op;
int ans[mxn];
void solve(){
op.clear();
seg1.init();
seg2.init();
for(int i = 1;i<=N;i++){
int pl = i+range[i].fs,pr = i+range[i].sc+1;
pl = min(pl,N),pr = min(pr,N+1);
op.push_back(D(1,i,pr));
op.push_back(D(2,i,pl));
op.push_back(D(3,i,i));
}
for(int i = 1;i<=Q;i++){
op.push_back(D(4,i,req[i].sc));
}
sort(op.begin(),op.end());
for(auto &[tp,id,___]:op){
//cout<<tp<<':'<<id<<' '<<___<<"::"<<seg1.seg[0].val<<endl;
if(tp == 1){
seg2.modify(0,0,N,id,seg1.getval(0,0,N,id,id).val);
seg1.chmin(0,0,N,id,inf);
}
else if(tp == 2){
seg1.chmin(0,0,N,id,H[id]);
}
else if(tp == 3){
int pl = id-range[id].sc,pr = id-range[id].fs;
pl = max(pl,0ll),pr = max(pr,0ll);
seg1.chmax(0,0,N,pl,pr,H[id]);
}
else{
ans[id] = max({ans[id],seg1.getval(0,0,N,req[id].fs,req[id].sc).val,seg2.getval(0,0,N,req[id].fs,req[id].sc)});
}
}
//cout<<endl;
return;
}
namespace SMALL{
vector<pii> v[mxn];
bool peko(int a,int b){
pii r1 = pii(a+range[a].fs,a+range[a].sc);
pii r2 = pii(b-range[b].sc,b-range[b].fs);
if(r1.fs<=b&&b<=r1.sc&&r2.fs<=a&&a<=r2.sc)return true;
return false;
}
void GO(){
for(int i = 1;i<=N;i++){
for(int j = i+1;j<=N;j++){
if(peko(i,j))v[j].push_back(pii(0,i));
}
}
for(int i = 1;i<=Q;i++){
v[req[i].sc].push_back(pii(1,i));
}
memset(ans,-1,sizeof(ans));
seg2.init();
for(int i = 1;i<=N;i++){
for(auto &j:v[i]){
if(j.fs == 0){
seg2.modify(0,0,N,j.sc,abs(H[j.sc]-H[i]));
}
else{
ans[j.sc] = seg2.getval(0,0,N,req[j.sc].fs,req[j.sc].sc);
}
}
}
for(int i = 1;i<=Q;i++)cout<<ans[i]<<'\n';
return;
}
}
main(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
cin>>N;
for(int i = 1;i<=N;i++){
cin>>H[i]>>range[i].fs>>range[i].sc;
}
cin>>Q;
for(int i = 1;i<=Q;i++){
cin>>req[i].fs>>req[i].sc;
}
if(N<=2000){
SMALL::GO();
return 0;
}
memset(ans,-1,sizeof(ans));
solve();
reverse(H+1,H+N+1);
reverse(range+1,range+N+1);
for(int i = 1;i<=Q;i++){
req[i].fs = N+1-req[i].fs,req[i].sc = N+1-req[i].sc;
swap(req[i].fs,req[i].sc);
}
solve();
for(int i = 1;i<=Q;i++){
cout<<ans[i]<<'\n';
}
return 0;
}
Compilation message
antennas.cpp:203:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
203 | main(){
| ^~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
37464 KB |
Output is correct |
2 |
Correct |
7 ms |
37468 KB |
Output is correct |
3 |
Correct |
7 ms |
37468 KB |
Output is correct |
4 |
Correct |
7 ms |
37468 KB |
Output is correct |
5 |
Correct |
7 ms |
37468 KB |
Output is correct |
6 |
Correct |
7 ms |
37468 KB |
Output is correct |
7 |
Correct |
7 ms |
37540 KB |
Output is correct |
8 |
Correct |
7 ms |
37468 KB |
Output is correct |
9 |
Correct |
7 ms |
37576 KB |
Output is correct |
10 |
Correct |
8 ms |
37468 KB |
Output is correct |
11 |
Correct |
7 ms |
37468 KB |
Output is correct |
12 |
Correct |
8 ms |
37580 KB |
Output is correct |
13 |
Correct |
6 ms |
37572 KB |
Output is correct |
14 |
Correct |
6 ms |
37468 KB |
Output is correct |
15 |
Correct |
7 ms |
37464 KB |
Output is correct |
16 |
Correct |
7 ms |
37468 KB |
Output is correct |
17 |
Correct |
7 ms |
37464 KB |
Output is correct |
18 |
Correct |
7 ms |
37468 KB |
Output is correct |
19 |
Correct |
6 ms |
37468 KB |
Output is correct |
20 |
Correct |
7 ms |
37464 KB |
Output is correct |
21 |
Correct |
7 ms |
37468 KB |
Output is correct |
22 |
Correct |
8 ms |
37464 KB |
Output is correct |
23 |
Correct |
8 ms |
37468 KB |
Output is correct |
24 |
Correct |
7 ms |
37472 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
37464 KB |
Output is correct |
2 |
Correct |
7 ms |
37468 KB |
Output is correct |
3 |
Correct |
7 ms |
37468 KB |
Output is correct |
4 |
Correct |
7 ms |
37468 KB |
Output is correct |
5 |
Correct |
7 ms |
37468 KB |
Output is correct |
6 |
Correct |
7 ms |
37468 KB |
Output is correct |
7 |
Correct |
7 ms |
37540 KB |
Output is correct |
8 |
Correct |
7 ms |
37468 KB |
Output is correct |
9 |
Correct |
7 ms |
37576 KB |
Output is correct |
10 |
Correct |
8 ms |
37468 KB |
Output is correct |
11 |
Correct |
7 ms |
37468 KB |
Output is correct |
12 |
Correct |
8 ms |
37580 KB |
Output is correct |
13 |
Correct |
6 ms |
37572 KB |
Output is correct |
14 |
Correct |
6 ms |
37468 KB |
Output is correct |
15 |
Correct |
7 ms |
37464 KB |
Output is correct |
16 |
Correct |
7 ms |
37468 KB |
Output is correct |
17 |
Correct |
7 ms |
37464 KB |
Output is correct |
18 |
Correct |
7 ms |
37468 KB |
Output is correct |
19 |
Correct |
6 ms |
37468 KB |
Output is correct |
20 |
Correct |
7 ms |
37464 KB |
Output is correct |
21 |
Correct |
7 ms |
37468 KB |
Output is correct |
22 |
Correct |
8 ms |
37464 KB |
Output is correct |
23 |
Correct |
8 ms |
37468 KB |
Output is correct |
24 |
Correct |
7 ms |
37472 KB |
Output is correct |
25 |
Correct |
50 ms |
43860 KB |
Output is correct |
26 |
Correct |
20 ms |
40788 KB |
Output is correct |
27 |
Correct |
72 ms |
47440 KB |
Output is correct |
28 |
Correct |
89 ms |
48472 KB |
Output is correct |
29 |
Correct |
47 ms |
44112 KB |
Output is correct |
30 |
Correct |
60 ms |
45700 KB |
Output is correct |
31 |
Correct |
55 ms |
44604 KB |
Output is correct |
32 |
Correct |
76 ms |
48464 KB |
Output is correct |
33 |
Correct |
69 ms |
46160 KB |
Output is correct |
34 |
Correct |
43 ms |
43860 KB |
Output is correct |
35 |
Correct |
75 ms |
47184 KB |
Output is correct |
36 |
Correct |
73 ms |
48464 KB |
Output is correct |
37 |
Correct |
41 ms |
41808 KB |
Output is correct |
38 |
Correct |
64 ms |
45080 KB |
Output is correct |
39 |
Correct |
18 ms |
38488 KB |
Output is correct |
40 |
Correct |
66 ms |
45072 KB |
Output is correct |
41 |
Correct |
50 ms |
42884 KB |
Output is correct |
42 |
Correct |
64 ms |
45064 KB |
Output is correct |
43 |
Correct |
34 ms |
40028 KB |
Output is correct |
44 |
Correct |
72 ms |
45160 KB |
Output is correct |
45 |
Correct |
19 ms |
38748 KB |
Output is correct |
46 |
Correct |
69 ms |
45144 KB |
Output is correct |
47 |
Correct |
31 ms |
39392 KB |
Output is correct |
48 |
Correct |
65 ms |
45060 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
446 ms |
65468 KB |
Output is correct |
2 |
Correct |
509 ms |
65472 KB |
Output is correct |
3 |
Correct |
329 ms |
53692 KB |
Output is correct |
4 |
Correct |
557 ms |
65532 KB |
Output is correct |
5 |
Correct |
229 ms |
52412 KB |
Output is correct |
6 |
Correct |
492 ms |
65544 KB |
Output is correct |
7 |
Correct |
419 ms |
52492 KB |
Output is correct |
8 |
Correct |
513 ms |
65556 KB |
Output is correct |
9 |
Correct |
75 ms |
41936 KB |
Output is correct |
10 |
Correct |
494 ms |
65544 KB |
Output is correct |
11 |
Correct |
284 ms |
53180 KB |
Output is correct |
12 |
Correct |
526 ms |
66324 KB |
Output is correct |
13 |
Correct |
392 ms |
66296 KB |
Output is correct |
14 |
Correct |
431 ms |
64188 KB |
Output is correct |
15 |
Correct |
397 ms |
65636 KB |
Output is correct |
16 |
Correct |
393 ms |
64444 KB |
Output is correct |
17 |
Correct |
414 ms |
66304 KB |
Output is correct |
18 |
Correct |
396 ms |
65056 KB |
Output is correct |
19 |
Correct |
390 ms |
66236 KB |
Output is correct |
20 |
Correct |
392 ms |
64264 KB |
Output is correct |
21 |
Correct |
394 ms |
65976 KB |
Output is correct |
22 |
Correct |
400 ms |
64772 KB |
Output is correct |
23 |
Correct |
423 ms |
65792 KB |
Output is correct |
24 |
Correct |
383 ms |
65720 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
37464 KB |
Output is correct |
2 |
Correct |
7 ms |
37468 KB |
Output is correct |
3 |
Correct |
7 ms |
37468 KB |
Output is correct |
4 |
Correct |
7 ms |
37468 KB |
Output is correct |
5 |
Correct |
7 ms |
37468 KB |
Output is correct |
6 |
Correct |
7 ms |
37468 KB |
Output is correct |
7 |
Correct |
7 ms |
37540 KB |
Output is correct |
8 |
Correct |
7 ms |
37468 KB |
Output is correct |
9 |
Correct |
7 ms |
37576 KB |
Output is correct |
10 |
Correct |
8 ms |
37468 KB |
Output is correct |
11 |
Correct |
7 ms |
37468 KB |
Output is correct |
12 |
Correct |
8 ms |
37580 KB |
Output is correct |
13 |
Correct |
6 ms |
37572 KB |
Output is correct |
14 |
Correct |
6 ms |
37468 KB |
Output is correct |
15 |
Correct |
7 ms |
37464 KB |
Output is correct |
16 |
Correct |
7 ms |
37468 KB |
Output is correct |
17 |
Correct |
7 ms |
37464 KB |
Output is correct |
18 |
Correct |
7 ms |
37468 KB |
Output is correct |
19 |
Correct |
6 ms |
37468 KB |
Output is correct |
20 |
Correct |
7 ms |
37464 KB |
Output is correct |
21 |
Correct |
7 ms |
37468 KB |
Output is correct |
22 |
Correct |
8 ms |
37464 KB |
Output is correct |
23 |
Correct |
8 ms |
37468 KB |
Output is correct |
24 |
Correct |
7 ms |
37472 KB |
Output is correct |
25 |
Correct |
50 ms |
43860 KB |
Output is correct |
26 |
Correct |
20 ms |
40788 KB |
Output is correct |
27 |
Correct |
72 ms |
47440 KB |
Output is correct |
28 |
Correct |
89 ms |
48472 KB |
Output is correct |
29 |
Correct |
47 ms |
44112 KB |
Output is correct |
30 |
Correct |
60 ms |
45700 KB |
Output is correct |
31 |
Correct |
55 ms |
44604 KB |
Output is correct |
32 |
Correct |
76 ms |
48464 KB |
Output is correct |
33 |
Correct |
69 ms |
46160 KB |
Output is correct |
34 |
Correct |
43 ms |
43860 KB |
Output is correct |
35 |
Correct |
75 ms |
47184 KB |
Output is correct |
36 |
Correct |
73 ms |
48464 KB |
Output is correct |
37 |
Correct |
41 ms |
41808 KB |
Output is correct |
38 |
Correct |
64 ms |
45080 KB |
Output is correct |
39 |
Correct |
18 ms |
38488 KB |
Output is correct |
40 |
Correct |
66 ms |
45072 KB |
Output is correct |
41 |
Correct |
50 ms |
42884 KB |
Output is correct |
42 |
Correct |
64 ms |
45064 KB |
Output is correct |
43 |
Correct |
34 ms |
40028 KB |
Output is correct |
44 |
Correct |
72 ms |
45160 KB |
Output is correct |
45 |
Correct |
19 ms |
38748 KB |
Output is correct |
46 |
Correct |
69 ms |
45144 KB |
Output is correct |
47 |
Correct |
31 ms |
39392 KB |
Output is correct |
48 |
Correct |
65 ms |
45060 KB |
Output is correct |
49 |
Correct |
446 ms |
65468 KB |
Output is correct |
50 |
Correct |
509 ms |
65472 KB |
Output is correct |
51 |
Correct |
329 ms |
53692 KB |
Output is correct |
52 |
Correct |
557 ms |
65532 KB |
Output is correct |
53 |
Correct |
229 ms |
52412 KB |
Output is correct |
54 |
Correct |
492 ms |
65544 KB |
Output is correct |
55 |
Correct |
419 ms |
52492 KB |
Output is correct |
56 |
Correct |
513 ms |
65556 KB |
Output is correct |
57 |
Correct |
75 ms |
41936 KB |
Output is correct |
58 |
Correct |
494 ms |
65544 KB |
Output is correct |
59 |
Correct |
284 ms |
53180 KB |
Output is correct |
60 |
Correct |
526 ms |
66324 KB |
Output is correct |
61 |
Correct |
392 ms |
66296 KB |
Output is correct |
62 |
Correct |
431 ms |
64188 KB |
Output is correct |
63 |
Correct |
397 ms |
65636 KB |
Output is correct |
64 |
Correct |
393 ms |
64444 KB |
Output is correct |
65 |
Correct |
414 ms |
66304 KB |
Output is correct |
66 |
Correct |
396 ms |
65056 KB |
Output is correct |
67 |
Correct |
390 ms |
66236 KB |
Output is correct |
68 |
Correct |
392 ms |
64264 KB |
Output is correct |
69 |
Correct |
394 ms |
65976 KB |
Output is correct |
70 |
Correct |
400 ms |
64772 KB |
Output is correct |
71 |
Correct |
423 ms |
65792 KB |
Output is correct |
72 |
Correct |
383 ms |
65720 KB |
Output is correct |
73 |
Correct |
741 ms |
70256 KB |
Output is correct |
74 |
Correct |
552 ms |
70332 KB |
Output is correct |
75 |
Correct |
632 ms |
71612 KB |
Output is correct |
76 |
Correct |
923 ms |
72128 KB |
Output is correct |
77 |
Correct |
417 ms |
56512 KB |
Output is correct |
78 |
Correct |
807 ms |
71040 KB |
Output is correct |
79 |
Correct |
778 ms |
72028 KB |
Output is correct |
80 |
Correct |
947 ms |
72948 KB |
Output is correct |
81 |
Correct |
362 ms |
54524 KB |
Output is correct |
82 |
Correct |
736 ms |
71436 KB |
Output is correct |
83 |
Correct |
685 ms |
69500 KB |
Output is correct |
84 |
Correct |
973 ms |
72952 KB |
Output is correct |
85 |
Correct |
613 ms |
70672 KB |
Output is correct |
86 |
Correct |
796 ms |
72944 KB |
Output is correct |
87 |
Correct |
481 ms |
69120 KB |
Output is correct |
88 |
Correct |
769 ms |
73148 KB |
Output is correct |
89 |
Correct |
724 ms |
71260 KB |
Output is correct |
90 |
Correct |
818 ms |
72892 KB |
Output is correct |
91 |
Correct |
527 ms |
69628 KB |
Output is correct |
92 |
Correct |
726 ms |
72888 KB |
Output is correct |
93 |
Correct |
475 ms |
68952 KB |
Output is correct |
94 |
Correct |
765 ms |
71352 KB |
Output is correct |
95 |
Correct |
534 ms |
71160 KB |
Output is correct |
96 |
Correct |
737 ms |
72456 KB |
Output is correct |