#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 100;
class SegmentTree {
private:
int sz;
vector<int> C; // C[i] = H[i] if i is active, -INF otherwise. We hold maximum C for each node.
vector<int> D; // D[i] = max(C[i] - H[j]) so far. We hold maximum D for each node.
vector<int> L; // lazy propagation, we have to update D[k] = max(D[k], C[k] - L) on segment
void Push(int n) {
if (L[n] != INF) {
L[n * 2] = min(L[n * 2], L[n]); // in order to maximize C[k] - L
L[n * 2 + 1] = min(L[n * 2 + 1], L[n]);
D[n * 2] = max(D[n * 2], C[n * 2] - L[n]); // lazy propagation
D[n * 2 + 1] = max(D[n * 2 + 1], C[n * 2 + 1] - L[n]);
L[n] = INF;
}
}
void Pull(int n) {
C[n] = max(C[n * 2], C[n * 2 + 1]); // C helps in lazy propagation to update maximum C - L quickly
D[n] = max(D[n * 2], D[n * 2 + 1]);
}
void PointSetUpdate(int n, int tl, int tr, int k, int H) {
if (tl == tr) return void(C[n] = H);
Push(n);
int mid = (tl + tr) / 2;
if (k <= mid) {
PointSetUpdate(n * 2, tl, mid, k, H);
} else {
PointSetUpdate(n * 2 + 1, mid + 1, tr, k, H);
}
Pull(n);
}
void RangeUpdate(int n, int tl, int tr, int l, int r, int H) {
if (tr < l || r < tl || tl > tr || l > r) return;
if (l <= tl && tr <= r) {
D[n] = max(D[n], C[n] - H);
L[n] = min(L[n], H);
return;
}
Push(n);
int mid = (tl + tr) / 2;
RangeUpdate(n * 2, tl, mid, l, r, H);
RangeUpdate(n * 2 + 1, mid + 1, tr, l, r, H);
Pull(n);
}
int RangeMaximumQuery(int n, int tl, int tr, int l, int r) {
if (tr < l || r < tl || tl > tr || l > r) return -INF;
if (l <= tl && tr <= r) return D[n];
Push(n);
int mid = (tl + tr) / 2;
return max(RangeMaximumQuery(n * 2, tl, mid, l, r),
RangeMaximumQuery(n * 2 + 1, mid + 1, tr, l, r));
}
public:
SegmentTree(int n) : sz(n) {
C.assign(4 * sz, -INF);
D.assign(4 * sz, -INF);
L.assign(4 * sz, INF);
}
void PointSetUpdate(int k, int H) { // set C[k] = H
return PointSetUpdate(1, 0, sz - 1, k, H);
}
void RangeUpdate(int l, int r, int H) { // for each k, l <= k <= r, D[k] = max(D[k], C[k] - H)
return RangeUpdate(1, 0, sz - 1, l, r, H);
}
int RangeMaximumQuery(int l, int r) { // RMQ on the array D
return RangeMaximumQuery(1, 0, sz - 1, max(l, 0), r);
}
};
vector<int> answer;
void Solve(int N, int Q, vector<int> H, vector<int> A, vector<int> B,
vector<int> L, vector<int> R) {
int a;
vector<vector<pair<int, int>>> events(N); // (type, x)
// type = 1 -> set C[x] = H[x]
// type = 2 -> set C[x] = -INF
// type <= 0 -> query (x, current), query id is -type
for (int i = 0; i < N; i++) {
int l = i + A[i], r = i + B[i] + 1; // antenna i is active on segment [l, r)
if (l < N) events[l].emplace_back(1, i);
if (r < N) events[r].emplace_back(2, i);
}
for (int i = 0; i < Q; i++) {
events[R[i]].emplace_back(-i, L[i]);
}
SegmentTree seg(N);
for (int t = 0; t < N; t++) {
reverse(begin(events[t]), end(events[t]));
while (!events[t].empty()) { // updates
if (events[t].back().first <= 0) break;
int type = events[t].back().first;
int x = events[t].back().second;
events[t].pop_back();
if (type == 1) {
seg.PointSetUpdate(x, H[x]);
} else {
seg.PointSetUpdate(x, -INF);
}
}
// for k, t - B[t] <= k <= t - A[t], we update D[k] = max(D[k], C[k] - H[t])
seg.RangeUpdate(t - B[t], t - A[t], H[t]);
while (!events[t].empty()) { // queries
int ql = events[t].back().second;
int qr = t;
int qi = -events[t].back().first;
events[t].pop_back();
answer[qi] = max(answer[qi], seg.RangeMaximumQuery(ql, qr));
}
}
}
void Solve() {
ios::sync_with_stdio(0);
cin.tie(0), cout.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];
}
int Q;
cin >> Q;
vector<int> L(Q), R(Q);
for (int i = 0; i < Q; i++) {
cin >> L[i] >> R[i];
L[i]--, R[i]--;
}
answer.assign(Q, -1);
auto Reverse = [&]() {
// reverse the array
reverse(begin(H), end(H));
reverse(begin(A), end(A));
reverse(begin(B), end(B));
for (int i = 0; i < Q; i++) {
L[i] = N - 1 - L[i];
R[i] = N - 1 - R[i];
swap(L[i], R[i]);
}
};
Solve(N, Q, H, A, B, L, R);
Reverse();
Solve(N, Q, H, A, B, L, R);
}
void Write() {
for (auto &ans : answer) {
cout << ans << "\n";
}
}
int main() {
Solve();
Write();
return 0;
}
Compilation message
antennas.cpp: In function 'void Solve(int, int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
antennas.cpp:90:7: warning: unused variable 'a' [-Wunused-variable]
int a;
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
256 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
6 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
6 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
256 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
6 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
6 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
92 ms |
6448 KB |
Output is correct |
26 |
Correct |
18 ms |
1160 KB |
Output is correct |
27 |
Correct |
145 ms |
8680 KB |
Output is correct |
28 |
Correct |
144 ms |
8824 KB |
Output is correct |
29 |
Correct |
99 ms |
6592 KB |
Output is correct |
30 |
Correct |
102 ms |
6264 KB |
Output is correct |
31 |
Correct |
107 ms |
8112 KB |
Output is correct |
32 |
Correct |
140 ms |
8824 KB |
Output is correct |
33 |
Correct |
131 ms |
8620 KB |
Output is correct |
34 |
Correct |
76 ms |
4472 KB |
Output is correct |
35 |
Correct |
137 ms |
9112 KB |
Output is correct |
36 |
Correct |
141 ms |
8696 KB |
Output is correct |
37 |
Correct |
87 ms |
5528 KB |
Output is correct |
38 |
Correct |
137 ms |
8700 KB |
Output is correct |
39 |
Correct |
25 ms |
1812 KB |
Output is correct |
40 |
Correct |
160 ms |
8696 KB |
Output is correct |
41 |
Correct |
104 ms |
7056 KB |
Output is correct |
42 |
Correct |
143 ms |
8696 KB |
Output is correct |
43 |
Correct |
51 ms |
3380 KB |
Output is correct |
44 |
Correct |
136 ms |
8696 KB |
Output is correct |
45 |
Correct |
30 ms |
2236 KB |
Output is correct |
46 |
Correct |
135 ms |
8696 KB |
Output is correct |
47 |
Correct |
41 ms |
2760 KB |
Output is correct |
48 |
Correct |
139 ms |
8696 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
356 ms |
24288 KB |
Output is correct |
2 |
Correct |
395 ms |
26872 KB |
Output is correct |
3 |
Correct |
270 ms |
19016 KB |
Output is correct |
4 |
Correct |
393 ms |
26872 KB |
Output is correct |
5 |
Correct |
170 ms |
12736 KB |
Output is correct |
6 |
Correct |
399 ms |
26872 KB |
Output is correct |
7 |
Correct |
375 ms |
23388 KB |
Output is correct |
8 |
Correct |
387 ms |
26872 KB |
Output is correct |
9 |
Correct |
52 ms |
4548 KB |
Output is correct |
10 |
Correct |
408 ms |
27084 KB |
Output is correct |
11 |
Correct |
219 ms |
16888 KB |
Output is correct |
12 |
Correct |
399 ms |
27000 KB |
Output is correct |
13 |
Correct |
272 ms |
26824 KB |
Output is correct |
14 |
Correct |
253 ms |
26500 KB |
Output is correct |
15 |
Correct |
256 ms |
25776 KB |
Output is correct |
16 |
Correct |
231 ms |
26128 KB |
Output is correct |
17 |
Correct |
302 ms |
27016 KB |
Output is correct |
18 |
Correct |
255 ms |
26056 KB |
Output is correct |
19 |
Correct |
269 ms |
26320 KB |
Output is correct |
20 |
Correct |
261 ms |
26348 KB |
Output is correct |
21 |
Correct |
245 ms |
26784 KB |
Output is correct |
22 |
Correct |
256 ms |
26468 KB |
Output is correct |
23 |
Correct |
269 ms |
26488 KB |
Output is correct |
24 |
Correct |
228 ms |
25584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
3 |
Correct |
5 ms |
384 KB |
Output is correct |
4 |
Correct |
5 ms |
384 KB |
Output is correct |
5 |
Correct |
5 ms |
384 KB |
Output is correct |
6 |
Correct |
5 ms |
384 KB |
Output is correct |
7 |
Correct |
5 ms |
384 KB |
Output is correct |
8 |
Correct |
5 ms |
256 KB |
Output is correct |
9 |
Correct |
5 ms |
384 KB |
Output is correct |
10 |
Correct |
6 ms |
384 KB |
Output is correct |
11 |
Correct |
5 ms |
384 KB |
Output is correct |
12 |
Correct |
5 ms |
384 KB |
Output is correct |
13 |
Correct |
5 ms |
384 KB |
Output is correct |
14 |
Correct |
5 ms |
384 KB |
Output is correct |
15 |
Correct |
5 ms |
384 KB |
Output is correct |
16 |
Correct |
5 ms |
384 KB |
Output is correct |
17 |
Correct |
5 ms |
384 KB |
Output is correct |
18 |
Correct |
5 ms |
384 KB |
Output is correct |
19 |
Correct |
5 ms |
384 KB |
Output is correct |
20 |
Correct |
5 ms |
384 KB |
Output is correct |
21 |
Correct |
5 ms |
384 KB |
Output is correct |
22 |
Correct |
5 ms |
384 KB |
Output is correct |
23 |
Correct |
6 ms |
384 KB |
Output is correct |
24 |
Correct |
5 ms |
384 KB |
Output is correct |
25 |
Correct |
92 ms |
6448 KB |
Output is correct |
26 |
Correct |
18 ms |
1160 KB |
Output is correct |
27 |
Correct |
145 ms |
8680 KB |
Output is correct |
28 |
Correct |
144 ms |
8824 KB |
Output is correct |
29 |
Correct |
99 ms |
6592 KB |
Output is correct |
30 |
Correct |
102 ms |
6264 KB |
Output is correct |
31 |
Correct |
107 ms |
8112 KB |
Output is correct |
32 |
Correct |
140 ms |
8824 KB |
Output is correct |
33 |
Correct |
131 ms |
8620 KB |
Output is correct |
34 |
Correct |
76 ms |
4472 KB |
Output is correct |
35 |
Correct |
137 ms |
9112 KB |
Output is correct |
36 |
Correct |
141 ms |
8696 KB |
Output is correct |
37 |
Correct |
87 ms |
5528 KB |
Output is correct |
38 |
Correct |
137 ms |
8700 KB |
Output is correct |
39 |
Correct |
25 ms |
1812 KB |
Output is correct |
40 |
Correct |
160 ms |
8696 KB |
Output is correct |
41 |
Correct |
104 ms |
7056 KB |
Output is correct |
42 |
Correct |
143 ms |
8696 KB |
Output is correct |
43 |
Correct |
51 ms |
3380 KB |
Output is correct |
44 |
Correct |
136 ms |
8696 KB |
Output is correct |
45 |
Correct |
30 ms |
2236 KB |
Output is correct |
46 |
Correct |
135 ms |
8696 KB |
Output is correct |
47 |
Correct |
41 ms |
2760 KB |
Output is correct |
48 |
Correct |
139 ms |
8696 KB |
Output is correct |
49 |
Correct |
356 ms |
24288 KB |
Output is correct |
50 |
Correct |
395 ms |
26872 KB |
Output is correct |
51 |
Correct |
270 ms |
19016 KB |
Output is correct |
52 |
Correct |
393 ms |
26872 KB |
Output is correct |
53 |
Correct |
170 ms |
12736 KB |
Output is correct |
54 |
Correct |
399 ms |
26872 KB |
Output is correct |
55 |
Correct |
375 ms |
23388 KB |
Output is correct |
56 |
Correct |
387 ms |
26872 KB |
Output is correct |
57 |
Correct |
52 ms |
4548 KB |
Output is correct |
58 |
Correct |
408 ms |
27084 KB |
Output is correct |
59 |
Correct |
219 ms |
16888 KB |
Output is correct |
60 |
Correct |
399 ms |
27000 KB |
Output is correct |
61 |
Correct |
272 ms |
26824 KB |
Output is correct |
62 |
Correct |
253 ms |
26500 KB |
Output is correct |
63 |
Correct |
256 ms |
25776 KB |
Output is correct |
64 |
Correct |
231 ms |
26128 KB |
Output is correct |
65 |
Correct |
302 ms |
27016 KB |
Output is correct |
66 |
Correct |
255 ms |
26056 KB |
Output is correct |
67 |
Correct |
269 ms |
26320 KB |
Output is correct |
68 |
Correct |
261 ms |
26348 KB |
Output is correct |
69 |
Correct |
245 ms |
26784 KB |
Output is correct |
70 |
Correct |
256 ms |
26468 KB |
Output is correct |
71 |
Correct |
269 ms |
26488 KB |
Output is correct |
72 |
Correct |
228 ms |
25584 KB |
Output is correct |
73 |
Correct |
599 ms |
31260 KB |
Output is correct |
74 |
Correct |
438 ms |
27808 KB |
Output is correct |
75 |
Correct |
559 ms |
28396 KB |
Output is correct |
76 |
Correct |
717 ms |
36412 KB |
Output is correct |
77 |
Correct |
357 ms |
19264 KB |
Output is correct |
78 |
Correct |
612 ms |
33440 KB |
Output is correct |
79 |
Correct |
647 ms |
32796 KB |
Output is correct |
80 |
Correct |
717 ms |
36364 KB |
Output is correct |
81 |
Correct |
256 ms |
13104 KB |
Output is correct |
82 |
Correct |
566 ms |
31676 KB |
Output is correct |
83 |
Correct |
516 ms |
26204 KB |
Output is correct |
84 |
Correct |
744 ms |
36364 KB |
Output is correct |
85 |
Correct |
453 ms |
32764 KB |
Output is correct |
86 |
Correct |
561 ms |
36800 KB |
Output is correct |
87 |
Correct |
298 ms |
27440 KB |
Output is correct |
88 |
Correct |
532 ms |
36036 KB |
Output is correct |
89 |
Correct |
499 ms |
34320 KB |
Output is correct |
90 |
Correct |
561 ms |
36292 KB |
Output is correct |
91 |
Correct |
377 ms |
30012 KB |
Output is correct |
92 |
Correct |
559 ms |
36644 KB |
Output is correct |
93 |
Correct |
302 ms |
28824 KB |
Output is correct |
94 |
Correct |
548 ms |
36544 KB |
Output is correct |
95 |
Correct |
340 ms |
29416 KB |
Output is correct |
96 |
Correct |
525 ms |
36020 KB |
Output is correct |