#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace std {
template <typename T> ostream &operator<<(ostream &out, const vector<T> &vec) {
out << "[";
for (int i = 0; i < (int)vec.size(); ++i) {
out << vec[i];
if (i + 1 < (int)vec.size())
out << ", ";
}
return out << "]";
}
} // namespace std
void dbg_out() { cout << endl; }
template <typename Head, typename... Tail> void dbg_out(Head H, Tail... T) {
cout << ' ' << H;
dbg_out(T...);
}
#ifdef DEBUG
#define dbg(...) cout << "(" << #__VA_ARGS__ << "):", dbg_out(__VA_ARGS__)
#else
#define dbg(...)
#endif
const int MAXN = 1e6;
const int INF = 1e18;
int iDeb[MAXN], iFin[MAXN];
int rangeMin[MAXN], rangeMax[MAXN];
int lazyMax[MAXN], lazyMin[MAXN];
int rangeSol[MAXN];
void pull(int node) {
rangeMin[node] = min(rangeMin[2 * node], rangeMin[2 * node + 1]);
rangeMax[node] = max(rangeMax[2 * node], rangeMax[2 * node + 1]);
rangeSol[node] = max(rangeSol[2 * node], rangeSol[2 * node + 1]);
}
void push(int node) {
if (lazyMax[node] > -INF) {
int h = lazyMax[node];
lazyMax[node] = -INF;
if (iDeb[node] != iFin[node]) {
lazyMax[2 * node] = max(lazyMax[2 * node], h);
lazyMax[2 * node + 1] = max(lazyMax[2 * node + 1], h);
}
rangeSol[node] = max(rangeSol[node], h - rangeMin[node]);
}
if (lazyMin[node] < INF) {
int h = lazyMin[node];
lazyMin[node] = INF;
if (iDeb[node] < iFin[node]) {
lazyMin[2 * node] = min(lazyMin[2 * node], h);
lazyMin[2 * node + 1] = min(lazyMin[2 * node + 1], h);
}
rangeSol[node] = max(rangeSol[node], rangeMax[node] - h);
}
}
void build(int node, int l, int r) {
iDeb[node] = l, iFin[node] = r;
rangeMin[node] = lazyMin[node] = INF, rangeMax[node] = lazyMax[node] = -INF;
rangeSol[node] = -INF;
if (l == r)
return;
build(2 * node, l, (l + r) / 2);
build(2 * node + 1, (l + r) / 2 + 1, r);
}
void update(int node, int pos, int x) {
push(node);
if (iDeb[node] > pos or iFin[node] < pos)
return;
if (iDeb[node] == iFin[node]) {
if (x == INF)
rangeMin[node] = x, rangeMax[node] = -x;
else
rangeMin[node] = rangeMax[node] = x;
return;
}
update(2 * node, pos, x);
update(2 * node + 1, pos, x);
pull(node);
}
void insert(int node, int l, int r, int x) {
push(node);
if (iDeb[node] > r or iFin[node] < l)
return;
if (iDeb[node] >= l and iFin[node] <= r) {
lazyMax[node] = lazyMin[node] = x;
push(node);
return;
}
insert(2 * node, l, r, x);
insert(2 * node + 1, l, r, x);
pull(node);
}
int query(int node, int l, int r) {
push(node);
if (iDeb[node] > r or iFin[node] < l)
return -INF;
if (iDeb[node] >= l and iFin[node] <= r)
return rangeSol[node];
return max(query(2 * node, l, r), query(2 * node + 1, l, r));
}
signed main(void) {
ios_base::sync_with_stdio(false);
cin.tie(0);
int N;
cin >> N;
vector<int> H(N), A(N), B(N);
for (int i = 0; i < N; ++i)
cin >> H[i] >> A[i] >> B[i];
vector<vector<int>> toInsert(N), toDel(N);
for (int i = 0; i < N; ++i) {
if (i - A[i] >= 0)
toInsert[i - A[i]].push_back(i);
if (i - B[i] > 0)
toDel[i - B[i] - 1].push_back(i);
}
build(1, 0, N - 1);
int Q;
cin >> Q;
vector<int> sol(Q);
vector<vector<pair<int, int>>> queries(N);
for (int i = 0; i < Q; ++i) {
int l, r;
cin >> l >> r;
--l, --r;
queries[l].emplace_back(r, i);
}
for (int i = N - 1; i >= 0; --i) {
dbg(i);
for (int j : toInsert[i]) {
dbg("insert", j);
update(1, j, H[j]);
}
for (int j : toDel[i]) {
dbg("del", j);
update(1, j, INF);
}
int lo = i + A[i], up = i + B[i];
if (lo < N) {
up = min(up, N - 1);
insert(1, lo, up, H[i]);
}
for (auto [r, j] : queries[i])
sol[j] = query(1, i, r);
dbg(rangeSol[1], rangeMax[1], rangeMin[1]);
}
for (int x : sol) {
x = max(-1LL, x);
cout << x << '\n';
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
336 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
336 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
81 ms |
7968 KB |
Output is correct |
26 |
Correct |
10 ms |
1660 KB |
Output is correct |
27 |
Correct |
107 ms |
10768 KB |
Output is correct |
28 |
Correct |
147 ms |
10572 KB |
Output is correct |
29 |
Correct |
89 ms |
8392 KB |
Output is correct |
30 |
Correct |
80 ms |
7960 KB |
Output is correct |
31 |
Correct |
91 ms |
9740 KB |
Output is correct |
32 |
Correct |
108 ms |
10380 KB |
Output is correct |
33 |
Correct |
93 ms |
10840 KB |
Output is correct |
34 |
Correct |
53 ms |
5520 KB |
Output is correct |
35 |
Correct |
127 ms |
11600 KB |
Output is correct |
36 |
Correct |
127 ms |
10396 KB |
Output is correct |
37 |
Correct |
56 ms |
5992 KB |
Output is correct |
38 |
Correct |
136 ms |
9440 KB |
Output is correct |
39 |
Correct |
16 ms |
2064 KB |
Output is correct |
40 |
Correct |
96 ms |
9364 KB |
Output is correct |
41 |
Correct |
87 ms |
7984 KB |
Output is correct |
42 |
Correct |
122 ms |
9372 KB |
Output is correct |
43 |
Correct |
46 ms |
3996 KB |
Output is correct |
44 |
Correct |
115 ms |
9404 KB |
Output is correct |
45 |
Correct |
20 ms |
2380 KB |
Output is correct |
46 |
Correct |
107 ms |
9352 KB |
Output is correct |
47 |
Correct |
28 ms |
3076 KB |
Output is correct |
48 |
Correct |
110 ms |
9368 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
335 ms |
49280 KB |
Output is correct |
2 |
Correct |
378 ms |
51528 KB |
Output is correct |
3 |
Correct |
297 ms |
44864 KB |
Output is correct |
4 |
Correct |
409 ms |
51560 KB |
Output is correct |
5 |
Correct |
147 ms |
25100 KB |
Output is correct |
6 |
Correct |
336 ms |
51528 KB |
Output is correct |
7 |
Correct |
271 ms |
48460 KB |
Output is correct |
8 |
Correct |
326 ms |
51652 KB |
Output is correct |
9 |
Correct |
37 ms |
7508 KB |
Output is correct |
10 |
Correct |
406 ms |
51548 KB |
Output is correct |
11 |
Correct |
202 ms |
28808 KB |
Output is correct |
12 |
Correct |
331 ms |
51404 KB |
Output is correct |
13 |
Correct |
171 ms |
51260 KB |
Output is correct |
14 |
Correct |
164 ms |
50848 KB |
Output is correct |
15 |
Correct |
172 ms |
49952 KB |
Output is correct |
16 |
Correct |
159 ms |
49436 KB |
Output is correct |
17 |
Correct |
185 ms |
51400 KB |
Output is correct |
18 |
Correct |
175 ms |
50204 KB |
Output is correct |
19 |
Correct |
176 ms |
50568 KB |
Output is correct |
20 |
Correct |
201 ms |
50796 KB |
Output is correct |
21 |
Correct |
160 ms |
51240 KB |
Output is correct |
22 |
Correct |
168 ms |
50840 KB |
Output is correct |
23 |
Correct |
178 ms |
50844 KB |
Output is correct |
24 |
Correct |
154 ms |
49436 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
468 KB |
Output is correct |
5 |
Correct |
1 ms |
336 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
468 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
468 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
336 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
336 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
332 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
332 KB |
Output is correct |
25 |
Correct |
81 ms |
7968 KB |
Output is correct |
26 |
Correct |
10 ms |
1660 KB |
Output is correct |
27 |
Correct |
107 ms |
10768 KB |
Output is correct |
28 |
Correct |
147 ms |
10572 KB |
Output is correct |
29 |
Correct |
89 ms |
8392 KB |
Output is correct |
30 |
Correct |
80 ms |
7960 KB |
Output is correct |
31 |
Correct |
91 ms |
9740 KB |
Output is correct |
32 |
Correct |
108 ms |
10380 KB |
Output is correct |
33 |
Correct |
93 ms |
10840 KB |
Output is correct |
34 |
Correct |
53 ms |
5520 KB |
Output is correct |
35 |
Correct |
127 ms |
11600 KB |
Output is correct |
36 |
Correct |
127 ms |
10396 KB |
Output is correct |
37 |
Correct |
56 ms |
5992 KB |
Output is correct |
38 |
Correct |
136 ms |
9440 KB |
Output is correct |
39 |
Correct |
16 ms |
2064 KB |
Output is correct |
40 |
Correct |
96 ms |
9364 KB |
Output is correct |
41 |
Correct |
87 ms |
7984 KB |
Output is correct |
42 |
Correct |
122 ms |
9372 KB |
Output is correct |
43 |
Correct |
46 ms |
3996 KB |
Output is correct |
44 |
Correct |
115 ms |
9404 KB |
Output is correct |
45 |
Correct |
20 ms |
2380 KB |
Output is correct |
46 |
Correct |
107 ms |
9352 KB |
Output is correct |
47 |
Correct |
28 ms |
3076 KB |
Output is correct |
48 |
Correct |
110 ms |
9368 KB |
Output is correct |
49 |
Correct |
335 ms |
49280 KB |
Output is correct |
50 |
Correct |
378 ms |
51528 KB |
Output is correct |
51 |
Correct |
297 ms |
44864 KB |
Output is correct |
52 |
Correct |
409 ms |
51560 KB |
Output is correct |
53 |
Correct |
147 ms |
25100 KB |
Output is correct |
54 |
Correct |
336 ms |
51528 KB |
Output is correct |
55 |
Correct |
271 ms |
48460 KB |
Output is correct |
56 |
Correct |
326 ms |
51652 KB |
Output is correct |
57 |
Correct |
37 ms |
7508 KB |
Output is correct |
58 |
Correct |
406 ms |
51548 KB |
Output is correct |
59 |
Correct |
202 ms |
28808 KB |
Output is correct |
60 |
Correct |
331 ms |
51404 KB |
Output is correct |
61 |
Correct |
171 ms |
51260 KB |
Output is correct |
62 |
Correct |
164 ms |
50848 KB |
Output is correct |
63 |
Correct |
172 ms |
49952 KB |
Output is correct |
64 |
Correct |
159 ms |
49436 KB |
Output is correct |
65 |
Correct |
185 ms |
51400 KB |
Output is correct |
66 |
Correct |
175 ms |
50204 KB |
Output is correct |
67 |
Correct |
176 ms |
50568 KB |
Output is correct |
68 |
Correct |
201 ms |
50796 KB |
Output is correct |
69 |
Correct |
160 ms |
51240 KB |
Output is correct |
70 |
Correct |
168 ms |
50840 KB |
Output is correct |
71 |
Correct |
178 ms |
50844 KB |
Output is correct |
72 |
Correct |
154 ms |
49436 KB |
Output is correct |
73 |
Correct |
575 ms |
61896 KB |
Output is correct |
74 |
Correct |
380 ms |
56956 KB |
Output is correct |
75 |
Correct |
448 ms |
59248 KB |
Output is correct |
76 |
Correct |
578 ms |
67564 KB |
Output is correct |
77 |
Correct |
281 ms |
35248 KB |
Output is correct |
78 |
Correct |
565 ms |
63760 KB |
Output is correct |
79 |
Correct |
525 ms |
63780 KB |
Output is correct |
80 |
Correct |
601 ms |
67480 KB |
Output is correct |
81 |
Correct |
204 ms |
18764 KB |
Output is correct |
82 |
Correct |
467 ms |
61700 KB |
Output is correct |
83 |
Correct |
443 ms |
42828 KB |
Output is correct |
84 |
Correct |
645 ms |
67496 KB |
Output is correct |
85 |
Correct |
314 ms |
61608 KB |
Output is correct |
86 |
Correct |
432 ms |
65612 KB |
Output is correct |
87 |
Correct |
204 ms |
55748 KB |
Output is correct |
88 |
Correct |
418 ms |
64176 KB |
Output is correct |
89 |
Correct |
399 ms |
63376 KB |
Output is correct |
90 |
Correct |
438 ms |
64840 KB |
Output is correct |
91 |
Correct |
257 ms |
58488 KB |
Output is correct |
92 |
Correct |
438 ms |
65580 KB |
Output is correct |
93 |
Correct |
200 ms |
57376 KB |
Output is correct |
94 |
Correct |
420 ms |
65396 KB |
Output is correct |
95 |
Correct |
238 ms |
57976 KB |
Output is correct |
96 |
Correct |
372 ms |
64276 KB |
Output is correct |