#include <bits/stdc++.h>
using namespace std;
#ifdef MIKU
string dbmc = "\033[1;38;2;57;197;187m", dbrs = "\033[0m";
#define debug(x...) cout << dbmc << "[" << #x << "]: ", dout(x)
void dout() { cout << dbrs << endl; }
template <typename T, typename ...U>
void dout(T t, U ...u) { cout << t << (sizeof...(u) ? ", " : ""); dout(u...); }
#else
#define debug(...) 39
#endif
#define fs first
#define sc second
#define mp make_pair
#define FOR(i, j, k) for (int i = j, Z = k; i < Z; i++)
using ll = long long;
typedef pair<int, int> pii;
const int MXN = 200005, INF = 1e9 + 39;
int n, q;
struct IN {
int h, a, b;
} in[MXN];
struct QRY {
int l, r, id;
} qry[MXN];
vector<pii> bck[MXN];
int ans[MXN];
struct LOSTONE {
#define mid ((l + r) >> 1)
#define ls id * 2 + 1
#define rs id * 2 + 2
int val[MXN * 4], c[MXN * 4], tag[MXN * 4];
void add_tag(int id, int l, int r, int _t) {
val[id] = max(val[id], c[id] - _t);
tag[id] = min(tag[id], _t);
}
void push(int id, int l, int r) {
if (tag[id] == INF) return;
add_tag(ls, l, mid, tag[id]);
add_tag(rs, mid, r, tag[id]);
tag[id] = INF;
}
void pull(int id, int l, int r) {
c[id] = max(c[ls], c[rs]);
val[id] = max(val[ls], val[rs]);
}
void init(int n) {
fill(val, val + n * 4, -1);
fill(tag, tag + n * 4, INF);
fill(c, c + n * 4, -INF);
}
void grade(int id, int l, int r, int p, int _c) {
if (l + 1 == r) {
c[id] = _c;
return;
}
push(id, l, r);
if (p < mid) grade(ls, l, mid, p, _c);
else grade(rs, mid, r, p, _c);
pull(id, l, r);
}
void test(int id, int l, int r, int _l, int _r, int _h) {
if (_l == _r) return;
if (_r <= l || r <= _l) return;
if (_l <= l && r <= _r) {
add_tag(id, l, r, _h);
return;
}
push(id, l, r);
test(ls, l, mid, _l, _r, _h);
test(rs, mid, r, _l, _r, _h);
pull(id, l, r);
}
int query(int id, int l, int r, int _l, int _r) {
if (_r <= l || r <= _l) return -1;
if (_l <= l && r <= _r) return val[id];
push(id, l, r);
return max(query(ls, l, mid, _l, _r), query(rs, mid, r, _l, _r));
}
#undef mid
#undef ls
#undef rs
} GOUKOKU;
void solve() {
GOUKOKU.init(n);
#define abb(t, p) if (t <= n) bck[t].push_back(p)
FOR(i, 0, n) {
abb(i + in[i].a, mp(3, i));
abb(i + in[i].b + 1, mp(3, -i - 1));
}
FOR(i, 0, q) {
abb(qry[i].r, mp(2, i));
}
#undef abb
FOR(r, 0, n + 1) {
for (auto [t, id] : bck[r]) {
if (t == 3) {
if (id >= 0) {
GOUKOKU.grade(0, 0, n, id, in[id].h);
} else {
id = -id - 1;
GOUKOKU.grade(0, 0, n, id, -INF);
}
} else {
auto [l, _, aid] = qry[id];
int x = GOUKOKU.query(0, 0, n, l, r);
ans[aid] = max(ans[aid], x);
}
}
#define abb(x) max(0, x)
if (r < n) {
GOUKOKU.test(0, 0, n, abb(r - in[r].b), abb(r - in[r].a + 1), in[r].h);
}
#undef abb
bck[r].clear();
}
}
void REVERSE() {
reverse(in, in + n);
FOR(i, 0, q) {
qry[i].l = n - qry[i].l;
qry[i].r = n - qry[i].r;
swap(qry[i].l, qry[i].r);
}
}
void miku() {
cin >> n;
FOR(i, 0, n) cin >> in[i].h >> in[i].a >> in[i].b;
cin >> q;
FOR(i, 0, q) {
cin >> qry[i].l >> qry[i].r;
qry[i].l--;
qry[i].id = i;
}
fill(ans, ans + q, -1);
solve();
REVERSE();
solve();
FOR(i, 0, q) cout << ans[i] << '\n';
}
int32_t main() {
cin.tie(0) -> sync_with_stdio(false);
cin.exceptions(cin.failbit);
miku();
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14684 KB |
Output is correct |
2 |
Correct |
3 ms |
14684 KB |
Output is correct |
3 |
Correct |
4 ms |
14684 KB |
Output is correct |
4 |
Correct |
3 ms |
14684 KB |
Output is correct |
5 |
Correct |
3 ms |
14684 KB |
Output is correct |
6 |
Correct |
3 ms |
14684 KB |
Output is correct |
7 |
Correct |
3 ms |
14684 KB |
Output is correct |
8 |
Correct |
3 ms |
14772 KB |
Output is correct |
9 |
Correct |
2 ms |
14684 KB |
Output is correct |
10 |
Correct |
2 ms |
14684 KB |
Output is correct |
11 |
Correct |
3 ms |
14684 KB |
Output is correct |
12 |
Correct |
3 ms |
14684 KB |
Output is correct |
13 |
Correct |
3 ms |
14684 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
3 ms |
14684 KB |
Output is correct |
16 |
Correct |
4 ms |
14744 KB |
Output is correct |
17 |
Correct |
3 ms |
14848 KB |
Output is correct |
18 |
Correct |
3 ms |
14680 KB |
Output is correct |
19 |
Correct |
2 ms |
14680 KB |
Output is correct |
20 |
Correct |
3 ms |
14684 KB |
Output is correct |
21 |
Correct |
3 ms |
14684 KB |
Output is correct |
22 |
Correct |
3 ms |
14684 KB |
Output is correct |
23 |
Correct |
2 ms |
14684 KB |
Output is correct |
24 |
Correct |
2 ms |
14680 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14684 KB |
Output is correct |
2 |
Correct |
3 ms |
14684 KB |
Output is correct |
3 |
Correct |
4 ms |
14684 KB |
Output is correct |
4 |
Correct |
3 ms |
14684 KB |
Output is correct |
5 |
Correct |
3 ms |
14684 KB |
Output is correct |
6 |
Correct |
3 ms |
14684 KB |
Output is correct |
7 |
Correct |
3 ms |
14684 KB |
Output is correct |
8 |
Correct |
3 ms |
14772 KB |
Output is correct |
9 |
Correct |
2 ms |
14684 KB |
Output is correct |
10 |
Correct |
2 ms |
14684 KB |
Output is correct |
11 |
Correct |
3 ms |
14684 KB |
Output is correct |
12 |
Correct |
3 ms |
14684 KB |
Output is correct |
13 |
Correct |
3 ms |
14684 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
3 ms |
14684 KB |
Output is correct |
16 |
Correct |
4 ms |
14744 KB |
Output is correct |
17 |
Correct |
3 ms |
14848 KB |
Output is correct |
18 |
Correct |
3 ms |
14680 KB |
Output is correct |
19 |
Correct |
2 ms |
14680 KB |
Output is correct |
20 |
Correct |
3 ms |
14684 KB |
Output is correct |
21 |
Correct |
3 ms |
14684 KB |
Output is correct |
22 |
Correct |
3 ms |
14684 KB |
Output is correct |
23 |
Correct |
2 ms |
14684 KB |
Output is correct |
24 |
Correct |
2 ms |
14680 KB |
Output is correct |
25 |
Correct |
66 ms |
18516 KB |
Output is correct |
26 |
Correct |
11 ms |
15196 KB |
Output is correct |
27 |
Correct |
97 ms |
19676 KB |
Output is correct |
28 |
Correct |
102 ms |
19664 KB |
Output is correct |
29 |
Correct |
74 ms |
18488 KB |
Output is correct |
30 |
Correct |
68 ms |
18320 KB |
Output is correct |
31 |
Correct |
74 ms |
19164 KB |
Output is correct |
32 |
Correct |
99 ms |
19700 KB |
Output is correct |
33 |
Correct |
89 ms |
19796 KB |
Output is correct |
34 |
Correct |
51 ms |
17164 KB |
Output is correct |
35 |
Correct |
95 ms |
20052 KB |
Output is correct |
36 |
Correct |
103 ms |
19536 KB |
Output is correct |
37 |
Correct |
69 ms |
17048 KB |
Output is correct |
38 |
Correct |
97 ms |
18516 KB |
Output is correct |
39 |
Correct |
18 ms |
15452 KB |
Output is correct |
40 |
Correct |
95 ms |
18612 KB |
Output is correct |
41 |
Correct |
71 ms |
18000 KB |
Output is correct |
42 |
Correct |
95 ms |
18704 KB |
Output is correct |
43 |
Correct |
35 ms |
16208 KB |
Output is correct |
44 |
Correct |
96 ms |
18616 KB |
Output is correct |
45 |
Correct |
20 ms |
15448 KB |
Output is correct |
46 |
Correct |
95 ms |
18772 KB |
Output is correct |
47 |
Correct |
27 ms |
15708 KB |
Output is correct |
48 |
Correct |
100 ms |
18660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
223 ms |
23924 KB |
Output is correct |
2 |
Correct |
234 ms |
24608 KB |
Output is correct |
3 |
Correct |
148 ms |
22356 KB |
Output is correct |
4 |
Correct |
226 ms |
24400 KB |
Output is correct |
5 |
Correct |
92 ms |
21204 KB |
Output is correct |
6 |
Correct |
213 ms |
24404 KB |
Output is correct |
7 |
Correct |
216 ms |
23888 KB |
Output is correct |
8 |
Correct |
215 ms |
24560 KB |
Output is correct |
9 |
Correct |
29 ms |
20056 KB |
Output is correct |
10 |
Correct |
305 ms |
24656 KB |
Output is correct |
11 |
Correct |
130 ms |
22024 KB |
Output is correct |
12 |
Correct |
213 ms |
24400 KB |
Output is correct |
13 |
Correct |
148 ms |
24788 KB |
Output is correct |
14 |
Correct |
144 ms |
24600 KB |
Output is correct |
15 |
Correct |
137 ms |
23836 KB |
Output is correct |
16 |
Correct |
134 ms |
24084 KB |
Output is correct |
17 |
Correct |
162 ms |
25416 KB |
Output is correct |
18 |
Correct |
142 ms |
24404 KB |
Output is correct |
19 |
Correct |
142 ms |
24268 KB |
Output is correct |
20 |
Correct |
143 ms |
24644 KB |
Output is correct |
21 |
Correct |
133 ms |
24908 KB |
Output is correct |
22 |
Correct |
144 ms |
24652 KB |
Output is correct |
23 |
Correct |
149 ms |
24532 KB |
Output is correct |
24 |
Correct |
124 ms |
23428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
14684 KB |
Output is correct |
2 |
Correct |
3 ms |
14684 KB |
Output is correct |
3 |
Correct |
4 ms |
14684 KB |
Output is correct |
4 |
Correct |
3 ms |
14684 KB |
Output is correct |
5 |
Correct |
3 ms |
14684 KB |
Output is correct |
6 |
Correct |
3 ms |
14684 KB |
Output is correct |
7 |
Correct |
3 ms |
14684 KB |
Output is correct |
8 |
Correct |
3 ms |
14772 KB |
Output is correct |
9 |
Correct |
2 ms |
14684 KB |
Output is correct |
10 |
Correct |
2 ms |
14684 KB |
Output is correct |
11 |
Correct |
3 ms |
14684 KB |
Output is correct |
12 |
Correct |
3 ms |
14684 KB |
Output is correct |
13 |
Correct |
3 ms |
14684 KB |
Output is correct |
14 |
Correct |
2 ms |
14684 KB |
Output is correct |
15 |
Correct |
3 ms |
14684 KB |
Output is correct |
16 |
Correct |
4 ms |
14744 KB |
Output is correct |
17 |
Correct |
3 ms |
14848 KB |
Output is correct |
18 |
Correct |
3 ms |
14680 KB |
Output is correct |
19 |
Correct |
2 ms |
14680 KB |
Output is correct |
20 |
Correct |
3 ms |
14684 KB |
Output is correct |
21 |
Correct |
3 ms |
14684 KB |
Output is correct |
22 |
Correct |
3 ms |
14684 KB |
Output is correct |
23 |
Correct |
2 ms |
14684 KB |
Output is correct |
24 |
Correct |
2 ms |
14680 KB |
Output is correct |
25 |
Correct |
66 ms |
18516 KB |
Output is correct |
26 |
Correct |
11 ms |
15196 KB |
Output is correct |
27 |
Correct |
97 ms |
19676 KB |
Output is correct |
28 |
Correct |
102 ms |
19664 KB |
Output is correct |
29 |
Correct |
74 ms |
18488 KB |
Output is correct |
30 |
Correct |
68 ms |
18320 KB |
Output is correct |
31 |
Correct |
74 ms |
19164 KB |
Output is correct |
32 |
Correct |
99 ms |
19700 KB |
Output is correct |
33 |
Correct |
89 ms |
19796 KB |
Output is correct |
34 |
Correct |
51 ms |
17164 KB |
Output is correct |
35 |
Correct |
95 ms |
20052 KB |
Output is correct |
36 |
Correct |
103 ms |
19536 KB |
Output is correct |
37 |
Correct |
69 ms |
17048 KB |
Output is correct |
38 |
Correct |
97 ms |
18516 KB |
Output is correct |
39 |
Correct |
18 ms |
15452 KB |
Output is correct |
40 |
Correct |
95 ms |
18612 KB |
Output is correct |
41 |
Correct |
71 ms |
18000 KB |
Output is correct |
42 |
Correct |
95 ms |
18704 KB |
Output is correct |
43 |
Correct |
35 ms |
16208 KB |
Output is correct |
44 |
Correct |
96 ms |
18616 KB |
Output is correct |
45 |
Correct |
20 ms |
15448 KB |
Output is correct |
46 |
Correct |
95 ms |
18772 KB |
Output is correct |
47 |
Correct |
27 ms |
15708 KB |
Output is correct |
48 |
Correct |
100 ms |
18660 KB |
Output is correct |
49 |
Correct |
223 ms |
23924 KB |
Output is correct |
50 |
Correct |
234 ms |
24608 KB |
Output is correct |
51 |
Correct |
148 ms |
22356 KB |
Output is correct |
52 |
Correct |
226 ms |
24400 KB |
Output is correct |
53 |
Correct |
92 ms |
21204 KB |
Output is correct |
54 |
Correct |
213 ms |
24404 KB |
Output is correct |
55 |
Correct |
216 ms |
23888 KB |
Output is correct |
56 |
Correct |
215 ms |
24560 KB |
Output is correct |
57 |
Correct |
29 ms |
20056 KB |
Output is correct |
58 |
Correct |
305 ms |
24656 KB |
Output is correct |
59 |
Correct |
130 ms |
22024 KB |
Output is correct |
60 |
Correct |
213 ms |
24400 KB |
Output is correct |
61 |
Correct |
148 ms |
24788 KB |
Output is correct |
62 |
Correct |
144 ms |
24600 KB |
Output is correct |
63 |
Correct |
137 ms |
23836 KB |
Output is correct |
64 |
Correct |
134 ms |
24084 KB |
Output is correct |
65 |
Correct |
162 ms |
25416 KB |
Output is correct |
66 |
Correct |
142 ms |
24404 KB |
Output is correct |
67 |
Correct |
142 ms |
24268 KB |
Output is correct |
68 |
Correct |
143 ms |
24644 KB |
Output is correct |
69 |
Correct |
133 ms |
24908 KB |
Output is correct |
70 |
Correct |
144 ms |
24652 KB |
Output is correct |
71 |
Correct |
149 ms |
24532 KB |
Output is correct |
72 |
Correct |
124 ms |
23428 KB |
Output is correct |
73 |
Correct |
370 ms |
27728 KB |
Output is correct |
74 |
Correct |
230 ms |
24916 KB |
Output is correct |
75 |
Correct |
338 ms |
27984 KB |
Output is correct |
76 |
Correct |
510 ms |
30036 KB |
Output is correct |
77 |
Correct |
216 ms |
25052 KB |
Output is correct |
78 |
Correct |
372 ms |
28240 KB |
Output is correct |
79 |
Correct |
401 ms |
29012 KB |
Output is correct |
80 |
Correct |
439 ms |
29980 KB |
Output is correct |
81 |
Correct |
200 ms |
24916 KB |
Output is correct |
82 |
Correct |
324 ms |
27096 KB |
Output is correct |
83 |
Correct |
354 ms |
27220 KB |
Output is correct |
84 |
Correct |
441 ms |
29856 KB |
Output is correct |
85 |
Correct |
263 ms |
28352 KB |
Output is correct |
86 |
Correct |
414 ms |
30464 KB |
Output is correct |
87 |
Correct |
166 ms |
25052 KB |
Output is correct |
88 |
Correct |
329 ms |
30104 KB |
Output is correct |
89 |
Correct |
311 ms |
29460 KB |
Output is correct |
90 |
Correct |
361 ms |
30456 KB |
Output is correct |
91 |
Correct |
218 ms |
27104 KB |
Output is correct |
92 |
Correct |
383 ms |
30544 KB |
Output is correct |
93 |
Correct |
174 ms |
26120 KB |
Output is correct |
94 |
Correct |
401 ms |
30296 KB |
Output is correct |
95 |
Correct |
202 ms |
26756 KB |
Output is correct |
96 |
Correct |
338 ms |
29868 KB |
Output is correct |