#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], Max[maxn], Min[maxn], lmx[maxn], lmn[maxn];
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 |
3 ms |
14680 KB |
Output is correct |
2 |
Correct |
4 ms |
14684 KB |
Output is correct |
3 |
Correct |
3 ms |
14832 KB |
Output is correct |
4 |
Correct |
4 ms |
14684 KB |
Output is correct |
5 |
Correct |
4 ms |
14684 KB |
Output is correct |
6 |
Correct |
4 ms |
14684 KB |
Output is correct |
7 |
Correct |
3 ms |
14840 KB |
Output is correct |
8 |
Correct |
3 ms |
14684 KB |
Output is correct |
9 |
Correct |
4 ms |
14684 KB |
Output is correct |
10 |
Correct |
3 ms |
14684 KB |
Output is correct |
11 |
Correct |
3 ms |
14688 KB |
Output is correct |
12 |
Correct |
3 ms |
14688 KB |
Output is correct |
13 |
Correct |
3 ms |
14684 KB |
Output is correct |
14 |
Correct |
3 ms |
14684 KB |
Output is correct |
15 |
Correct |
3 ms |
14828 KB |
Output is correct |
16 |
Correct |
3 ms |
14684 KB |
Output is correct |
17 |
Correct |
3 ms |
14684 KB |
Output is correct |
18 |
Correct |
3 ms |
14688 KB |
Output is correct |
19 |
Correct |
3 ms |
14684 KB |
Output is correct |
20 |
Correct |
4 ms |
14684 KB |
Output is correct |
21 |
Correct |
4 ms |
14684 KB |
Output is correct |
22 |
Correct |
4 ms |
14684 KB |
Output is correct |
23 |
Correct |
3 ms |
14684 KB |
Output is correct |
24 |
Correct |
4 ms |
14684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14680 KB |
Output is correct |
2 |
Correct |
4 ms |
14684 KB |
Output is correct |
3 |
Correct |
3 ms |
14832 KB |
Output is correct |
4 |
Correct |
4 ms |
14684 KB |
Output is correct |
5 |
Correct |
4 ms |
14684 KB |
Output is correct |
6 |
Correct |
4 ms |
14684 KB |
Output is correct |
7 |
Correct |
3 ms |
14840 KB |
Output is correct |
8 |
Correct |
3 ms |
14684 KB |
Output is correct |
9 |
Correct |
4 ms |
14684 KB |
Output is correct |
10 |
Correct |
3 ms |
14684 KB |
Output is correct |
11 |
Correct |
3 ms |
14688 KB |
Output is correct |
12 |
Correct |
3 ms |
14688 KB |
Output is correct |
13 |
Correct |
3 ms |
14684 KB |
Output is correct |
14 |
Correct |
3 ms |
14684 KB |
Output is correct |
15 |
Correct |
3 ms |
14828 KB |
Output is correct |
16 |
Correct |
3 ms |
14684 KB |
Output is correct |
17 |
Correct |
3 ms |
14684 KB |
Output is correct |
18 |
Correct |
3 ms |
14688 KB |
Output is correct |
19 |
Correct |
3 ms |
14684 KB |
Output is correct |
20 |
Correct |
4 ms |
14684 KB |
Output is correct |
21 |
Correct |
4 ms |
14684 KB |
Output is correct |
22 |
Correct |
4 ms |
14684 KB |
Output is correct |
23 |
Correct |
3 ms |
14684 KB |
Output is correct |
24 |
Correct |
4 ms |
14684 KB |
Output is correct |
25 |
Correct |
48 ms |
18952 KB |
Output is correct |
26 |
Correct |
9 ms |
15268 KB |
Output is correct |
27 |
Correct |
69 ms |
20920 KB |
Output is correct |
28 |
Correct |
70 ms |
20788 KB |
Output is correct |
29 |
Correct |
46 ms |
19036 KB |
Output is correct |
30 |
Correct |
48 ms |
18768 KB |
Output is correct |
31 |
Correct |
54 ms |
19792 KB |
Output is correct |
32 |
Correct |
70 ms |
20772 KB |
Output is correct |
33 |
Correct |
62 ms |
20520 KB |
Output is correct |
34 |
Correct |
35 ms |
17744 KB |
Output is correct |
35 |
Correct |
67 ms |
20816 KB |
Output is correct |
36 |
Correct |
73 ms |
20776 KB |
Output is correct |
37 |
Correct |
40 ms |
17744 KB |
Output is correct |
38 |
Correct |
67 ms |
19800 KB |
Output is correct |
39 |
Correct |
13 ms |
15452 KB |
Output is correct |
40 |
Correct |
67 ms |
19784 KB |
Output is correct |
41 |
Correct |
48 ms |
18516 KB |
Output is correct |
42 |
Correct |
74 ms |
20048 KB |
Output is correct |
43 |
Correct |
25 ms |
16476 KB |
Output is correct |
44 |
Correct |
66 ms |
19792 KB |
Output is correct |
45 |
Correct |
15 ms |
15704 KB |
Output is correct |
46 |
Correct |
67 ms |
19992 KB |
Output is correct |
47 |
Correct |
21 ms |
15964 KB |
Output is correct |
48 |
Correct |
66 ms |
19796 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
62 ms |
42712 KB |
Execution killed with signal 11 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
14680 KB |
Output is correct |
2 |
Correct |
4 ms |
14684 KB |
Output is correct |
3 |
Correct |
3 ms |
14832 KB |
Output is correct |
4 |
Correct |
4 ms |
14684 KB |
Output is correct |
5 |
Correct |
4 ms |
14684 KB |
Output is correct |
6 |
Correct |
4 ms |
14684 KB |
Output is correct |
7 |
Correct |
3 ms |
14840 KB |
Output is correct |
8 |
Correct |
3 ms |
14684 KB |
Output is correct |
9 |
Correct |
4 ms |
14684 KB |
Output is correct |
10 |
Correct |
3 ms |
14684 KB |
Output is correct |
11 |
Correct |
3 ms |
14688 KB |
Output is correct |
12 |
Correct |
3 ms |
14688 KB |
Output is correct |
13 |
Correct |
3 ms |
14684 KB |
Output is correct |
14 |
Correct |
3 ms |
14684 KB |
Output is correct |
15 |
Correct |
3 ms |
14828 KB |
Output is correct |
16 |
Correct |
3 ms |
14684 KB |
Output is correct |
17 |
Correct |
3 ms |
14684 KB |
Output is correct |
18 |
Correct |
3 ms |
14688 KB |
Output is correct |
19 |
Correct |
3 ms |
14684 KB |
Output is correct |
20 |
Correct |
4 ms |
14684 KB |
Output is correct |
21 |
Correct |
4 ms |
14684 KB |
Output is correct |
22 |
Correct |
4 ms |
14684 KB |
Output is correct |
23 |
Correct |
3 ms |
14684 KB |
Output is correct |
24 |
Correct |
4 ms |
14684 KB |
Output is correct |
25 |
Correct |
48 ms |
18952 KB |
Output is correct |
26 |
Correct |
9 ms |
15268 KB |
Output is correct |
27 |
Correct |
69 ms |
20920 KB |
Output is correct |
28 |
Correct |
70 ms |
20788 KB |
Output is correct |
29 |
Correct |
46 ms |
19036 KB |
Output is correct |
30 |
Correct |
48 ms |
18768 KB |
Output is correct |
31 |
Correct |
54 ms |
19792 KB |
Output is correct |
32 |
Correct |
70 ms |
20772 KB |
Output is correct |
33 |
Correct |
62 ms |
20520 KB |
Output is correct |
34 |
Correct |
35 ms |
17744 KB |
Output is correct |
35 |
Correct |
67 ms |
20816 KB |
Output is correct |
36 |
Correct |
73 ms |
20776 KB |
Output is correct |
37 |
Correct |
40 ms |
17744 KB |
Output is correct |
38 |
Correct |
67 ms |
19800 KB |
Output is correct |
39 |
Correct |
13 ms |
15452 KB |
Output is correct |
40 |
Correct |
67 ms |
19784 KB |
Output is correct |
41 |
Correct |
48 ms |
18516 KB |
Output is correct |
42 |
Correct |
74 ms |
20048 KB |
Output is correct |
43 |
Correct |
25 ms |
16476 KB |
Output is correct |
44 |
Correct |
66 ms |
19792 KB |
Output is correct |
45 |
Correct |
15 ms |
15704 KB |
Output is correct |
46 |
Correct |
67 ms |
19992 KB |
Output is correct |
47 |
Correct |
21 ms |
15964 KB |
Output is correct |
48 |
Correct |
66 ms |
19796 KB |
Output is correct |
49 |
Runtime error |
62 ms |
42712 KB |
Execution killed with signal 11 |
50 |
Halted |
0 ms |
0 KB |
- |