#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
typedef long double ld;
#define fastInp cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
const ll SZ = 200'100, INF = 2'000'000'000;
struct tow {
ll h, a, b;
};
struct qs{
ll l, r, ind;
};
vector<tow> vec;
vector<qs> queries[SZ];
ll n, q;
ll pushmx[SZ * 8], pushmn[SZ * 8], opt[SZ * 4], mx[SZ * 4], mn[SZ * 4];
void push(int v) {
opt[v] = max(opt[v], pushmx[v] - mn[v]);
opt[v] = max(opt[v], mx[v] - pushmn[v]);
pushmx[v * 2 + 1] = max(pushmx[v * 2 + 1], pushmx[v]);
pushmx[v * 2 + 2] = max(pushmx[v * 2 + 2], pushmx[v]);
pushmn[v * 2 + 1] = min(pushmn[v * 2 + 1], pushmn[v]);
pushmn[v * 2 + 2] = min(pushmn[v * 2 + 2], pushmn[v]);
pushmx[v] = -INF;
pushmn[v] = INF;
}
void toggle(int v, int l, int r, int pos) {
push(v);
if (l == r - 1) {
if (mx[v] == -INF) {
mx[v] = mn[v] = vec[l].h;
} else {
mx[v] = -INF;
mn[v] = INF;
}
} else {
push(v * 2 + 1);
push(v * 2 + 2);
int mid = (l + r) / 2;
if (pos < mid) {
toggle(v * 2 + 1, l, mid, pos);
} else {
toggle(v * 2 + 2, mid, r, pos);
}
mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
mn[v] = min(mn[v * 2 + 1], mn[v * 2 + 2]);
opt[v] = max(opt[v * 2 + 1], opt[v * 2 + 2]);
}
}
ll ask(int v, int l, int r, int askl, int askr) {
push(v);
if (l >= askr || r <= askl) return -1;
if (askl <= l && r <= askr) {
return opt[v];
}
int mid = (l + r) / 2;
return max(ask(v * 2 + 1, l, mid, askl, askr), ask(v * 2 + 2, mid, r, askl, askr));
}
void upd(int v, int l, int r, int askl, int askr, ll val) {
push(v);
if (l >= askr || r <= askl) return;
if (askl <= l && r <= askr) {
pushmn[v] = min(pushmn[v], val);
pushmx[v] = max(pushmx[v], val);
push(v);
return;
}
int mid = (l + r) / 2;
upd(v * 2 + 1, l, mid, askl, askr, val);
upd(v * 2 + 2, mid, r, askl, askr, val);
push(v * 2 + 1);
push(v * 2 + 2);
mx[v] = max(mx[v * 2 + 1], mx[v * 2 + 2]);
mn[v] = min(mn[v * 2 + 1], mn[v * 2 + 2]);
opt[v] = max(opt[v * 2 + 1], opt[v * 2 + 2]);
}
vector<ll> togler[SZ * 2 + 100];
int main() {
fastInp;
cin >> n;
vec.resize(n);
for (auto &c : vec) cin >> c.h >> c.a >> c.b;
cin >> q;
for (int i = 0; i < q; i++) {
ll l, r;
cin >> l >> r;
l--; r--;
queries[r].push_back({l, r, i});
}
for (int i = 0; i < SZ * 8; i++) {
pushmx[i] = -INF;
pushmn[i] = INF;
}
for (int i = 0; i < SZ * 4; i++) {
opt[i] = -1;
mx[i] = -INF;
mn[i] = INF;
}
vector<ll> ans(q);
for (int i = 0; i < n; i++) {
for (auto c : togler[i]) {
toggle(0, 0, n, c);
}
ll l = i - vec[i].b, r = i - vec[i].a;
l = max(l, 0ll);
upd(0, 0, n, l, r + 1, vec[i].h);
for (auto c : queries[i]) {
ans[c.ind] = ask(0, 0, n, c.l, c.r + 1);
}
togler[i + vec[i].a].push_back(i);
togler[i + vec[i].b + 1].push_back(i);
}
for (auto c : ans) cout << c << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
58224 KB |
Output is correct |
2 |
Correct |
28 ms |
58188 KB |
Output is correct |
3 |
Correct |
30 ms |
58180 KB |
Output is correct |
4 |
Correct |
29 ms |
58236 KB |
Output is correct |
5 |
Correct |
28 ms |
58264 KB |
Output is correct |
6 |
Correct |
26 ms |
58196 KB |
Output is correct |
7 |
Correct |
28 ms |
58324 KB |
Output is correct |
8 |
Correct |
29 ms |
58248 KB |
Output is correct |
9 |
Correct |
36 ms |
58272 KB |
Output is correct |
10 |
Correct |
31 ms |
58292 KB |
Output is correct |
11 |
Correct |
30 ms |
58196 KB |
Output is correct |
12 |
Correct |
28 ms |
58296 KB |
Output is correct |
13 |
Correct |
28 ms |
58212 KB |
Output is correct |
14 |
Correct |
29 ms |
58228 KB |
Output is correct |
15 |
Correct |
28 ms |
58208 KB |
Output is correct |
16 |
Correct |
28 ms |
58284 KB |
Output is correct |
17 |
Correct |
28 ms |
58292 KB |
Output is correct |
18 |
Correct |
33 ms |
58268 KB |
Output is correct |
19 |
Correct |
26 ms |
58260 KB |
Output is correct |
20 |
Correct |
35 ms |
58276 KB |
Output is correct |
21 |
Correct |
29 ms |
58240 KB |
Output is correct |
22 |
Correct |
28 ms |
58296 KB |
Output is correct |
23 |
Correct |
35 ms |
58264 KB |
Output is correct |
24 |
Correct |
28 ms |
58188 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
58224 KB |
Output is correct |
2 |
Correct |
28 ms |
58188 KB |
Output is correct |
3 |
Correct |
30 ms |
58180 KB |
Output is correct |
4 |
Correct |
29 ms |
58236 KB |
Output is correct |
5 |
Correct |
28 ms |
58264 KB |
Output is correct |
6 |
Correct |
26 ms |
58196 KB |
Output is correct |
7 |
Correct |
28 ms |
58324 KB |
Output is correct |
8 |
Correct |
29 ms |
58248 KB |
Output is correct |
9 |
Correct |
36 ms |
58272 KB |
Output is correct |
10 |
Correct |
31 ms |
58292 KB |
Output is correct |
11 |
Correct |
30 ms |
58196 KB |
Output is correct |
12 |
Correct |
28 ms |
58296 KB |
Output is correct |
13 |
Correct |
28 ms |
58212 KB |
Output is correct |
14 |
Correct |
29 ms |
58228 KB |
Output is correct |
15 |
Correct |
28 ms |
58208 KB |
Output is correct |
16 |
Correct |
28 ms |
58284 KB |
Output is correct |
17 |
Correct |
28 ms |
58292 KB |
Output is correct |
18 |
Correct |
33 ms |
58268 KB |
Output is correct |
19 |
Correct |
26 ms |
58260 KB |
Output is correct |
20 |
Correct |
35 ms |
58276 KB |
Output is correct |
21 |
Correct |
29 ms |
58240 KB |
Output is correct |
22 |
Correct |
28 ms |
58296 KB |
Output is correct |
23 |
Correct |
35 ms |
58264 KB |
Output is correct |
24 |
Correct |
28 ms |
58188 KB |
Output is correct |
25 |
Correct |
94 ms |
66828 KB |
Output is correct |
26 |
Correct |
40 ms |
59252 KB |
Output is correct |
27 |
Correct |
128 ms |
70504 KB |
Output is correct |
28 |
Correct |
128 ms |
70588 KB |
Output is correct |
29 |
Correct |
92 ms |
66908 KB |
Output is correct |
30 |
Correct |
96 ms |
66424 KB |
Output is correct |
31 |
Correct |
103 ms |
69084 KB |
Output is correct |
32 |
Correct |
126 ms |
70492 KB |
Output is correct |
33 |
Correct |
116 ms |
69600 KB |
Output is correct |
34 |
Correct |
93 ms |
64320 KB |
Output is correct |
35 |
Correct |
123 ms |
70292 KB |
Output is correct |
36 |
Correct |
125 ms |
70592 KB |
Output is correct |
37 |
Correct |
84 ms |
64864 KB |
Output is correct |
38 |
Correct |
133 ms |
69588 KB |
Output is correct |
39 |
Correct |
42 ms |
59832 KB |
Output is correct |
40 |
Correct |
125 ms |
69580 KB |
Output is correct |
41 |
Correct |
100 ms |
66548 KB |
Output is correct |
42 |
Correct |
125 ms |
69628 KB |
Output is correct |
43 |
Correct |
66 ms |
62124 KB |
Output is correct |
44 |
Correct |
125 ms |
69592 KB |
Output is correct |
45 |
Correct |
45 ms |
60236 KB |
Output is correct |
46 |
Correct |
125 ms |
69596 KB |
Output is correct |
47 |
Correct |
55 ms |
61188 KB |
Output is correct |
48 |
Correct |
131 ms |
69764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
374 ms |
73596 KB |
Output is correct |
2 |
Correct |
437 ms |
75452 KB |
Output is correct |
3 |
Correct |
276 ms |
70192 KB |
Output is correct |
4 |
Correct |
421 ms |
75296 KB |
Output is correct |
5 |
Correct |
163 ms |
66000 KB |
Output is correct |
6 |
Correct |
413 ms |
75316 KB |
Output is correct |
7 |
Correct |
374 ms |
72996 KB |
Output is correct |
8 |
Correct |
426 ms |
75296 KB |
Output is correct |
9 |
Correct |
66 ms |
60892 KB |
Output is correct |
10 |
Correct |
429 ms |
75292 KB |
Output is correct |
11 |
Correct |
239 ms |
68844 KB |
Output is correct |
12 |
Correct |
422 ms |
75292 KB |
Output is correct |
13 |
Correct |
256 ms |
72756 KB |
Output is correct |
14 |
Correct |
240 ms |
72660 KB |
Output is correct |
15 |
Correct |
233 ms |
73284 KB |
Output is correct |
16 |
Correct |
194 ms |
73880 KB |
Output is correct |
17 |
Correct |
256 ms |
72680 KB |
Output is correct |
18 |
Correct |
225 ms |
72976 KB |
Output is correct |
19 |
Correct |
242 ms |
72556 KB |
Output is correct |
20 |
Correct |
230 ms |
72664 KB |
Output is correct |
21 |
Correct |
225 ms |
72728 KB |
Output is correct |
22 |
Correct |
234 ms |
72916 KB |
Output is correct |
23 |
Correct |
236 ms |
72760 KB |
Output is correct |
24 |
Correct |
222 ms |
73508 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
28 ms |
58224 KB |
Output is correct |
2 |
Correct |
28 ms |
58188 KB |
Output is correct |
3 |
Correct |
30 ms |
58180 KB |
Output is correct |
4 |
Correct |
29 ms |
58236 KB |
Output is correct |
5 |
Correct |
28 ms |
58264 KB |
Output is correct |
6 |
Correct |
26 ms |
58196 KB |
Output is correct |
7 |
Correct |
28 ms |
58324 KB |
Output is correct |
8 |
Correct |
29 ms |
58248 KB |
Output is correct |
9 |
Correct |
36 ms |
58272 KB |
Output is correct |
10 |
Correct |
31 ms |
58292 KB |
Output is correct |
11 |
Correct |
30 ms |
58196 KB |
Output is correct |
12 |
Correct |
28 ms |
58296 KB |
Output is correct |
13 |
Correct |
28 ms |
58212 KB |
Output is correct |
14 |
Correct |
29 ms |
58228 KB |
Output is correct |
15 |
Correct |
28 ms |
58208 KB |
Output is correct |
16 |
Correct |
28 ms |
58284 KB |
Output is correct |
17 |
Correct |
28 ms |
58292 KB |
Output is correct |
18 |
Correct |
33 ms |
58268 KB |
Output is correct |
19 |
Correct |
26 ms |
58260 KB |
Output is correct |
20 |
Correct |
35 ms |
58276 KB |
Output is correct |
21 |
Correct |
29 ms |
58240 KB |
Output is correct |
22 |
Correct |
28 ms |
58296 KB |
Output is correct |
23 |
Correct |
35 ms |
58264 KB |
Output is correct |
24 |
Correct |
28 ms |
58188 KB |
Output is correct |
25 |
Correct |
94 ms |
66828 KB |
Output is correct |
26 |
Correct |
40 ms |
59252 KB |
Output is correct |
27 |
Correct |
128 ms |
70504 KB |
Output is correct |
28 |
Correct |
128 ms |
70588 KB |
Output is correct |
29 |
Correct |
92 ms |
66908 KB |
Output is correct |
30 |
Correct |
96 ms |
66424 KB |
Output is correct |
31 |
Correct |
103 ms |
69084 KB |
Output is correct |
32 |
Correct |
126 ms |
70492 KB |
Output is correct |
33 |
Correct |
116 ms |
69600 KB |
Output is correct |
34 |
Correct |
93 ms |
64320 KB |
Output is correct |
35 |
Correct |
123 ms |
70292 KB |
Output is correct |
36 |
Correct |
125 ms |
70592 KB |
Output is correct |
37 |
Correct |
84 ms |
64864 KB |
Output is correct |
38 |
Correct |
133 ms |
69588 KB |
Output is correct |
39 |
Correct |
42 ms |
59832 KB |
Output is correct |
40 |
Correct |
125 ms |
69580 KB |
Output is correct |
41 |
Correct |
100 ms |
66548 KB |
Output is correct |
42 |
Correct |
125 ms |
69628 KB |
Output is correct |
43 |
Correct |
66 ms |
62124 KB |
Output is correct |
44 |
Correct |
125 ms |
69592 KB |
Output is correct |
45 |
Correct |
45 ms |
60236 KB |
Output is correct |
46 |
Correct |
125 ms |
69596 KB |
Output is correct |
47 |
Correct |
55 ms |
61188 KB |
Output is correct |
48 |
Correct |
131 ms |
69764 KB |
Output is correct |
49 |
Correct |
374 ms |
73596 KB |
Output is correct |
50 |
Correct |
437 ms |
75452 KB |
Output is correct |
51 |
Correct |
276 ms |
70192 KB |
Output is correct |
52 |
Correct |
421 ms |
75296 KB |
Output is correct |
53 |
Correct |
163 ms |
66000 KB |
Output is correct |
54 |
Correct |
413 ms |
75316 KB |
Output is correct |
55 |
Correct |
374 ms |
72996 KB |
Output is correct |
56 |
Correct |
426 ms |
75296 KB |
Output is correct |
57 |
Correct |
66 ms |
60892 KB |
Output is correct |
58 |
Correct |
429 ms |
75292 KB |
Output is correct |
59 |
Correct |
239 ms |
68844 KB |
Output is correct |
60 |
Correct |
422 ms |
75292 KB |
Output is correct |
61 |
Correct |
256 ms |
72756 KB |
Output is correct |
62 |
Correct |
240 ms |
72660 KB |
Output is correct |
63 |
Correct |
233 ms |
73284 KB |
Output is correct |
64 |
Correct |
194 ms |
73880 KB |
Output is correct |
65 |
Correct |
256 ms |
72680 KB |
Output is correct |
66 |
Correct |
225 ms |
72976 KB |
Output is correct |
67 |
Correct |
242 ms |
72556 KB |
Output is correct |
68 |
Correct |
230 ms |
72664 KB |
Output is correct |
69 |
Correct |
225 ms |
72728 KB |
Output is correct |
70 |
Correct |
234 ms |
72916 KB |
Output is correct |
71 |
Correct |
236 ms |
72760 KB |
Output is correct |
72 |
Correct |
222 ms |
73508 KB |
Output is correct |
73 |
Correct |
597 ms |
83144 KB |
Output is correct |
74 |
Correct |
527 ms |
76300 KB |
Output is correct |
75 |
Correct |
560 ms |
82776 KB |
Output is correct |
76 |
Correct |
714 ms |
87956 KB |
Output is correct |
77 |
Correct |
351 ms |
75208 KB |
Output is correct |
78 |
Correct |
651 ms |
83668 KB |
Output is correct |
79 |
Correct |
687 ms |
85660 KB |
Output is correct |
80 |
Correct |
691 ms |
88040 KB |
Output is correct |
81 |
Correct |
203 ms |
72916 KB |
Output is correct |
82 |
Correct |
540 ms |
81328 KB |
Output is correct |
83 |
Correct |
441 ms |
81528 KB |
Output is correct |
84 |
Correct |
695 ms |
87992 KB |
Output is correct |
85 |
Correct |
424 ms |
79264 KB |
Output is correct |
86 |
Correct |
483 ms |
84068 KB |
Output is correct |
87 |
Correct |
276 ms |
74896 KB |
Output is correct |
88 |
Correct |
464 ms |
85276 KB |
Output is correct |
89 |
Correct |
454 ms |
81060 KB |
Output is correct |
90 |
Correct |
499 ms |
84472 KB |
Output is correct |
91 |
Correct |
335 ms |
76248 KB |
Output is correct |
92 |
Correct |
492 ms |
84116 KB |
Output is correct |
93 |
Correct |
268 ms |
74624 KB |
Output is correct |
94 |
Correct |
502 ms |
84476 KB |
Output is correct |
95 |
Correct |
322 ms |
75636 KB |
Output is correct |
96 |
Correct |
476 ms |
84936 KB |
Output is correct |