#include <bits/stdc++.h>
using namespace std;
using nagai = long long;
#define sz(x) int((x).size())
const int LG=18;
const int N=1<<LG;
const int oo=0x3f3f3f3f;
struct it{
int t[2*N],ans[2*N],mnh[2*N],psh[2*N];
void init(){
fill(t,t+2*N,0);
fill(psh,psh+2*N,0);
fill(ans,ans+2*N,-oo);
fill(mnh,mnh+2*N,oo);
}
it(){
init();
}
void app(int x,int y){
ans[x]=max(ans[x],y-mnh[x]);
t[x]=max(t[x],y);
psh[x]=max(psh[x],y);
}
void push1(int x){
app(2*x,psh[x]);
app(2*x+1,psh[x]);
psh[x]=0;
}
void push(int x){
for(int i=LG;i;--i)
push1(x>>i);
}
void upd(int x){
while(x>1){
t[x>>1]=max(t[x],t[x^1]);
ans[x>>1]=max(ans[x],ans[x^1]);
x>>=1;
}
}
void chh(int x,int y){
x+=N;
push(x);
ans[x]=max(ans[x],t[x]-y);
mnh[x]=y;
upd(x);
while(x>1)mnh[x>>1]=min(mnh[x],mnh[x^1]),x>>=1;
}
void chan(int l,int r,int v){
if(r<=l)return;
l+=N;
r+=N;
int l1=l,r1=r;
push(l);
push(r-1);
while(l<r){
if(l&1)
app(l++,v);
if(r&1)
app(--r,v);
l>>=1,r>>=1;
}
push(l1);
push(r1-1);
upd(l1);
upd(r1-1);
}
int get(int l,int r){
l+=N;
r+=N;
int ans=-1;
push(l);
push(r-1);
while(l<r){
if(l&1)ans=max(ans,this->ans[l++]);
if(r&1)ans=max(ans,this->ans[--r]);
l/=2,r/=2;
}
return ans;
}
} myit;
int n,q;
int a[N],b[N];
int h[N];
int ans[N];
pair<int,int>qs[N];
vector<pair<int,int>>mts[N];
vector<int>evs[N];
int stup(int l,int r){
int ans=-1;
for(int i=l;i<=r;++i)
for(int j=i+1;j<=r;++j)
if(a[i]<=j-i&&j-i<=b[i]&&a[j]<=j-i&&j-i<=b[j])
ans=max(ans,h[j]-h[i]);
return ans;
}
void solve(){
for(int i=0;i<n;++i)mts[i].clear();
for(int i=0;i<q;++i)mts[qs[i].second].emplace_back(qs[i].first,i);
myit.init();
for(int i=0;i<n;++i)evs[i].clear();
for(int i=0;i<n;++i){
evs[min(i+a[i],n)].push_back(i);
evs[min(i+b[i]+1,n)].push_back(i);
}
vector<bool>u(n);
for(int i=0;i<n;++i){
for(int x:evs[i]){
if(!u[x]){
myit.push(N+x);
myit.t[N+x]=0;
myit.upd(N+x);
myit.chh(x,h[x]),u[x]=1;
}
else
myit.chh(x,oo);
}
int l=max(0,i-b[i]);
int r=max(0,i-a[i]+1);
myit.chan(l,r,h[i]);
for(auto&[l,ind]:mts[i]){
int kek=myit.get(l,i+1);
// cerr<<kek<<' '<<stup(l,i)<<'\n';
// assert(kek==stup(l,i));
ans[ind]=max(ans[ind],kek);
}
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(int i=0;i<n;++i)cin>>h[i]>>a[i]>>b[i];
cin>>q;
fill(ans,ans+q,-1);
for(int i=0;i<q;++i){
int a,b;
cin>>a>>b;
--a;
--b;
qs[i]={a,b};
}
solve();
reverse(h,h+n);
reverse(a,a+n);
reverse(b,b+n);
for(int i=0;i<q;++i){
qs[i].second=n-qs[i].second-1;
qs[i].first=n-qs[i].first-1;
swap(qs[i].first,qs[i].second);
}
solve();
for(int i=0;i<q;++i)
cout<<ans[i]<<'\n';
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
20856 KB |
Output is correct |
2 |
Correct |
25 ms |
20984 KB |
Output is correct |
3 |
Correct |
29 ms |
20984 KB |
Output is correct |
4 |
Correct |
26 ms |
20988 KB |
Output is correct |
5 |
Correct |
26 ms |
20984 KB |
Output is correct |
6 |
Correct |
28 ms |
21064 KB |
Output is correct |
7 |
Correct |
25 ms |
20960 KB |
Output is correct |
8 |
Correct |
27 ms |
20984 KB |
Output is correct |
9 |
Correct |
24 ms |
20944 KB |
Output is correct |
10 |
Correct |
25 ms |
20984 KB |
Output is correct |
11 |
Correct |
24 ms |
20856 KB |
Output is correct |
12 |
Correct |
25 ms |
20860 KB |
Output is correct |
13 |
Correct |
24 ms |
20860 KB |
Output is correct |
14 |
Correct |
25 ms |
20860 KB |
Output is correct |
15 |
Correct |
25 ms |
20984 KB |
Output is correct |
16 |
Correct |
31 ms |
20856 KB |
Output is correct |
17 |
Correct |
30 ms |
20984 KB |
Output is correct |
18 |
Correct |
25 ms |
20956 KB |
Output is correct |
19 |
Correct |
30 ms |
20984 KB |
Output is correct |
20 |
Correct |
30 ms |
20984 KB |
Output is correct |
21 |
Correct |
28 ms |
20856 KB |
Output is correct |
22 |
Correct |
25 ms |
20856 KB |
Output is correct |
23 |
Correct |
25 ms |
20984 KB |
Output is correct |
24 |
Correct |
25 ms |
20984 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
20856 KB |
Output is correct |
2 |
Correct |
25 ms |
20984 KB |
Output is correct |
3 |
Correct |
29 ms |
20984 KB |
Output is correct |
4 |
Correct |
26 ms |
20988 KB |
Output is correct |
5 |
Correct |
26 ms |
20984 KB |
Output is correct |
6 |
Correct |
28 ms |
21064 KB |
Output is correct |
7 |
Correct |
25 ms |
20960 KB |
Output is correct |
8 |
Correct |
27 ms |
20984 KB |
Output is correct |
9 |
Correct |
24 ms |
20944 KB |
Output is correct |
10 |
Correct |
25 ms |
20984 KB |
Output is correct |
11 |
Correct |
24 ms |
20856 KB |
Output is correct |
12 |
Correct |
25 ms |
20860 KB |
Output is correct |
13 |
Correct |
24 ms |
20860 KB |
Output is correct |
14 |
Correct |
25 ms |
20860 KB |
Output is correct |
15 |
Correct |
25 ms |
20984 KB |
Output is correct |
16 |
Correct |
31 ms |
20856 KB |
Output is correct |
17 |
Correct |
30 ms |
20984 KB |
Output is correct |
18 |
Correct |
25 ms |
20956 KB |
Output is correct |
19 |
Correct |
30 ms |
20984 KB |
Output is correct |
20 |
Correct |
30 ms |
20984 KB |
Output is correct |
21 |
Correct |
28 ms |
20856 KB |
Output is correct |
22 |
Correct |
25 ms |
20856 KB |
Output is correct |
23 |
Correct |
25 ms |
20984 KB |
Output is correct |
24 |
Correct |
25 ms |
20984 KB |
Output is correct |
25 |
Correct |
264 ms |
27548 KB |
Output is correct |
26 |
Correct |
57 ms |
21880 KB |
Output is correct |
27 |
Correct |
331 ms |
30200 KB |
Output is correct |
28 |
Correct |
336 ms |
30076 KB |
Output is correct |
29 |
Correct |
259 ms |
27644 KB |
Output is correct |
30 |
Correct |
230 ms |
27356 KB |
Output is correct |
31 |
Correct |
399 ms |
29176 KB |
Output is correct |
32 |
Correct |
324 ms |
29996 KB |
Output is correct |
33 |
Correct |
313 ms |
29792 KB |
Output is correct |
34 |
Correct |
178 ms |
25336 KB |
Output is correct |
35 |
Correct |
317 ms |
30436 KB |
Output is correct |
36 |
Correct |
316 ms |
30116 KB |
Output is correct |
37 |
Correct |
191 ms |
25720 KB |
Output is correct |
38 |
Correct |
325 ms |
29160 KB |
Output is correct |
39 |
Correct |
68 ms |
22136 KB |
Output is correct |
40 |
Correct |
338 ms |
29080 KB |
Output is correct |
41 |
Correct |
239 ms |
27228 KB |
Output is correct |
42 |
Correct |
319 ms |
29048 KB |
Output is correct |
43 |
Correct |
123 ms |
23816 KB |
Output is correct |
44 |
Correct |
317 ms |
28956 KB |
Output is correct |
45 |
Correct |
85 ms |
22496 KB |
Output is correct |
46 |
Correct |
370 ms |
29048 KB |
Output is correct |
47 |
Correct |
100 ms |
23032 KB |
Output is correct |
48 |
Correct |
317 ms |
28992 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
576 ms |
28520 KB |
Output is correct |
2 |
Correct |
648 ms |
33916 KB |
Output is correct |
3 |
Correct |
436 ms |
30648 KB |
Output is correct |
4 |
Correct |
653 ms |
33804 KB |
Output is correct |
5 |
Correct |
282 ms |
26736 KB |
Output is correct |
6 |
Correct |
638 ms |
34036 KB |
Output is correct |
7 |
Correct |
542 ms |
32236 KB |
Output is correct |
8 |
Correct |
641 ms |
33824 KB |
Output is correct |
9 |
Correct |
105 ms |
23032 KB |
Output is correct |
10 |
Correct |
643 ms |
33996 KB |
Output is correct |
11 |
Correct |
389 ms |
29800 KB |
Output is correct |
12 |
Correct |
650 ms |
33792 KB |
Output is correct |
13 |
Correct |
552 ms |
32704 KB |
Output is correct |
14 |
Correct |
518 ms |
32120 KB |
Output is correct |
15 |
Correct |
446 ms |
32020 KB |
Output is correct |
16 |
Correct |
488 ms |
32012 KB |
Output is correct |
17 |
Correct |
554 ms |
33484 KB |
Output is correct |
18 |
Correct |
501 ms |
32208 KB |
Output is correct |
19 |
Correct |
474 ms |
32012 KB |
Output is correct |
20 |
Correct |
482 ms |
32452 KB |
Output is correct |
21 |
Correct |
528 ms |
32368 KB |
Output is correct |
22 |
Correct |
518 ms |
32160 KB |
Output is correct |
23 |
Correct |
494 ms |
32192 KB |
Output is correct |
24 |
Correct |
448 ms |
31596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
20856 KB |
Output is correct |
2 |
Correct |
25 ms |
20984 KB |
Output is correct |
3 |
Correct |
29 ms |
20984 KB |
Output is correct |
4 |
Correct |
26 ms |
20988 KB |
Output is correct |
5 |
Correct |
26 ms |
20984 KB |
Output is correct |
6 |
Correct |
28 ms |
21064 KB |
Output is correct |
7 |
Correct |
25 ms |
20960 KB |
Output is correct |
8 |
Correct |
27 ms |
20984 KB |
Output is correct |
9 |
Correct |
24 ms |
20944 KB |
Output is correct |
10 |
Correct |
25 ms |
20984 KB |
Output is correct |
11 |
Correct |
24 ms |
20856 KB |
Output is correct |
12 |
Correct |
25 ms |
20860 KB |
Output is correct |
13 |
Correct |
24 ms |
20860 KB |
Output is correct |
14 |
Correct |
25 ms |
20860 KB |
Output is correct |
15 |
Correct |
25 ms |
20984 KB |
Output is correct |
16 |
Correct |
31 ms |
20856 KB |
Output is correct |
17 |
Correct |
30 ms |
20984 KB |
Output is correct |
18 |
Correct |
25 ms |
20956 KB |
Output is correct |
19 |
Correct |
30 ms |
20984 KB |
Output is correct |
20 |
Correct |
30 ms |
20984 KB |
Output is correct |
21 |
Correct |
28 ms |
20856 KB |
Output is correct |
22 |
Correct |
25 ms |
20856 KB |
Output is correct |
23 |
Correct |
25 ms |
20984 KB |
Output is correct |
24 |
Correct |
25 ms |
20984 KB |
Output is correct |
25 |
Correct |
264 ms |
27548 KB |
Output is correct |
26 |
Correct |
57 ms |
21880 KB |
Output is correct |
27 |
Correct |
331 ms |
30200 KB |
Output is correct |
28 |
Correct |
336 ms |
30076 KB |
Output is correct |
29 |
Correct |
259 ms |
27644 KB |
Output is correct |
30 |
Correct |
230 ms |
27356 KB |
Output is correct |
31 |
Correct |
399 ms |
29176 KB |
Output is correct |
32 |
Correct |
324 ms |
29996 KB |
Output is correct |
33 |
Correct |
313 ms |
29792 KB |
Output is correct |
34 |
Correct |
178 ms |
25336 KB |
Output is correct |
35 |
Correct |
317 ms |
30436 KB |
Output is correct |
36 |
Correct |
316 ms |
30116 KB |
Output is correct |
37 |
Correct |
191 ms |
25720 KB |
Output is correct |
38 |
Correct |
325 ms |
29160 KB |
Output is correct |
39 |
Correct |
68 ms |
22136 KB |
Output is correct |
40 |
Correct |
338 ms |
29080 KB |
Output is correct |
41 |
Correct |
239 ms |
27228 KB |
Output is correct |
42 |
Correct |
319 ms |
29048 KB |
Output is correct |
43 |
Correct |
123 ms |
23816 KB |
Output is correct |
44 |
Correct |
317 ms |
28956 KB |
Output is correct |
45 |
Correct |
85 ms |
22496 KB |
Output is correct |
46 |
Correct |
370 ms |
29048 KB |
Output is correct |
47 |
Correct |
100 ms |
23032 KB |
Output is correct |
48 |
Correct |
317 ms |
28992 KB |
Output is correct |
49 |
Correct |
576 ms |
28520 KB |
Output is correct |
50 |
Correct |
648 ms |
33916 KB |
Output is correct |
51 |
Correct |
436 ms |
30648 KB |
Output is correct |
52 |
Correct |
653 ms |
33804 KB |
Output is correct |
53 |
Correct |
282 ms |
26736 KB |
Output is correct |
54 |
Correct |
638 ms |
34036 KB |
Output is correct |
55 |
Correct |
542 ms |
32236 KB |
Output is correct |
56 |
Correct |
641 ms |
33824 KB |
Output is correct |
57 |
Correct |
105 ms |
23032 KB |
Output is correct |
58 |
Correct |
643 ms |
33996 KB |
Output is correct |
59 |
Correct |
389 ms |
29800 KB |
Output is correct |
60 |
Correct |
650 ms |
33792 KB |
Output is correct |
61 |
Correct |
552 ms |
32704 KB |
Output is correct |
62 |
Correct |
518 ms |
32120 KB |
Output is correct |
63 |
Correct |
446 ms |
32020 KB |
Output is correct |
64 |
Correct |
488 ms |
32012 KB |
Output is correct |
65 |
Correct |
554 ms |
33484 KB |
Output is correct |
66 |
Correct |
501 ms |
32208 KB |
Output is correct |
67 |
Correct |
474 ms |
32012 KB |
Output is correct |
68 |
Correct |
482 ms |
32452 KB |
Output is correct |
69 |
Correct |
528 ms |
32368 KB |
Output is correct |
70 |
Correct |
518 ms |
32160 KB |
Output is correct |
71 |
Correct |
494 ms |
32192 KB |
Output is correct |
72 |
Correct |
448 ms |
31596 KB |
Output is correct |
73 |
Correct |
890 ms |
42484 KB |
Output is correct |
74 |
Correct |
668 ms |
35220 KB |
Output is correct |
75 |
Correct |
831 ms |
41908 KB |
Output is correct |
76 |
Correct |
1079 ms |
46820 KB |
Output is correct |
77 |
Correct |
555 ms |
35332 KB |
Output is correct |
78 |
Correct |
913 ms |
43188 KB |
Output is correct |
79 |
Correct |
966 ms |
44644 KB |
Output is correct |
80 |
Correct |
1060 ms |
46856 KB |
Output is correct |
81 |
Correct |
411 ms |
32904 KB |
Output is correct |
82 |
Correct |
851 ms |
41052 KB |
Output is correct |
83 |
Correct |
781 ms |
40692 KB |
Output is correct |
84 |
Correct |
1067 ms |
46852 KB |
Output is correct |
85 |
Correct |
810 ms |
40080 KB |
Output is correct |
86 |
Correct |
1006 ms |
43952 KB |
Output is correct |
87 |
Correct |
540 ms |
34160 KB |
Output is correct |
88 |
Correct |
945 ms |
43344 KB |
Output is correct |
89 |
Correct |
903 ms |
42220 KB |
Output is correct |
90 |
Correct |
972 ms |
43664 KB |
Output is correct |
91 |
Correct |
644 ms |
36948 KB |
Output is correct |
92 |
Correct |
918 ms |
43648 KB |
Output is correct |
93 |
Correct |
619 ms |
35052 KB |
Output is correct |
94 |
Correct |
976 ms |
43896 KB |
Output is correct |
95 |
Correct |
644 ms |
36100 KB |
Output is correct |
96 |
Correct |
927 ms |
43240 KB |
Output is correct |