#include<bits/stdc++.h>
using namespace std;
typedef long long llint;
typedef pair <int, int> pi;
const int MAXN = 200005;
const llint INF = 1000000000000000000LL;
int n, q, ofs = 1;
int h[MAXN], a[MAXN], b[MAXN], res[MAXN];
vector <int> v[MAXN];
vector <pi> r[MAXN];
struct node {
llint sol, mn, mx, prop_mn, prop_mx;
node () {
sol = -1;
mn = prop_mn = INF;
mx = prop_mx = -INF;
}
node (llint _sol, llint _mn, llint _mx, llint _prop_mn, llint _prop_mx) {
sol = _sol; mn = _mn; mx = _mx; prop_mn = _prop_mn, prop_mx = _prop_mx;
}
} t[MAXN * 4];
void propagate (int x) {
if (x < ofs) {
t[2 * x].prop_mn = min(t[2 * x].prop_mn, t[x].prop_mn);
t[2 * x].prop_mx = max(t[2 * x].prop_mx, t[x].prop_mx);
t[2 * x + 1].prop_mn = min(t[2 * x + 1].prop_mn, t[x].prop_mn);
t[2 * x + 1].prop_mx = max(t[2 * x + 1].prop_mx, t[x].prop_mx);
}
if (t[x].prop_mn <= t[x].mx) t[x].sol = max(t[x].sol, t[x].mx - t[x].prop_mn);
if (t[x].mn <= t[x].prop_mx) t[x].sol = max(t[x].sol, t[x].prop_mx - t[x].mn);
t[x].prop_mn = INF;
t[x].prop_mx = -INF;
}
node spoji (node x, node y) {
return node(max(x.sol, y.sol), min(x.mn, y.mn), max(x.mx, y.mx), min(x.prop_mn, y.prop_mn), max(x.prop_mx, y.prop_mx));
}
void update_prop (int x, int from, int to, int lo, int hi, llint val) {
propagate(x);
if (from <= lo && hi <= to) {
t[x].prop_mn = min(t[x].prop_mn, val);
t[x].prop_mx = max(t[x].prop_mx, val);
propagate(x);
return;
}
if (to < lo || hi < from) return;
update_prop(2 * x, from, to, lo, (lo + hi) / 2, val);
update_prop(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi, val);
t[x] = spoji(t[2 * x], t[2 * x + 1]);
}
void update_akt (int x, int pos, int lo, int hi, llint val) {
propagate(x);
if (pos == lo && pos == hi) {
if (val == 0) {
t[x].mn = INF;
t[x].mx = -INF;
} else {
t[x].mn = min(t[x].mn, val);
t[x].mx = max(t[x].mx, val);
}
propagate(x);
return;
}
if (pos < lo || hi < pos) return;
update_akt(2 * x, pos, lo, (lo + hi) / 2, val);
update_akt(2 * x + 1, pos, (lo + hi) / 2 + 1, hi, val);
t[x] = spoji(t[2 * x], t[2 * x + 1]);
}
llint upit (int x, int from, int to, int lo, int hi) {
propagate(x);
if (from <= lo && hi <= to) return t[x].sol;
if (to < lo || hi < from) return -1;
return max(upit(2 * x, from, to, lo, (lo + hi) / 2), upit(2 * x + 1, from, to, (lo + hi) / 2 + 1, hi));
}
void sweep () {
for (int i = 1; i <= n; i++) {
int lo = i + a[i], hi = i + b[i];
if (lo <= n) v[lo].push_back(i);
if (hi + 1 <= n) v[hi + 1].push_back(-i);
}
for (int i = 1; i <= n; i++) {
for (auto x : v[i]) {
if (x > 0) {
update_akt(1, x, 0, ofs - 1, h[x]);
} else {
update_akt(1, -x, 0, ofs - 1, 0);
}
}
int lo = i - b[i], hi = i - a[i];
if (1 <= hi) {
lo = max(lo, 1);
update_prop(1, lo, hi, 0, ofs - 1, h[i]);
}
for (auto par : r[i]) {
int lef = par.first, ind = par.second;
res[ind] = upit(1, lef, i, 0, ofs - 1);
}
}
}
int main () {
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n;
while (ofs < n + 1) ofs *= 2;
for (int i = 1; i <= n; i++) {
cin >> h[i] >> a[i] >> b[i];
}
cin >> q;
for (int i = 1; i <= q; i++) {
int a, b;
cin >> a >> b;
r[b].push_back({a, i});
}
sweep();
for (int i = 1; i <= q; i++) {
cout << res[i] << '\n';
}
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
41080 KB |
Output is correct |
2 |
Correct |
22 ms |
41088 KB |
Output is correct |
3 |
Correct |
22 ms |
41088 KB |
Output is correct |
4 |
Correct |
22 ms |
41088 KB |
Output is correct |
5 |
Correct |
23 ms |
41088 KB |
Output is correct |
6 |
Correct |
25 ms |
41080 KB |
Output is correct |
7 |
Correct |
22 ms |
41080 KB |
Output is correct |
8 |
Correct |
26 ms |
41088 KB |
Output is correct |
9 |
Correct |
24 ms |
41088 KB |
Output is correct |
10 |
Correct |
22 ms |
41220 KB |
Output is correct |
11 |
Correct |
22 ms |
41088 KB |
Output is correct |
12 |
Correct |
26 ms |
41088 KB |
Output is correct |
13 |
Correct |
23 ms |
41088 KB |
Output is correct |
14 |
Correct |
22 ms |
41088 KB |
Output is correct |
15 |
Correct |
22 ms |
41088 KB |
Output is correct |
16 |
Correct |
25 ms |
41088 KB |
Output is correct |
17 |
Correct |
28 ms |
41088 KB |
Output is correct |
18 |
Correct |
28 ms |
41080 KB |
Output is correct |
19 |
Correct |
22 ms |
41088 KB |
Output is correct |
20 |
Correct |
22 ms |
41088 KB |
Output is correct |
21 |
Correct |
24 ms |
41080 KB |
Output is correct |
22 |
Correct |
26 ms |
41088 KB |
Output is correct |
23 |
Correct |
23 ms |
41088 KB |
Output is correct |
24 |
Correct |
24 ms |
41088 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
41080 KB |
Output is correct |
2 |
Correct |
22 ms |
41088 KB |
Output is correct |
3 |
Correct |
22 ms |
41088 KB |
Output is correct |
4 |
Correct |
22 ms |
41088 KB |
Output is correct |
5 |
Correct |
23 ms |
41088 KB |
Output is correct |
6 |
Correct |
25 ms |
41080 KB |
Output is correct |
7 |
Correct |
22 ms |
41080 KB |
Output is correct |
8 |
Correct |
26 ms |
41088 KB |
Output is correct |
9 |
Correct |
24 ms |
41088 KB |
Output is correct |
10 |
Correct |
22 ms |
41220 KB |
Output is correct |
11 |
Correct |
22 ms |
41088 KB |
Output is correct |
12 |
Correct |
26 ms |
41088 KB |
Output is correct |
13 |
Correct |
23 ms |
41088 KB |
Output is correct |
14 |
Correct |
22 ms |
41088 KB |
Output is correct |
15 |
Correct |
22 ms |
41088 KB |
Output is correct |
16 |
Correct |
25 ms |
41088 KB |
Output is correct |
17 |
Correct |
28 ms |
41088 KB |
Output is correct |
18 |
Correct |
28 ms |
41080 KB |
Output is correct |
19 |
Correct |
22 ms |
41088 KB |
Output is correct |
20 |
Correct |
22 ms |
41088 KB |
Output is correct |
21 |
Correct |
24 ms |
41080 KB |
Output is correct |
22 |
Correct |
26 ms |
41088 KB |
Output is correct |
23 |
Correct |
23 ms |
41088 KB |
Output is correct |
24 |
Correct |
24 ms |
41088 KB |
Output is correct |
25 |
Correct |
134 ms |
45808 KB |
Output is correct |
26 |
Correct |
39 ms |
41720 KB |
Output is correct |
27 |
Correct |
183 ms |
47736 KB |
Output is correct |
28 |
Correct |
195 ms |
47864 KB |
Output is correct |
29 |
Correct |
133 ms |
45816 KB |
Output is correct |
30 |
Correct |
143 ms |
45560 KB |
Output is correct |
31 |
Correct |
169 ms |
46968 KB |
Output is correct |
32 |
Correct |
208 ms |
47828 KB |
Output is correct |
33 |
Correct |
182 ms |
47352 KB |
Output is correct |
34 |
Correct |
108 ms |
44424 KB |
Output is correct |
35 |
Correct |
180 ms |
47736 KB |
Output is correct |
36 |
Correct |
183 ms |
47864 KB |
Output is correct |
37 |
Correct |
112 ms |
44412 KB |
Output is correct |
38 |
Correct |
192 ms |
46840 KB |
Output is correct |
39 |
Correct |
53 ms |
41976 KB |
Output is correct |
40 |
Correct |
178 ms |
46840 KB |
Output is correct |
41 |
Correct |
140 ms |
45304 KB |
Output is correct |
42 |
Correct |
183 ms |
46840 KB |
Output is correct |
43 |
Correct |
98 ms |
43092 KB |
Output is correct |
44 |
Correct |
181 ms |
46972 KB |
Output is correct |
45 |
Correct |
51 ms |
42104 KB |
Output is correct |
46 |
Correct |
216 ms |
46972 KB |
Output is correct |
47 |
Correct |
63 ms |
42616 KB |
Output is correct |
48 |
Correct |
182 ms |
46968 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
479 ms |
45880 KB |
Output is correct |
2 |
Correct |
481 ms |
50812 KB |
Output is correct |
3 |
Correct |
342 ms |
47992 KB |
Output is correct |
4 |
Correct |
550 ms |
50936 KB |
Output is correct |
5 |
Correct |
211 ms |
45560 KB |
Output is correct |
6 |
Correct |
511 ms |
50808 KB |
Output is correct |
7 |
Correct |
436 ms |
49528 KB |
Output is correct |
8 |
Correct |
514 ms |
50808 KB |
Output is correct |
9 |
Correct |
78 ms |
42616 KB |
Output is correct |
10 |
Correct |
570 ms |
50884 KB |
Output is correct |
11 |
Correct |
270 ms |
47224 KB |
Output is correct |
12 |
Correct |
565 ms |
50936 KB |
Output is correct |
13 |
Correct |
370 ms |
49024 KB |
Output is correct |
14 |
Correct |
350 ms |
48760 KB |
Output is correct |
15 |
Correct |
328 ms |
48984 KB |
Output is correct |
16 |
Correct |
356 ms |
49376 KB |
Output is correct |
17 |
Correct |
385 ms |
49108 KB |
Output is correct |
18 |
Correct |
350 ms |
49400 KB |
Output is correct |
19 |
Correct |
346 ms |
48880 KB |
Output is correct |
20 |
Correct |
336 ms |
48824 KB |
Output is correct |
21 |
Correct |
344 ms |
48628 KB |
Output is correct |
22 |
Correct |
341 ms |
48944 KB |
Output is correct |
23 |
Correct |
349 ms |
48884 KB |
Output is correct |
24 |
Correct |
363 ms |
48884 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
22 ms |
41080 KB |
Output is correct |
2 |
Correct |
22 ms |
41088 KB |
Output is correct |
3 |
Correct |
22 ms |
41088 KB |
Output is correct |
4 |
Correct |
22 ms |
41088 KB |
Output is correct |
5 |
Correct |
23 ms |
41088 KB |
Output is correct |
6 |
Correct |
25 ms |
41080 KB |
Output is correct |
7 |
Correct |
22 ms |
41080 KB |
Output is correct |
8 |
Correct |
26 ms |
41088 KB |
Output is correct |
9 |
Correct |
24 ms |
41088 KB |
Output is correct |
10 |
Correct |
22 ms |
41220 KB |
Output is correct |
11 |
Correct |
22 ms |
41088 KB |
Output is correct |
12 |
Correct |
26 ms |
41088 KB |
Output is correct |
13 |
Correct |
23 ms |
41088 KB |
Output is correct |
14 |
Correct |
22 ms |
41088 KB |
Output is correct |
15 |
Correct |
22 ms |
41088 KB |
Output is correct |
16 |
Correct |
25 ms |
41088 KB |
Output is correct |
17 |
Correct |
28 ms |
41088 KB |
Output is correct |
18 |
Correct |
28 ms |
41080 KB |
Output is correct |
19 |
Correct |
22 ms |
41088 KB |
Output is correct |
20 |
Correct |
22 ms |
41088 KB |
Output is correct |
21 |
Correct |
24 ms |
41080 KB |
Output is correct |
22 |
Correct |
26 ms |
41088 KB |
Output is correct |
23 |
Correct |
23 ms |
41088 KB |
Output is correct |
24 |
Correct |
24 ms |
41088 KB |
Output is correct |
25 |
Correct |
134 ms |
45808 KB |
Output is correct |
26 |
Correct |
39 ms |
41720 KB |
Output is correct |
27 |
Correct |
183 ms |
47736 KB |
Output is correct |
28 |
Correct |
195 ms |
47864 KB |
Output is correct |
29 |
Correct |
133 ms |
45816 KB |
Output is correct |
30 |
Correct |
143 ms |
45560 KB |
Output is correct |
31 |
Correct |
169 ms |
46968 KB |
Output is correct |
32 |
Correct |
208 ms |
47828 KB |
Output is correct |
33 |
Correct |
182 ms |
47352 KB |
Output is correct |
34 |
Correct |
108 ms |
44424 KB |
Output is correct |
35 |
Correct |
180 ms |
47736 KB |
Output is correct |
36 |
Correct |
183 ms |
47864 KB |
Output is correct |
37 |
Correct |
112 ms |
44412 KB |
Output is correct |
38 |
Correct |
192 ms |
46840 KB |
Output is correct |
39 |
Correct |
53 ms |
41976 KB |
Output is correct |
40 |
Correct |
178 ms |
46840 KB |
Output is correct |
41 |
Correct |
140 ms |
45304 KB |
Output is correct |
42 |
Correct |
183 ms |
46840 KB |
Output is correct |
43 |
Correct |
98 ms |
43092 KB |
Output is correct |
44 |
Correct |
181 ms |
46972 KB |
Output is correct |
45 |
Correct |
51 ms |
42104 KB |
Output is correct |
46 |
Correct |
216 ms |
46972 KB |
Output is correct |
47 |
Correct |
63 ms |
42616 KB |
Output is correct |
48 |
Correct |
182 ms |
46968 KB |
Output is correct |
49 |
Correct |
479 ms |
45880 KB |
Output is correct |
50 |
Correct |
481 ms |
50812 KB |
Output is correct |
51 |
Correct |
342 ms |
47992 KB |
Output is correct |
52 |
Correct |
550 ms |
50936 KB |
Output is correct |
53 |
Correct |
211 ms |
45560 KB |
Output is correct |
54 |
Correct |
511 ms |
50808 KB |
Output is correct |
55 |
Correct |
436 ms |
49528 KB |
Output is correct |
56 |
Correct |
514 ms |
50808 KB |
Output is correct |
57 |
Correct |
78 ms |
42616 KB |
Output is correct |
58 |
Correct |
570 ms |
50884 KB |
Output is correct |
59 |
Correct |
270 ms |
47224 KB |
Output is correct |
60 |
Correct |
565 ms |
50936 KB |
Output is correct |
61 |
Correct |
370 ms |
49024 KB |
Output is correct |
62 |
Correct |
350 ms |
48760 KB |
Output is correct |
63 |
Correct |
328 ms |
48984 KB |
Output is correct |
64 |
Correct |
356 ms |
49376 KB |
Output is correct |
65 |
Correct |
385 ms |
49108 KB |
Output is correct |
66 |
Correct |
350 ms |
49400 KB |
Output is correct |
67 |
Correct |
346 ms |
48880 KB |
Output is correct |
68 |
Correct |
336 ms |
48824 KB |
Output is correct |
69 |
Correct |
344 ms |
48628 KB |
Output is correct |
70 |
Correct |
341 ms |
48944 KB |
Output is correct |
71 |
Correct |
349 ms |
48884 KB |
Output is correct |
72 |
Correct |
363 ms |
48884 KB |
Output is correct |
73 |
Correct |
735 ms |
56952 KB |
Output is correct |
74 |
Correct |
566 ms |
51704 KB |
Output is correct |
75 |
Correct |
688 ms |
56568 KB |
Output is correct |
76 |
Correct |
908 ms |
59940 KB |
Output is correct |
77 |
Correct |
481 ms |
51704 KB |
Output is correct |
78 |
Correct |
818 ms |
57268 KB |
Output is correct |
79 |
Correct |
827 ms |
58468 KB |
Output is correct |
80 |
Correct |
862 ms |
60024 KB |
Output is correct |
81 |
Correct |
326 ms |
49912 KB |
Output is correct |
82 |
Correct |
667 ms |
55672 KB |
Output is correct |
83 |
Correct |
634 ms |
55672 KB |
Output is correct |
84 |
Correct |
876 ms |
59896 KB |
Output is correct |
85 |
Correct |
603 ms |
53696 KB |
Output is correct |
86 |
Correct |
782 ms |
56820 KB |
Output is correct |
87 |
Correct |
387 ms |
50296 KB |
Output is correct |
88 |
Correct |
715 ms |
57400 KB |
Output is correct |
89 |
Correct |
664 ms |
55156 KB |
Output is correct |
90 |
Correct |
757 ms |
57320 KB |
Output is correct |
91 |
Correct |
479 ms |
51840 KB |
Output is correct |
92 |
Correct |
701 ms |
56820 KB |
Output is correct |
93 |
Correct |
415 ms |
50260 KB |
Output is correct |
94 |
Correct |
717 ms |
56896 KB |
Output is correct |
95 |
Correct |
453 ms |
51184 KB |
Output is correct |
96 |
Correct |
752 ms |
56924 KB |
Output is correct |