#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;
using vi = vector<ll>;
const ll mx = 200'000;
const ll INF = 1'000'000'005;
ll N, Q;
vi H(1+mx), A(1+mx), B(1+mx);
vi L(1+mx), R(1+mx);
const ll Z = (1<<18);
struct segtree
{
vi minH, maxLP, rawAns, l, r;
void build(ll i, ll lv, ll rv)
{
l[i] = lv, r[i] = rv;
if(lv == rv)
{
minH[i] = +INF;
}
else
{
build(2*i, lv, (lv+rv)/2);
build(2*i+1, (lv+rv)/2+1, rv);
minH[i] = min(minH[2*i], minH[2*i+1]);
}
}
void init()
{
minH = vi(Z<<1, INF);
maxLP = vi(Z<<1, -INF);
rawAns = vi(Z<<1, -INF);
l = vi(Z<<1);
r = vi(Z<<1);
build(1, 1, N);
}
void deploy(ll L, ll R, ll V, ll i = 1)
{
if(r[i] < L || R < l[i]) return;
else if(L <= l[i] && r[i] <= R)
{
maxLP[i] = max(maxLP[i], V);
rawAns[i] = max(rawAns[i], maxLP[i] - minH[i]);
}
else
{
deploy(L, R, V, 2*i);
deploy(L, R, V, 2*i+1);
rawAns[i] = max({rawAns[2*i], rawAns[2*i+1], maxLP[i] - minH[i]});
}
}
void pushLazy(int i, ll V)
{
maxLP[i] = max(maxLP[i], V);
rawAns[i] = max(rawAns[i], maxLP[i] - minH[i]);
}
void setH(ll I, ll V, ll i = 1, ll lzv = -INF)
{
// cerr << "setH" << ' ' << I << ' ' << V << ' ' << i << ' ' << l[i] << " - " << r[i] << ' ' << lzv << '\n';
if(l[i] == r[i])
{
rawAns[i] = max(rawAns[i], max(lzv, maxLP[i]) - minH[i]);
minH[i] = V;
maxLP[i] = -INF;
}
else
{
if(I <= (l[i]+r[i])/2)
{
setH(I, V, 2*i, max(lzv, maxLP[i]));
pushLazy(2*i+1, max(lzv, maxLP[i]));
}
else
{
setH(I, V, 2*i+1, max(lzv, maxLP[i]));
pushLazy(2*i, max(lzv, maxLP[i]));
}
minH[i] = min(minH[2*i], minH[2*i+1]);
//rawAns[i] = max({rawAns[2*i], rawAns[2*i+1], maxLP[i] - minH[i]}); //BAD
rawAns[i] = max({rawAns[i], rawAns[2*i], rawAns[2*i+1]});
maxLP[i] = -INF;
}
// cerr << i << ' ' << l[i] << ' ' << r[i] << " : " << minH[i] << ' ' << rawAns[i] << ' ' << maxLP[i] << '\n';
}
ll query(ll L, ll R, ll i = 1, ll topMaxLP = -INF)
{
// cerr << "query : " << L << ' ' << R << ' ' << i << ' ' << l[i] << ' ' << r[i] << " -> " << rawAns[i] << '\n';
if(r[i] < L || R < l[i]) return -INF;
else if(L <= l[i] && r[i] <= R)
{
// cerr << "case Z\n";
// if(L == 2 && R == 2) cerr << "ZZZ " << topMaxLP << ' ' << minH[i] << ' ' << rawAns[i] << '\n';
return max(topMaxLP - minH[i], rawAns[i]);
}
else
{
// if(L == 2 && R == 2) cerr << "YYY " << topMaxLP << ' ' << minH[i] << ' ' << rawAns[i] << '\n';
topMaxLP = max(topMaxLP, maxLP[i]);
return max(query(L, R, 2*i, topMaxLP), query(L, R, 2*i+1, topMaxLP));
}
}
};
signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cin >> N;
for(ll i = 1; i <= N; i++)
{
cin >> H[i] >> A[i] >> B[i];
}
cin >> Q;
for(ll j = 1; j <= Q; j++)
{
cin >> L[j] >> R[j];
}
vi res(1+Q, -1);
segtree S;
for(ll t = 0; t < 2; t++)
{
// cerr << "\n\n\n t = " << t << '\n';
if(t == 1)
{
for(ll i = 1; 2*i <= N; i++)
{
swap(H[i], H[N-i+1]);
swap(A[i], A[N-i+1]);
swap(B[i], B[N-i+1]);
}
for(ll j = 1; j <= Q; j++)
{
L[j] = N+1 - L[j];
R[j] = N+1 - R[j];
swap(L[j], R[j]);
// cerr << L[j] << " <> " << R[j] << "\n";
}
}
// cerr << "\n\n\n t = " << t << '\n';
// for(ll i = 1; i <= N; i++) cerr << i << " : " << H[i] << ' ' << A[i] << ' ' << B[i] << '\n';
vi R_occ[1+N];
for(ll j = 1; j <= Q; j++)
R_occ[R[j]].push_back(j);
vi to_enable[1+N], to_disable[1+N];
for(ll i = 1; i <= N; i++)
{
if(i + A[i] <= N) to_enable[i+A[i]].push_back(i);
if(i + B[i] + 1 <= N) to_disable[i+B[i]+1].push_back(i);
}
S.init();
for(ll r = 1; r <= N; r++)
{
// cerr << "\n\n r = " << r << '\n';
// cerr << H[r] << "\n";
// cerr << A[r] << ' ' << B[r] << '\n';
for(ll i: to_enable[r])
{
// cerr << "enable : " << i << '\n';
S.setH(i, H[i]);
}
// cerr << "answer 2 = " << S.query(2, 2) << "###\n\n\n";
// cerr << "\n\n";
for(ll i: to_disable[r])
{
// cerr << "disable : " << i << '\n';
S.setH(i, INF);
}
// cerr << "answer 2 = " << S.query(2, 2) << "!!!\n\n\n";
ll le = r - B[r];
ll re = r - A[r];
// cerr << "interval = " << le << ' ' << re << '\n';
if(1 <= re)
{
// cerr << "deploy : " << le << ' ' << re << ' ' << H[r] << '\n';
S.deploy(le, re, H[r]);
}
// for(ll i = 1; i <= N; i++) cerr << S.query(i, i) << ' ';
// cerr << '\n';
for(ll j: R_occ[r])
res[j] = max(res[j], S.query(L[j], R[j]));
}
}
for(ll j = 1; j <= Q; j++) cout << res[j] << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
32708 KB |
Output is correct |
2 |
Correct |
23 ms |
32900 KB |
Output is correct |
3 |
Correct |
22 ms |
32736 KB |
Output is correct |
4 |
Correct |
21 ms |
32840 KB |
Output is correct |
5 |
Correct |
21 ms |
32736 KB |
Output is correct |
6 |
Correct |
21 ms |
32828 KB |
Output is correct |
7 |
Correct |
21 ms |
32828 KB |
Output is correct |
8 |
Correct |
21 ms |
32864 KB |
Output is correct |
9 |
Correct |
20 ms |
32748 KB |
Output is correct |
10 |
Correct |
20 ms |
32796 KB |
Output is correct |
11 |
Correct |
20 ms |
32732 KB |
Output is correct |
12 |
Correct |
25 ms |
32832 KB |
Output is correct |
13 |
Correct |
20 ms |
32844 KB |
Output is correct |
14 |
Correct |
20 ms |
32856 KB |
Output is correct |
15 |
Correct |
20 ms |
32848 KB |
Output is correct |
16 |
Correct |
20 ms |
32848 KB |
Output is correct |
17 |
Correct |
20 ms |
32844 KB |
Output is correct |
18 |
Correct |
20 ms |
32856 KB |
Output is correct |
19 |
Correct |
21 ms |
32840 KB |
Output is correct |
20 |
Correct |
19 ms |
32844 KB |
Output is correct |
21 |
Correct |
21 ms |
32756 KB |
Output is correct |
22 |
Correct |
20 ms |
32844 KB |
Output is correct |
23 |
Correct |
21 ms |
32808 KB |
Output is correct |
24 |
Correct |
21 ms |
32840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
32708 KB |
Output is correct |
2 |
Correct |
23 ms |
32900 KB |
Output is correct |
3 |
Correct |
22 ms |
32736 KB |
Output is correct |
4 |
Correct |
21 ms |
32840 KB |
Output is correct |
5 |
Correct |
21 ms |
32736 KB |
Output is correct |
6 |
Correct |
21 ms |
32828 KB |
Output is correct |
7 |
Correct |
21 ms |
32828 KB |
Output is correct |
8 |
Correct |
21 ms |
32864 KB |
Output is correct |
9 |
Correct |
20 ms |
32748 KB |
Output is correct |
10 |
Correct |
20 ms |
32796 KB |
Output is correct |
11 |
Correct |
20 ms |
32732 KB |
Output is correct |
12 |
Correct |
25 ms |
32832 KB |
Output is correct |
13 |
Correct |
20 ms |
32844 KB |
Output is correct |
14 |
Correct |
20 ms |
32856 KB |
Output is correct |
15 |
Correct |
20 ms |
32848 KB |
Output is correct |
16 |
Correct |
20 ms |
32848 KB |
Output is correct |
17 |
Correct |
20 ms |
32844 KB |
Output is correct |
18 |
Correct |
20 ms |
32856 KB |
Output is correct |
19 |
Correct |
21 ms |
32840 KB |
Output is correct |
20 |
Correct |
19 ms |
32844 KB |
Output is correct |
21 |
Correct |
21 ms |
32756 KB |
Output is correct |
22 |
Correct |
20 ms |
32844 KB |
Output is correct |
23 |
Correct |
21 ms |
32808 KB |
Output is correct |
24 |
Correct |
21 ms |
32840 KB |
Output is correct |
25 |
Correct |
97 ms |
36576 KB |
Output is correct |
26 |
Correct |
32 ms |
33472 KB |
Output is correct |
27 |
Correct |
140 ms |
38784 KB |
Output is correct |
28 |
Correct |
143 ms |
38592 KB |
Output is correct |
29 |
Correct |
95 ms |
37252 KB |
Output is correct |
30 |
Correct |
111 ms |
37164 KB |
Output is correct |
31 |
Correct |
105 ms |
38276 KB |
Output is correct |
32 |
Correct |
135 ms |
38612 KB |
Output is correct |
33 |
Correct |
137 ms |
38640 KB |
Output is correct |
34 |
Correct |
76 ms |
35704 KB |
Output is correct |
35 |
Correct |
143 ms |
39504 KB |
Output is correct |
36 |
Correct |
135 ms |
38564 KB |
Output is correct |
37 |
Correct |
87 ms |
36288 KB |
Output is correct |
38 |
Correct |
130 ms |
38596 KB |
Output is correct |
39 |
Correct |
36 ms |
33868 KB |
Output is correct |
40 |
Correct |
133 ms |
38524 KB |
Output is correct |
41 |
Correct |
100 ms |
37480 KB |
Output is correct |
42 |
Correct |
133 ms |
38576 KB |
Output is correct |
43 |
Correct |
58 ms |
35012 KB |
Output is correct |
44 |
Correct |
147 ms |
38540 KB |
Output is correct |
45 |
Correct |
40 ms |
33988 KB |
Output is correct |
46 |
Correct |
131 ms |
38548 KB |
Output is correct |
47 |
Correct |
49 ms |
34536 KB |
Output is correct |
48 |
Correct |
143 ms |
38632 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
415 ms |
48860 KB |
Output is correct |
2 |
Correct |
515 ms |
54980 KB |
Output is correct |
3 |
Correct |
302 ms |
48360 KB |
Output is correct |
4 |
Correct |
487 ms |
55108 KB |
Output is correct |
5 |
Correct |
186 ms |
42952 KB |
Output is correct |
6 |
Correct |
477 ms |
54976 KB |
Output is correct |
7 |
Correct |
386 ms |
52072 KB |
Output is correct |
8 |
Correct |
467 ms |
54976 KB |
Output is correct |
9 |
Correct |
61 ms |
36272 KB |
Output is correct |
10 |
Correct |
472 ms |
55004 KB |
Output is correct |
11 |
Correct |
277 ms |
46648 KB |
Output is correct |
12 |
Correct |
458 ms |
54976 KB |
Output is correct |
13 |
Correct |
264 ms |
54628 KB |
Output is correct |
14 |
Correct |
237 ms |
54320 KB |
Output is correct |
15 |
Correct |
242 ms |
53652 KB |
Output is correct |
16 |
Correct |
224 ms |
53208 KB |
Output is correct |
17 |
Correct |
259 ms |
54872 KB |
Output is correct |
18 |
Correct |
244 ms |
53752 KB |
Output is correct |
19 |
Correct |
244 ms |
54196 KB |
Output is correct |
20 |
Correct |
253 ms |
54244 KB |
Output is correct |
21 |
Correct |
225 ms |
54680 KB |
Output is correct |
22 |
Correct |
236 ms |
54260 KB |
Output is correct |
23 |
Correct |
242 ms |
54340 KB |
Output is correct |
24 |
Correct |
211 ms |
53224 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
21 ms |
32708 KB |
Output is correct |
2 |
Correct |
23 ms |
32900 KB |
Output is correct |
3 |
Correct |
22 ms |
32736 KB |
Output is correct |
4 |
Correct |
21 ms |
32840 KB |
Output is correct |
5 |
Correct |
21 ms |
32736 KB |
Output is correct |
6 |
Correct |
21 ms |
32828 KB |
Output is correct |
7 |
Correct |
21 ms |
32828 KB |
Output is correct |
8 |
Correct |
21 ms |
32864 KB |
Output is correct |
9 |
Correct |
20 ms |
32748 KB |
Output is correct |
10 |
Correct |
20 ms |
32796 KB |
Output is correct |
11 |
Correct |
20 ms |
32732 KB |
Output is correct |
12 |
Correct |
25 ms |
32832 KB |
Output is correct |
13 |
Correct |
20 ms |
32844 KB |
Output is correct |
14 |
Correct |
20 ms |
32856 KB |
Output is correct |
15 |
Correct |
20 ms |
32848 KB |
Output is correct |
16 |
Correct |
20 ms |
32848 KB |
Output is correct |
17 |
Correct |
20 ms |
32844 KB |
Output is correct |
18 |
Correct |
20 ms |
32856 KB |
Output is correct |
19 |
Correct |
21 ms |
32840 KB |
Output is correct |
20 |
Correct |
19 ms |
32844 KB |
Output is correct |
21 |
Correct |
21 ms |
32756 KB |
Output is correct |
22 |
Correct |
20 ms |
32844 KB |
Output is correct |
23 |
Correct |
21 ms |
32808 KB |
Output is correct |
24 |
Correct |
21 ms |
32840 KB |
Output is correct |
25 |
Correct |
97 ms |
36576 KB |
Output is correct |
26 |
Correct |
32 ms |
33472 KB |
Output is correct |
27 |
Correct |
140 ms |
38784 KB |
Output is correct |
28 |
Correct |
143 ms |
38592 KB |
Output is correct |
29 |
Correct |
95 ms |
37252 KB |
Output is correct |
30 |
Correct |
111 ms |
37164 KB |
Output is correct |
31 |
Correct |
105 ms |
38276 KB |
Output is correct |
32 |
Correct |
135 ms |
38612 KB |
Output is correct |
33 |
Correct |
137 ms |
38640 KB |
Output is correct |
34 |
Correct |
76 ms |
35704 KB |
Output is correct |
35 |
Correct |
143 ms |
39504 KB |
Output is correct |
36 |
Correct |
135 ms |
38564 KB |
Output is correct |
37 |
Correct |
87 ms |
36288 KB |
Output is correct |
38 |
Correct |
130 ms |
38596 KB |
Output is correct |
39 |
Correct |
36 ms |
33868 KB |
Output is correct |
40 |
Correct |
133 ms |
38524 KB |
Output is correct |
41 |
Correct |
100 ms |
37480 KB |
Output is correct |
42 |
Correct |
133 ms |
38576 KB |
Output is correct |
43 |
Correct |
58 ms |
35012 KB |
Output is correct |
44 |
Correct |
147 ms |
38540 KB |
Output is correct |
45 |
Correct |
40 ms |
33988 KB |
Output is correct |
46 |
Correct |
131 ms |
38548 KB |
Output is correct |
47 |
Correct |
49 ms |
34536 KB |
Output is correct |
48 |
Correct |
143 ms |
38632 KB |
Output is correct |
49 |
Correct |
415 ms |
48860 KB |
Output is correct |
50 |
Correct |
515 ms |
54980 KB |
Output is correct |
51 |
Correct |
302 ms |
48360 KB |
Output is correct |
52 |
Correct |
487 ms |
55108 KB |
Output is correct |
53 |
Correct |
186 ms |
42952 KB |
Output is correct |
54 |
Correct |
477 ms |
54976 KB |
Output is correct |
55 |
Correct |
386 ms |
52072 KB |
Output is correct |
56 |
Correct |
467 ms |
54976 KB |
Output is correct |
57 |
Correct |
61 ms |
36272 KB |
Output is correct |
58 |
Correct |
472 ms |
55004 KB |
Output is correct |
59 |
Correct |
277 ms |
46648 KB |
Output is correct |
60 |
Correct |
458 ms |
54976 KB |
Output is correct |
61 |
Correct |
264 ms |
54628 KB |
Output is correct |
62 |
Correct |
237 ms |
54320 KB |
Output is correct |
63 |
Correct |
242 ms |
53652 KB |
Output is correct |
64 |
Correct |
224 ms |
53208 KB |
Output is correct |
65 |
Correct |
259 ms |
54872 KB |
Output is correct |
66 |
Correct |
244 ms |
53752 KB |
Output is correct |
67 |
Correct |
244 ms |
54196 KB |
Output is correct |
68 |
Correct |
253 ms |
54244 KB |
Output is correct |
69 |
Correct |
225 ms |
54680 KB |
Output is correct |
70 |
Correct |
236 ms |
54260 KB |
Output is correct |
71 |
Correct |
242 ms |
54340 KB |
Output is correct |
72 |
Correct |
211 ms |
53224 KB |
Output is correct |
73 |
Correct |
723 ms |
59324 KB |
Output is correct |
74 |
Correct |
492 ms |
55756 KB |
Output is correct |
75 |
Correct |
680 ms |
56280 KB |
Output is correct |
76 |
Correct |
824 ms |
63488 KB |
Output is correct |
77 |
Correct |
422 ms |
48560 KB |
Output is correct |
78 |
Correct |
736 ms |
61000 KB |
Output is correct |
79 |
Correct |
739 ms |
60376 KB |
Output is correct |
80 |
Correct |
842 ms |
63564 KB |
Output is correct |
81 |
Correct |
311 ms |
42548 KB |
Output is correct |
82 |
Correct |
680 ms |
59460 KB |
Output is correct |
83 |
Correct |
584 ms |
54344 KB |
Output is correct |
84 |
Correct |
824 ms |
63552 KB |
Output is correct |
85 |
Correct |
478 ms |
59868 KB |
Output is correct |
86 |
Correct |
609 ms |
62648 KB |
Output is correct |
87 |
Correct |
288 ms |
54940 KB |
Output is correct |
88 |
Correct |
589 ms |
61732 KB |
Output is correct |
89 |
Correct |
561 ms |
61264 KB |
Output is correct |
90 |
Correct |
646 ms |
62248 KB |
Output is correct |
91 |
Correct |
380 ms |
57268 KB |
Output is correct |
92 |
Correct |
637 ms |
62808 KB |
Output is correct |
93 |
Correct |
302 ms |
56340 KB |
Output is correct |
94 |
Correct |
626 ms |
62648 KB |
Output is correct |
95 |
Correct |
353 ms |
56752 KB |
Output is correct |
96 |
Correct |
584 ms |
61668 KB |
Output is correct |