#include<bits/stdc++.h>
#define ll int
#define pll pair<ll, ll>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ld long double
#define sz(a) ((ll)(a).size())
using namespace std;
const ll maxn=200005, inf=2e9;
ll h[maxn], a[maxn], b[maxn], ans[maxn];
vector <pll> Q[maxn];
vector <ll> H[maxn];
namespace SegTree
{
ll n, ans[maxn*4], Max[maxn*4], Min[maxn*4], lmx[maxn*4], lmn[maxn*4];
void build(ll i, ll Start, ll End)
{
lmx[i]=Max[i]=-1, lmn[i]=Min[i]=inf, ans[i]=-1;
if (Start==End) return;
ll mid=(Start+End)/2;
build(i*2, Start, mid);
build(i*2+1, mid+1, End);
}
void init(ll sz){n=sz, build(1, 1, n);}
void Move(ll i)
{
if (lmx[i]>-1)
{
ll t=lmx[i]; lmx[i]=-1;
lmx[i*2]=max(lmx[i*2], t);
ans[i*2]=max(ans[i*2], t-Min[i*2]);
lmx[i*2+1]=max(lmx[i*2+1], t);
ans[i*2+1]=max(ans[i*2+1], t-Min[i*2+1]);
}
if (lmn[i]<inf)
{
ll t=lmn[i]; lmn[i]=inf;
lmn[i*2]=min(lmn[i*2], t);
ans[i*2]=max(ans[i*2], Max[i*2]-t);
lmn[i*2+1]=min(lmn[i*2+1], t);
ans[i*2+1]=max(ans[i*2+1], Max[i*2+1]-t);
}
}
void toggle(ll i, ll Start, ll End, ll idx)
{
if (Start>idx || End<idx) return;
if (Start==End)
{
if (Max[i]>=0) Max[i]=-1, Min[i]=inf;
else Max[i]=Min[i]=h[Start];
return;
}
ll mid=(Start+End)/2; Move(i);
if (idx<=mid) toggle(i*2, Start, mid, idx);
else toggle(i*2+1, mid+1, End, idx);
Max[i]=max(Max[i*2], Max[i*2+1]);
Min[i]=min(Min[i*2], Min[i*2+1]);
}
void toggle(ll idx) {
// cout << "toggle: " << idx << "\n";
toggle(1, 1, n, idx);}
void update(ll i, ll Start, ll End, ll l, ll r, ll v)
{
if (Start>r || End<l) return;
if (Start>=l && End<=r)
{
lmx[i]=max(lmx[i], v), lmn[i]=min(lmn[i], v);
ans[i]=max({ans[i], v-Min[i], Max[i]-v});
return;
}
ll mid=(Start+End)/2; Move(i);
if (mid>=l) update(i*2, Start, mid, l, r, v);
if (mid+1<=r) update(i*2+1, mid+1, End, l, r, v);
ans[i]=max({ans[i], ans[i*2], ans[i*2+1]});
}
void update(ll l, ll r, ll v) {
// cout << "update: " << l << " " << r << " " << v << "\n";
update(1, 1, n, l, r, v);}
ll query(ll i, ll Start, ll End, ll l, ll r)
{
if (Start>r || End<l) return -1;
if (Start>=l && End<=r) return ans[i];
ll mid=(Start+End)/2; Move(i);
if (mid<l) return query(i*2+1, mid+1, End, l, r);
if (mid+1>r) return query(i*2, Start, mid, l, r);
return max(query(i*2, Start, mid, l, r), query(i*2+1, mid+1, End, l, r));
}
ll query(ll l, ll r){
// cout << "query: " << l << " " << r << " " << query(1, 1, n, l, r) << "\n";
return query(1, 1, n, l, r);}
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
ll n; cin >> n;
for (ll i=1; i<=n; i++)
{
cin >> h[i] >> a[i] >> b[i];
if (i+a[i]<=n) H[i+a[i]].pb(i);
if (i+b[i]+1<=n) H[i+b[i]+1].pb(i);
}
ll q; cin >> q;
for (ll i=1; i<=q; i++)
{
ll l, r; cin >> l >> r, ans[i]=-1;
Q[r].pb({l, i});
}
SegTree::init(n);
for (ll i=1; i<=n; i++)
{
// cout << "order: " << i << "\n";
for (ll x:H[i]) SegTree::toggle(x);
SegTree::update(i-b[i], i-a[i], h[i]);
for (auto [l, idx]:Q[i])
ans[idx]=max(ans[idx], SegTree::query(l, i));
}
for (ll i=1; i<=q; i++) cout << ans[i] << " ";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
20824 KB |
Output is correct |
2 |
Correct |
4 ms |
20824 KB |
Output is correct |
3 |
Correct |
4 ms |
20828 KB |
Output is correct |
4 |
Correct |
5 ms |
20824 KB |
Output is correct |
5 |
Correct |
4 ms |
20824 KB |
Output is correct |
6 |
Correct |
4 ms |
20920 KB |
Output is correct |
7 |
Correct |
4 ms |
20828 KB |
Output is correct |
8 |
Correct |
4 ms |
20828 KB |
Output is correct |
9 |
Correct |
5 ms |
20924 KB |
Output is correct |
10 |
Correct |
4 ms |
20824 KB |
Output is correct |
11 |
Correct |
5 ms |
20824 KB |
Output is correct |
12 |
Correct |
4 ms |
21012 KB |
Output is correct |
13 |
Correct |
4 ms |
20824 KB |
Output is correct |
14 |
Correct |
4 ms |
20828 KB |
Output is correct |
15 |
Correct |
4 ms |
20828 KB |
Output is correct |
16 |
Correct |
4 ms |
20920 KB |
Output is correct |
17 |
Correct |
4 ms |
20828 KB |
Output is correct |
18 |
Correct |
4 ms |
20828 KB |
Output is correct |
19 |
Correct |
4 ms |
20828 KB |
Output is correct |
20 |
Correct |
4 ms |
20920 KB |
Output is correct |
21 |
Correct |
4 ms |
21000 KB |
Output is correct |
22 |
Correct |
4 ms |
21172 KB |
Output is correct |
23 |
Correct |
4 ms |
20828 KB |
Output is correct |
24 |
Correct |
4 ms |
20828 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
20824 KB |
Output is correct |
2 |
Correct |
4 ms |
20824 KB |
Output is correct |
3 |
Correct |
4 ms |
20828 KB |
Output is correct |
4 |
Correct |
5 ms |
20824 KB |
Output is correct |
5 |
Correct |
4 ms |
20824 KB |
Output is correct |
6 |
Correct |
4 ms |
20920 KB |
Output is correct |
7 |
Correct |
4 ms |
20828 KB |
Output is correct |
8 |
Correct |
4 ms |
20828 KB |
Output is correct |
9 |
Correct |
5 ms |
20924 KB |
Output is correct |
10 |
Correct |
4 ms |
20824 KB |
Output is correct |
11 |
Correct |
5 ms |
20824 KB |
Output is correct |
12 |
Correct |
4 ms |
21012 KB |
Output is correct |
13 |
Correct |
4 ms |
20824 KB |
Output is correct |
14 |
Correct |
4 ms |
20828 KB |
Output is correct |
15 |
Correct |
4 ms |
20828 KB |
Output is correct |
16 |
Correct |
4 ms |
20920 KB |
Output is correct |
17 |
Correct |
4 ms |
20828 KB |
Output is correct |
18 |
Correct |
4 ms |
20828 KB |
Output is correct |
19 |
Correct |
4 ms |
20828 KB |
Output is correct |
20 |
Correct |
4 ms |
20920 KB |
Output is correct |
21 |
Correct |
4 ms |
21000 KB |
Output is correct |
22 |
Correct |
4 ms |
21172 KB |
Output is correct |
23 |
Correct |
4 ms |
20828 KB |
Output is correct |
24 |
Correct |
4 ms |
20828 KB |
Output is correct |
25 |
Correct |
48 ms |
23888 KB |
Output is correct |
26 |
Correct |
10 ms |
21340 KB |
Output is correct |
27 |
Correct |
68 ms |
25172 KB |
Output is correct |
28 |
Correct |
69 ms |
25168 KB |
Output is correct |
29 |
Correct |
47 ms |
23888 KB |
Output is correct |
30 |
Correct |
61 ms |
23632 KB |
Output is correct |
31 |
Correct |
54 ms |
24656 KB |
Output is correct |
32 |
Correct |
70 ms |
25044 KB |
Output is correct |
33 |
Correct |
63 ms |
24964 KB |
Output is correct |
34 |
Correct |
37 ms |
22864 KB |
Output is correct |
35 |
Correct |
67 ms |
25172 KB |
Output is correct |
36 |
Correct |
69 ms |
25068 KB |
Output is correct |
37 |
Correct |
40 ms |
22868 KB |
Output is correct |
38 |
Correct |
67 ms |
24148 KB |
Output is correct |
39 |
Correct |
13 ms |
21340 KB |
Output is correct |
40 |
Correct |
67 ms |
24260 KB |
Output is correct |
41 |
Correct |
57 ms |
23380 KB |
Output is correct |
42 |
Correct |
67 ms |
24260 KB |
Output is correct |
43 |
Correct |
25 ms |
22092 KB |
Output is correct |
44 |
Correct |
67 ms |
24280 KB |
Output is correct |
45 |
Correct |
16 ms |
21592 KB |
Output is correct |
46 |
Correct |
67 ms |
24148 KB |
Output is correct |
47 |
Correct |
20 ms |
21852 KB |
Output is correct |
48 |
Correct |
67 ms |
24120 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
159 ms |
31104 KB |
Output is correct |
2 |
Correct |
165 ms |
35880 KB |
Output is correct |
3 |
Correct |
107 ms |
33104 KB |
Output is correct |
4 |
Correct |
170 ms |
36288 KB |
Output is correct |
5 |
Correct |
64 ms |
29016 KB |
Output is correct |
6 |
Correct |
167 ms |
36180 KB |
Output is correct |
7 |
Correct |
135 ms |
34756 KB |
Output is correct |
8 |
Correct |
159 ms |
36056 KB |
Output is correct |
9 |
Correct |
24 ms |
26456 KB |
Output is correct |
10 |
Correct |
165 ms |
36080 KB |
Output is correct |
11 |
Correct |
94 ms |
30548 KB |
Output is correct |
12 |
Correct |
160 ms |
36060 KB |
Output is correct |
13 |
Correct |
112 ms |
33828 KB |
Output is correct |
14 |
Correct |
97 ms |
34000 KB |
Output is correct |
15 |
Correct |
105 ms |
34044 KB |
Output is correct |
16 |
Correct |
90 ms |
34384 KB |
Output is correct |
17 |
Correct |
115 ms |
34096 KB |
Output is correct |
18 |
Correct |
97 ms |
34384 KB |
Output is correct |
19 |
Correct |
100 ms |
33900 KB |
Output is correct |
20 |
Correct |
99 ms |
34040 KB |
Output is correct |
21 |
Correct |
101 ms |
33736 KB |
Output is correct |
22 |
Correct |
100 ms |
33892 KB |
Output is correct |
23 |
Correct |
102 ms |
33852 KB |
Output is correct |
24 |
Correct |
87 ms |
33940 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
20824 KB |
Output is correct |
2 |
Correct |
4 ms |
20824 KB |
Output is correct |
3 |
Correct |
4 ms |
20828 KB |
Output is correct |
4 |
Correct |
5 ms |
20824 KB |
Output is correct |
5 |
Correct |
4 ms |
20824 KB |
Output is correct |
6 |
Correct |
4 ms |
20920 KB |
Output is correct |
7 |
Correct |
4 ms |
20828 KB |
Output is correct |
8 |
Correct |
4 ms |
20828 KB |
Output is correct |
9 |
Correct |
5 ms |
20924 KB |
Output is correct |
10 |
Correct |
4 ms |
20824 KB |
Output is correct |
11 |
Correct |
5 ms |
20824 KB |
Output is correct |
12 |
Correct |
4 ms |
21012 KB |
Output is correct |
13 |
Correct |
4 ms |
20824 KB |
Output is correct |
14 |
Correct |
4 ms |
20828 KB |
Output is correct |
15 |
Correct |
4 ms |
20828 KB |
Output is correct |
16 |
Correct |
4 ms |
20920 KB |
Output is correct |
17 |
Correct |
4 ms |
20828 KB |
Output is correct |
18 |
Correct |
4 ms |
20828 KB |
Output is correct |
19 |
Correct |
4 ms |
20828 KB |
Output is correct |
20 |
Correct |
4 ms |
20920 KB |
Output is correct |
21 |
Correct |
4 ms |
21000 KB |
Output is correct |
22 |
Correct |
4 ms |
21172 KB |
Output is correct |
23 |
Correct |
4 ms |
20828 KB |
Output is correct |
24 |
Correct |
4 ms |
20828 KB |
Output is correct |
25 |
Correct |
48 ms |
23888 KB |
Output is correct |
26 |
Correct |
10 ms |
21340 KB |
Output is correct |
27 |
Correct |
68 ms |
25172 KB |
Output is correct |
28 |
Correct |
69 ms |
25168 KB |
Output is correct |
29 |
Correct |
47 ms |
23888 KB |
Output is correct |
30 |
Correct |
61 ms |
23632 KB |
Output is correct |
31 |
Correct |
54 ms |
24656 KB |
Output is correct |
32 |
Correct |
70 ms |
25044 KB |
Output is correct |
33 |
Correct |
63 ms |
24964 KB |
Output is correct |
34 |
Correct |
37 ms |
22864 KB |
Output is correct |
35 |
Correct |
67 ms |
25172 KB |
Output is correct |
36 |
Correct |
69 ms |
25068 KB |
Output is correct |
37 |
Correct |
40 ms |
22868 KB |
Output is correct |
38 |
Correct |
67 ms |
24148 KB |
Output is correct |
39 |
Correct |
13 ms |
21340 KB |
Output is correct |
40 |
Correct |
67 ms |
24260 KB |
Output is correct |
41 |
Correct |
57 ms |
23380 KB |
Output is correct |
42 |
Correct |
67 ms |
24260 KB |
Output is correct |
43 |
Correct |
25 ms |
22092 KB |
Output is correct |
44 |
Correct |
67 ms |
24280 KB |
Output is correct |
45 |
Correct |
16 ms |
21592 KB |
Output is correct |
46 |
Correct |
67 ms |
24148 KB |
Output is correct |
47 |
Correct |
20 ms |
21852 KB |
Output is correct |
48 |
Correct |
67 ms |
24120 KB |
Output is correct |
49 |
Correct |
159 ms |
31104 KB |
Output is correct |
50 |
Correct |
165 ms |
35880 KB |
Output is correct |
51 |
Correct |
107 ms |
33104 KB |
Output is correct |
52 |
Correct |
170 ms |
36288 KB |
Output is correct |
53 |
Correct |
64 ms |
29016 KB |
Output is correct |
54 |
Correct |
167 ms |
36180 KB |
Output is correct |
55 |
Correct |
135 ms |
34756 KB |
Output is correct |
56 |
Correct |
159 ms |
36056 KB |
Output is correct |
57 |
Correct |
24 ms |
26456 KB |
Output is correct |
58 |
Correct |
165 ms |
36080 KB |
Output is correct |
59 |
Correct |
94 ms |
30548 KB |
Output is correct |
60 |
Correct |
160 ms |
36060 KB |
Output is correct |
61 |
Correct |
112 ms |
33828 KB |
Output is correct |
62 |
Correct |
97 ms |
34000 KB |
Output is correct |
63 |
Correct |
105 ms |
34044 KB |
Output is correct |
64 |
Correct |
90 ms |
34384 KB |
Output is correct |
65 |
Correct |
115 ms |
34096 KB |
Output is correct |
66 |
Correct |
97 ms |
34384 KB |
Output is correct |
67 |
Correct |
100 ms |
33900 KB |
Output is correct |
68 |
Correct |
99 ms |
34040 KB |
Output is correct |
69 |
Correct |
101 ms |
33736 KB |
Output is correct |
70 |
Correct |
100 ms |
33892 KB |
Output is correct |
71 |
Correct |
102 ms |
33852 KB |
Output is correct |
72 |
Correct |
87 ms |
33940 KB |
Output is correct |
73 |
Correct |
271 ms |
41284 KB |
Output is correct |
74 |
Correct |
176 ms |
36724 KB |
Output is correct |
75 |
Correct |
231 ms |
41044 KB |
Output is correct |
76 |
Correct |
311 ms |
44264 KB |
Output is correct |
77 |
Correct |
156 ms |
34612 KB |
Output is correct |
78 |
Correct |
251 ms |
41712 KB |
Output is correct |
79 |
Correct |
275 ms |
42804 KB |
Output is correct |
80 |
Correct |
295 ms |
44116 KB |
Output is correct |
81 |
Correct |
122 ms |
33124 KB |
Output is correct |
82 |
Correct |
250 ms |
40264 KB |
Output is correct |
83 |
Correct |
227 ms |
38160 KB |
Output is correct |
84 |
Correct |
302 ms |
44116 KB |
Output is correct |
85 |
Correct |
176 ms |
38432 KB |
Output is correct |
86 |
Correct |
226 ms |
40912 KB |
Output is correct |
87 |
Correct |
118 ms |
35156 KB |
Output is correct |
88 |
Correct |
218 ms |
41556 KB |
Output is correct |
89 |
Correct |
196 ms |
39728 KB |
Output is correct |
90 |
Correct |
217 ms |
41720 KB |
Output is correct |
91 |
Correct |
148 ms |
36528 KB |
Output is correct |
92 |
Correct |
213 ms |
40992 KB |
Output is correct |
93 |
Correct |
116 ms |
35016 KB |
Output is correct |
94 |
Correct |
228 ms |
41252 KB |
Output is correct |
95 |
Correct |
134 ms |
36164 KB |
Output is correct |
96 |
Correct |
219 ms |
41304 KB |
Output is correct |