// ~Be name khoda~ //
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
#define cl clear
#define endll '\n'
const int maxn = 1e6 + 10;
const int maxn5 = 2e5 + 10;
const int maxnt = 8e5 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
struct javab{
ll val1, val2, mn, mx, ans1, ans2;
javab(){
val1 = val2 = mn = mx = ans1 = ans2 = -1 * inf;
return;
}
} seg[maxnt];
int a[maxn5], b[maxn5], h[maxn5], l[maxn5], r[maxn5];
vector <pair<int, pair<int, int>>> eve;
vector <int> req;
ll out[maxn5];
void shift(int, int, int);
inline bool cmp(int i, int j){return l[i] > l[j];}
inline void recalc(int v){
seg[v].ans1 = max(seg[v].ans1, seg[v].val1 + seg[v].mn);
seg[v].ans2 = max(seg[v].ans2, seg[v].val2 + seg[v].mx);
return;
}
inline javab multi(javab a, javab b, javab c, bool ty){
javab ret;
ret.val1 = max(b.val1, c.val1);
ret.val2 = max(b.val2, c.val2);
ret.ans1 = max(b.ans1, c.ans1);
ret.ans2 = max(b.ans2, c.ans2);
if(ty){
ret.ans1 = max(ret.ans1, a.ans1);
ret.ans2 = max(ret.ans2, a.ans2);
}
return ret;
}
inline void setval(int l, int r, int ind, ll va1, ll va2, int v){
if(r - l == 1){
seg[v].mn = seg[v].mx = -1 * inf;
seg[v].val1 = va1;
seg[v].val2 = va2;
//recalc(v);
//cout << "ok setval " << l << ' ' << r << ' ' << seg[v].val1 << ' ' << seg[v].ans1 << endl;
return;
}
int mid = (l + r) >> 1; shift(v, l, r);
if(ind < mid)
setval(l, mid, ind, va1, va2, v * 2);
else
setval(mid, r, ind, va1, va2, v * 2 + 1);
seg[v] = multi(seg[v], seg[v * 2], seg[v * 2 + 1], true);
//cout << "righttt " << l << ' ' << r << ' ' << seg[v].ans1 << ' ' << seg[v].mn << endl;
return;
}
inline void setmax(int l, int r, int lq, int rq, ll va1, ll va2, int v){
//cout << "em vel " << l << ' ' << r << ' ' << lq << ' ' << rq << endl;
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
seg[v].mn = max(seg[v].mn, va1);
seg[v].mx = max(seg[v].mx, va2);
recalc(v);
// << ' ' << l << ' ' << r << ' ' << va1 << ' ' << seg[v].ans1 << ' ' << seg[v].mn << ' ' << seg[v].val1 << endl;
return;
}
int mid = (l + r) >> 1; shift(v, l, r);
setmax(l, mid, lq, rq, va1, va2, v * 2);
setmax(mid, r, lq, rq, va1, va2, v * 2 + 1);
seg[v] = multi(seg[v], seg[v * 2], seg[v * 2 + 1], true);
return;
}
inline ll get_max(int l, int r, int lq, int rq, int v){
//cout << "hey getting max! " << endl;
if(rq <= l || r <= lq)
return -1 * inf;
if(lq <= l && r <= rq){
//<< l << ' ' << r << ' ' << seg[v].ans1 << ' ' << seg[v].val1 << ' ' << seg[v].mn << endl;
return max(seg[v].ans1, seg[v].ans2);
}
int mid = (l + r) >> 1; shift(v, l, r);
return max(get_max(l, mid, lq, rq, v * 2), get_max(mid, r, lq, rq, v * 2 + 1));
}
inline void shift(int v, int l, int r){
int mid = (l + r) >> 1;
setmax(l, mid, l, mid, seg[v].mn, seg[v].mx, v * 2);
setmax(mid, r, mid, r, seg[v].mn, seg[v].mx, v * 2 + 1);
seg[v].mn = seg[v].mx = -1 * inf;
return;
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int n; cin >> n;
for(int i = 0; i < n; i++){
cin >> h[i] >> a[i] >> b[i];
eve.pb({i, {0, i}});
eve.pb({i - a[i], {1, i}});
eve.pb({i - b[i] - 1, {2, i}});
}
sort(all(eve));
int q; cin >> q;
for(int i = 0; i < q; i++){
cin >> l[i] >> r[i];
l[i]--;
r[i]--;
req.pb(i);
}
sort(all(req), cmp); // az l bozorg be koochak
for(auto i : req){
//cout << "aha " << l[i] << ' ' << eve.size() << ' ' << eve.back().fi << endl;
while(!eve.empty() && eve.back().fi >= l[i]){
int ty = eve.back().se.fi, id = eve.back().se.se;
eve.pop_back();
if(ty == 0){
setmax(0, n, min(n, id + a[id]), min(n, id + b[id] + 1), -h[id], h[id], 1);
setval(0, n, id, -1 * inf, -1 * inf, 1);
}
if(ty == 1){
setval(0, n, id, h[id], -1 * h[id], 1);
}
if(ty == 2){
setval(0, n, id, -1 * inf, -1 * inf, 1);
}
//cout << "after event of " << ty << ' ' << id << ' ' << seg[1].ans1 << ' ' << seg[1].ans2 << endl;
}
out[i] = get_max(0, n, l[i], r[i] + 1, 1);
}
for(int i = 0; i < q; i++)
cout << (out[i] < 0 ? -1 : out[i]) << '\n';
}
/*
20
260055884 2 15
737689751 5 5
575359903 1 15
341907415 14 14
162026576 9 19
55126745 10 19
95712405 11 14
416027186 8 13
370819848 11 14
629309664 4 13
822713895 5 15
390716905 13 17
577166133 8 19
195931195 10 17
377030463 14 17
968486685 11 19
963040581 4 10
566835557 1 12
586336111 6 16
385865831 8 9
1
1 20
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
37896 KB |
Output is correct |
2 |
Correct |
32 ms |
37880 KB |
Output is correct |
3 |
Correct |
21 ms |
37888 KB |
Output is correct |
4 |
Correct |
20 ms |
37908 KB |
Output is correct |
5 |
Correct |
16 ms |
37896 KB |
Output is correct |
6 |
Correct |
16 ms |
37900 KB |
Output is correct |
7 |
Correct |
15 ms |
37904 KB |
Output is correct |
8 |
Correct |
21 ms |
37836 KB |
Output is correct |
9 |
Correct |
17 ms |
37836 KB |
Output is correct |
10 |
Correct |
20 ms |
37900 KB |
Output is correct |
11 |
Correct |
16 ms |
37836 KB |
Output is correct |
12 |
Correct |
31 ms |
37840 KB |
Output is correct |
13 |
Correct |
17 ms |
37836 KB |
Output is correct |
14 |
Correct |
23 ms |
37836 KB |
Output is correct |
15 |
Correct |
22 ms |
37892 KB |
Output is correct |
16 |
Correct |
21 ms |
37908 KB |
Output is correct |
17 |
Correct |
23 ms |
37836 KB |
Output is correct |
18 |
Correct |
24 ms |
37932 KB |
Output is correct |
19 |
Correct |
18 ms |
37836 KB |
Output is correct |
20 |
Correct |
29 ms |
37816 KB |
Output is correct |
21 |
Correct |
20 ms |
37912 KB |
Output is correct |
22 |
Correct |
19 ms |
37888 KB |
Output is correct |
23 |
Correct |
30 ms |
37904 KB |
Output is correct |
24 |
Correct |
32 ms |
37900 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
37896 KB |
Output is correct |
2 |
Correct |
32 ms |
37880 KB |
Output is correct |
3 |
Correct |
21 ms |
37888 KB |
Output is correct |
4 |
Correct |
20 ms |
37908 KB |
Output is correct |
5 |
Correct |
16 ms |
37896 KB |
Output is correct |
6 |
Correct |
16 ms |
37900 KB |
Output is correct |
7 |
Correct |
15 ms |
37904 KB |
Output is correct |
8 |
Correct |
21 ms |
37836 KB |
Output is correct |
9 |
Correct |
17 ms |
37836 KB |
Output is correct |
10 |
Correct |
20 ms |
37900 KB |
Output is correct |
11 |
Correct |
16 ms |
37836 KB |
Output is correct |
12 |
Correct |
31 ms |
37840 KB |
Output is correct |
13 |
Correct |
17 ms |
37836 KB |
Output is correct |
14 |
Correct |
23 ms |
37836 KB |
Output is correct |
15 |
Correct |
22 ms |
37892 KB |
Output is correct |
16 |
Correct |
21 ms |
37908 KB |
Output is correct |
17 |
Correct |
23 ms |
37836 KB |
Output is correct |
18 |
Correct |
24 ms |
37932 KB |
Output is correct |
19 |
Correct |
18 ms |
37836 KB |
Output is correct |
20 |
Correct |
29 ms |
37816 KB |
Output is correct |
21 |
Correct |
20 ms |
37912 KB |
Output is correct |
22 |
Correct |
19 ms |
37888 KB |
Output is correct |
23 |
Correct |
30 ms |
37904 KB |
Output is correct |
24 |
Correct |
32 ms |
37900 KB |
Output is correct |
25 |
Correct |
132 ms |
43320 KB |
Output is correct |
26 |
Correct |
34 ms |
38568 KB |
Output is correct |
27 |
Correct |
223 ms |
45516 KB |
Output is correct |
28 |
Correct |
206 ms |
45624 KB |
Output is correct |
29 |
Correct |
128 ms |
43320 KB |
Output is correct |
30 |
Correct |
201 ms |
43032 KB |
Output is correct |
31 |
Correct |
182 ms |
44808 KB |
Output is correct |
32 |
Correct |
240 ms |
45620 KB |
Output is correct |
33 |
Correct |
222 ms |
45068 KB |
Output is correct |
34 |
Correct |
112 ms |
41668 KB |
Output is correct |
35 |
Correct |
240 ms |
45468 KB |
Output is correct |
36 |
Correct |
213 ms |
45592 KB |
Output is correct |
37 |
Correct |
145 ms |
41860 KB |
Output is correct |
38 |
Correct |
182 ms |
44676 KB |
Output is correct |
39 |
Correct |
51 ms |
38968 KB |
Output is correct |
40 |
Correct |
188 ms |
44644 KB |
Output is correct |
41 |
Correct |
134 ms |
42888 KB |
Output is correct |
42 |
Correct |
213 ms |
44608 KB |
Output is correct |
43 |
Correct |
66 ms |
40256 KB |
Output is correct |
44 |
Correct |
168 ms |
44724 KB |
Output is correct |
45 |
Correct |
75 ms |
39228 KB |
Output is correct |
46 |
Correct |
244 ms |
44688 KB |
Output is correct |
47 |
Correct |
123 ms |
39840 KB |
Output is correct |
48 |
Correct |
172 ms |
44684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
428 ms |
56368 KB |
Output is correct |
2 |
Correct |
490 ms |
56612 KB |
Output is correct |
3 |
Correct |
372 ms |
47696 KB |
Output is correct |
4 |
Correct |
535 ms |
56552 KB |
Output is correct |
5 |
Correct |
243 ms |
47112 KB |
Output is correct |
6 |
Correct |
551 ms |
56548 KB |
Output is correct |
7 |
Correct |
408 ms |
50000 KB |
Output is correct |
8 |
Correct |
466 ms |
56576 KB |
Output is correct |
9 |
Correct |
110 ms |
40380 KB |
Output is correct |
10 |
Correct |
469 ms |
56604 KB |
Output is correct |
11 |
Correct |
290 ms |
47272 KB |
Output is correct |
12 |
Correct |
539 ms |
56564 KB |
Output is correct |
13 |
Correct |
436 ms |
56484 KB |
Output is correct |
14 |
Correct |
401 ms |
56484 KB |
Output is correct |
15 |
Correct |
396 ms |
56480 KB |
Output is correct |
16 |
Correct |
408 ms |
56472 KB |
Output is correct |
17 |
Correct |
470 ms |
56460 KB |
Output is correct |
18 |
Correct |
409 ms |
56480 KB |
Output is correct |
19 |
Correct |
415 ms |
56476 KB |
Output is correct |
20 |
Correct |
459 ms |
56444 KB |
Output is correct |
21 |
Correct |
381 ms |
56412 KB |
Output is correct |
22 |
Correct |
406 ms |
56412 KB |
Output is correct |
23 |
Correct |
446 ms |
56484 KB |
Output is correct |
24 |
Correct |
406 ms |
56488 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
37896 KB |
Output is correct |
2 |
Correct |
32 ms |
37880 KB |
Output is correct |
3 |
Correct |
21 ms |
37888 KB |
Output is correct |
4 |
Correct |
20 ms |
37908 KB |
Output is correct |
5 |
Correct |
16 ms |
37896 KB |
Output is correct |
6 |
Correct |
16 ms |
37900 KB |
Output is correct |
7 |
Correct |
15 ms |
37904 KB |
Output is correct |
8 |
Correct |
21 ms |
37836 KB |
Output is correct |
9 |
Correct |
17 ms |
37836 KB |
Output is correct |
10 |
Correct |
20 ms |
37900 KB |
Output is correct |
11 |
Correct |
16 ms |
37836 KB |
Output is correct |
12 |
Correct |
31 ms |
37840 KB |
Output is correct |
13 |
Correct |
17 ms |
37836 KB |
Output is correct |
14 |
Correct |
23 ms |
37836 KB |
Output is correct |
15 |
Correct |
22 ms |
37892 KB |
Output is correct |
16 |
Correct |
21 ms |
37908 KB |
Output is correct |
17 |
Correct |
23 ms |
37836 KB |
Output is correct |
18 |
Correct |
24 ms |
37932 KB |
Output is correct |
19 |
Correct |
18 ms |
37836 KB |
Output is correct |
20 |
Correct |
29 ms |
37816 KB |
Output is correct |
21 |
Correct |
20 ms |
37912 KB |
Output is correct |
22 |
Correct |
19 ms |
37888 KB |
Output is correct |
23 |
Correct |
30 ms |
37904 KB |
Output is correct |
24 |
Correct |
32 ms |
37900 KB |
Output is correct |
25 |
Correct |
132 ms |
43320 KB |
Output is correct |
26 |
Correct |
34 ms |
38568 KB |
Output is correct |
27 |
Correct |
223 ms |
45516 KB |
Output is correct |
28 |
Correct |
206 ms |
45624 KB |
Output is correct |
29 |
Correct |
128 ms |
43320 KB |
Output is correct |
30 |
Correct |
201 ms |
43032 KB |
Output is correct |
31 |
Correct |
182 ms |
44808 KB |
Output is correct |
32 |
Correct |
240 ms |
45620 KB |
Output is correct |
33 |
Correct |
222 ms |
45068 KB |
Output is correct |
34 |
Correct |
112 ms |
41668 KB |
Output is correct |
35 |
Correct |
240 ms |
45468 KB |
Output is correct |
36 |
Correct |
213 ms |
45592 KB |
Output is correct |
37 |
Correct |
145 ms |
41860 KB |
Output is correct |
38 |
Correct |
182 ms |
44676 KB |
Output is correct |
39 |
Correct |
51 ms |
38968 KB |
Output is correct |
40 |
Correct |
188 ms |
44644 KB |
Output is correct |
41 |
Correct |
134 ms |
42888 KB |
Output is correct |
42 |
Correct |
213 ms |
44608 KB |
Output is correct |
43 |
Correct |
66 ms |
40256 KB |
Output is correct |
44 |
Correct |
168 ms |
44724 KB |
Output is correct |
45 |
Correct |
75 ms |
39228 KB |
Output is correct |
46 |
Correct |
244 ms |
44688 KB |
Output is correct |
47 |
Correct |
123 ms |
39840 KB |
Output is correct |
48 |
Correct |
172 ms |
44684 KB |
Output is correct |
49 |
Correct |
428 ms |
56368 KB |
Output is correct |
50 |
Correct |
490 ms |
56612 KB |
Output is correct |
51 |
Correct |
372 ms |
47696 KB |
Output is correct |
52 |
Correct |
535 ms |
56552 KB |
Output is correct |
53 |
Correct |
243 ms |
47112 KB |
Output is correct |
54 |
Correct |
551 ms |
56548 KB |
Output is correct |
55 |
Correct |
408 ms |
50000 KB |
Output is correct |
56 |
Correct |
466 ms |
56576 KB |
Output is correct |
57 |
Correct |
110 ms |
40380 KB |
Output is correct |
58 |
Correct |
469 ms |
56604 KB |
Output is correct |
59 |
Correct |
290 ms |
47272 KB |
Output is correct |
60 |
Correct |
539 ms |
56564 KB |
Output is correct |
61 |
Correct |
436 ms |
56484 KB |
Output is correct |
62 |
Correct |
401 ms |
56484 KB |
Output is correct |
63 |
Correct |
396 ms |
56480 KB |
Output is correct |
64 |
Correct |
408 ms |
56472 KB |
Output is correct |
65 |
Correct |
470 ms |
56460 KB |
Output is correct |
66 |
Correct |
409 ms |
56480 KB |
Output is correct |
67 |
Correct |
415 ms |
56476 KB |
Output is correct |
68 |
Correct |
459 ms |
56444 KB |
Output is correct |
69 |
Correct |
381 ms |
56412 KB |
Output is correct |
70 |
Correct |
406 ms |
56412 KB |
Output is correct |
71 |
Correct |
446 ms |
56484 KB |
Output is correct |
72 |
Correct |
406 ms |
56488 KB |
Output is correct |
73 |
Correct |
691 ms |
57688 KB |
Output is correct |
74 |
Correct |
549 ms |
56540 KB |
Output is correct |
75 |
Correct |
607 ms |
56972 KB |
Output is correct |
76 |
Correct |
869 ms |
61276 KB |
Output is correct |
77 |
Correct |
517 ms |
51284 KB |
Output is correct |
78 |
Correct |
699 ms |
58464 KB |
Output is correct |
79 |
Correct |
775 ms |
59384 KB |
Output is correct |
80 |
Correct |
908 ms |
61264 KB |
Output is correct |
81 |
Correct |
279 ms |
48848 KB |
Output is correct |
82 |
Correct |
621 ms |
56604 KB |
Output is correct |
83 |
Correct |
568 ms |
55880 KB |
Output is correct |
84 |
Correct |
796 ms |
61248 KB |
Output is correct |
85 |
Correct |
640 ms |
56488 KB |
Output is correct |
86 |
Correct |
715 ms |
60016 KB |
Output is correct |
87 |
Correct |
506 ms |
56396 KB |
Output is correct |
88 |
Correct |
734 ms |
60016 KB |
Output is correct |
89 |
Correct |
752 ms |
58060 KB |
Output is correct |
90 |
Correct |
890 ms |
60024 KB |
Output is correct |
91 |
Correct |
530 ms |
56388 KB |
Output is correct |
92 |
Correct |
760 ms |
60192 KB |
Output is correct |
93 |
Correct |
429 ms |
56580 KB |
Output is correct |
94 |
Correct |
714 ms |
60084 KB |
Output is correct |
95 |
Correct |
523 ms |
56528 KB |
Output is correct |
96 |
Correct |
778 ms |
60108 KB |
Output is correct |