#include <bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define em emplace
#define all(v) v.begin(), v.end()
#define my_assert cout << "!" << endl;
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int MAX = 101010;
const int INF = (1 << 30) - 1;
const ll LINF = 1LL << 60;
struct antena {
int h, a, b;
} arr[2*MAX];
struct SEG {
vector <pll> tree;
vector <ll> lazy;
SEG(int n) {
tree.resize(4*n+10);
lazy.resize(4*n+10);
for(int i = 1; i < tree.size(); i++) {
tree[i].fi = -1;
tree[i].se = LINF;
lazy[i] = -LINF;
}
}
void update_lazy(int node, int s, int e) {
tree[node].fi = max(tree[node].fi, lazy[node] - tree[node].se);
if(s != e) {
lazy[node*2] = max(lazy[node*2], lazy[node]);
lazy[node*2+1] = max(lazy[node*2+1], lazy[node]);
}
lazy[node] = -LINF;
}
void update1(int node, int s, int e, int l, int r, int val) {
if(l > r) return;
update_lazy(node, s, e);
if(s > r || e < l) return;
if(s >= l && e <= r) {
lazy[node] = max(lazy[node], (ll)val);
update_lazy(node, s, e);
return;
}
int m = (s + e) / 2;
update1(node*2, s, m, l, r, val), update1(node*2+1, m+1, e, l, r, val);
tree[node].fi = max(tree[node*2].fi, tree[node*2+1].fi);
}
void update2(int node, int s, int e, int k, bool flag) {
update_lazy(node, s, e);
if(s == e) {
if(flag) tree[node].se = arr[k].h;
else tree[node].se = LINF;
return;
}
int m = (s + e) / 2;
if(k <= m) update2(node*2, s, m, k, flag);
else update2(node*2+1, m+1, e, k, flag);
tree[node].se = min(tree[node*2].se, tree[node*2+1].se);
}
int cal(int node, int s, int e, int l, int r) {
update_lazy(node, s, e);
if(s > r || e < l) return -1;
if(s >= l && e <= r) return tree[node].fi;
int m = (s + e) / 2;
return max(cal(node*2, s, m, l, r), cal(node*2+1, m+1, e, l, r));
}
};
struct Query {
int l, r, idx;
} Q[2*MAX];
int ans[2*MAX], n, q;
void solve() {
SEG st(n);
int idx = 0;
priority_queue <pii, vector <pii>, greater <pii> > pq1, pq2;
for(int i = 1; i <= q; i++) {
while(idx < Q[i].r) {
while(!pq2.empty() && pq2.top().fi == idx) {
st.update2(1, 1, n, pq2.top().se, false);
pq2.pop();
}
idx++;
while(!pq1.empty() && pq1.top().fi == idx) {
st.update2(1, 1, n, pq1.top().se, true);
pq1.pop();
}
st.update1(1, 1, n, max(1, idx - arr[idx].b), max(0, idx - arr[idx].a), arr[idx].h);
pq1.em(idx + arr[idx].a, idx);
pq2.em(idx + arr[idx].b, idx);
}
ans[Q[i].idx] = max(ans[Q[i].idx], st.cal(1, 1, n, Q[i].l, Q[i].r));
}
}
int main() {
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> arr[i].h >> arr[i].a >> arr[i].b;
}
cin >> q;
for(int i = 1; i <= q; i++) {
cin >> Q[i].l >> Q[i].r;
Q[i].idx = i;
ans[i] = -1;
}
sort(Q+1, Q+q+1, [](Query a, Query b) {
return a.r < b.r;
});
solve();
for(int i = 1; i <= n; i++) {
arr[i].h = - arr[i].h;
}
solve();
for(int i = 1; i <= q; i++) {
cout << ans[i] << '\n';
}
}
Compilation message
antennas.cpp: In constructor 'SEG::SEG(int)':
antennas.cpp:29:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < tree.size(); i++) {
~~^~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
424 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
424 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
136 ms |
5212 KB |
Output is correct |
26 |
Correct |
20 ms |
1080 KB |
Output is correct |
27 |
Correct |
200 ms |
7144 KB |
Output is correct |
28 |
Correct |
209 ms |
7208 KB |
Output is correct |
29 |
Correct |
136 ms |
5240 KB |
Output is correct |
30 |
Correct |
138 ms |
5064 KB |
Output is correct |
31 |
Correct |
155 ms |
6520 KB |
Output is correct |
32 |
Correct |
209 ms |
7224 KB |
Output is correct |
33 |
Correct |
185 ms |
6656 KB |
Output is correct |
34 |
Correct |
102 ms |
3752 KB |
Output is correct |
35 |
Correct |
200 ms |
7216 KB |
Output is correct |
36 |
Correct |
211 ms |
7372 KB |
Output is correct |
37 |
Correct |
117 ms |
3880 KB |
Output is correct |
38 |
Correct |
203 ms |
6492 KB |
Output is correct |
39 |
Correct |
32 ms |
1400 KB |
Output is correct |
40 |
Correct |
203 ms |
6388 KB |
Output is correct |
41 |
Correct |
147 ms |
4800 KB |
Output is correct |
42 |
Correct |
205 ms |
6384 KB |
Output is correct |
43 |
Correct |
71 ms |
2376 KB |
Output is correct |
44 |
Correct |
203 ms |
6248 KB |
Output is correct |
45 |
Correct |
37 ms |
1472 KB |
Output is correct |
46 |
Correct |
202 ms |
6260 KB |
Output is correct |
47 |
Correct |
55 ms |
2000 KB |
Output is correct |
48 |
Correct |
206 ms |
6368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
451 ms |
25384 KB |
Output is correct |
2 |
Correct |
508 ms |
27176 KB |
Output is correct |
3 |
Correct |
320 ms |
19800 KB |
Output is correct |
4 |
Correct |
513 ms |
27008 KB |
Output is correct |
5 |
Correct |
196 ms |
14304 KB |
Output is correct |
6 |
Correct |
489 ms |
27744 KB |
Output is correct |
7 |
Correct |
412 ms |
23644 KB |
Output is correct |
8 |
Correct |
521 ms |
30480 KB |
Output is correct |
9 |
Correct |
60 ms |
5124 KB |
Output is correct |
10 |
Correct |
553 ms |
30540 KB |
Output is correct |
11 |
Correct |
273 ms |
18604 KB |
Output is correct |
12 |
Correct |
481 ms |
30524 KB |
Output is correct |
13 |
Correct |
387 ms |
30404 KB |
Output is correct |
14 |
Correct |
352 ms |
30256 KB |
Output is correct |
15 |
Correct |
349 ms |
29200 KB |
Output is correct |
16 |
Correct |
298 ms |
29172 KB |
Output is correct |
17 |
Correct |
410 ms |
30456 KB |
Output is correct |
18 |
Correct |
349 ms |
29012 KB |
Output is correct |
19 |
Correct |
370 ms |
30584 KB |
Output is correct |
20 |
Correct |
356 ms |
30328 KB |
Output is correct |
21 |
Correct |
342 ms |
30496 KB |
Output is correct |
22 |
Correct |
360 ms |
30432 KB |
Output is correct |
23 |
Correct |
365 ms |
29072 KB |
Output is correct |
24 |
Correct |
306 ms |
29204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
376 KB |
Output is correct |
2 |
Correct |
2 ms |
376 KB |
Output is correct |
3 |
Correct |
3 ms |
376 KB |
Output is correct |
4 |
Correct |
3 ms |
376 KB |
Output is correct |
5 |
Correct |
2 ms |
376 KB |
Output is correct |
6 |
Correct |
2 ms |
380 KB |
Output is correct |
7 |
Correct |
3 ms |
376 KB |
Output is correct |
8 |
Correct |
3 ms |
376 KB |
Output is correct |
9 |
Correct |
2 ms |
376 KB |
Output is correct |
10 |
Correct |
2 ms |
376 KB |
Output is correct |
11 |
Correct |
2 ms |
376 KB |
Output is correct |
12 |
Correct |
3 ms |
376 KB |
Output is correct |
13 |
Correct |
2 ms |
376 KB |
Output is correct |
14 |
Correct |
3 ms |
376 KB |
Output is correct |
15 |
Correct |
2 ms |
376 KB |
Output is correct |
16 |
Correct |
3 ms |
376 KB |
Output is correct |
17 |
Correct |
2 ms |
424 KB |
Output is correct |
18 |
Correct |
2 ms |
376 KB |
Output is correct |
19 |
Correct |
2 ms |
376 KB |
Output is correct |
20 |
Correct |
3 ms |
376 KB |
Output is correct |
21 |
Correct |
3 ms |
376 KB |
Output is correct |
22 |
Correct |
3 ms |
376 KB |
Output is correct |
23 |
Correct |
3 ms |
376 KB |
Output is correct |
24 |
Correct |
3 ms |
376 KB |
Output is correct |
25 |
Correct |
136 ms |
5212 KB |
Output is correct |
26 |
Correct |
20 ms |
1080 KB |
Output is correct |
27 |
Correct |
200 ms |
7144 KB |
Output is correct |
28 |
Correct |
209 ms |
7208 KB |
Output is correct |
29 |
Correct |
136 ms |
5240 KB |
Output is correct |
30 |
Correct |
138 ms |
5064 KB |
Output is correct |
31 |
Correct |
155 ms |
6520 KB |
Output is correct |
32 |
Correct |
209 ms |
7224 KB |
Output is correct |
33 |
Correct |
185 ms |
6656 KB |
Output is correct |
34 |
Correct |
102 ms |
3752 KB |
Output is correct |
35 |
Correct |
200 ms |
7216 KB |
Output is correct |
36 |
Correct |
211 ms |
7372 KB |
Output is correct |
37 |
Correct |
117 ms |
3880 KB |
Output is correct |
38 |
Correct |
203 ms |
6492 KB |
Output is correct |
39 |
Correct |
32 ms |
1400 KB |
Output is correct |
40 |
Correct |
203 ms |
6388 KB |
Output is correct |
41 |
Correct |
147 ms |
4800 KB |
Output is correct |
42 |
Correct |
205 ms |
6384 KB |
Output is correct |
43 |
Correct |
71 ms |
2376 KB |
Output is correct |
44 |
Correct |
203 ms |
6248 KB |
Output is correct |
45 |
Correct |
37 ms |
1472 KB |
Output is correct |
46 |
Correct |
202 ms |
6260 KB |
Output is correct |
47 |
Correct |
55 ms |
2000 KB |
Output is correct |
48 |
Correct |
206 ms |
6368 KB |
Output is correct |
49 |
Correct |
451 ms |
25384 KB |
Output is correct |
50 |
Correct |
508 ms |
27176 KB |
Output is correct |
51 |
Correct |
320 ms |
19800 KB |
Output is correct |
52 |
Correct |
513 ms |
27008 KB |
Output is correct |
53 |
Correct |
196 ms |
14304 KB |
Output is correct |
54 |
Correct |
489 ms |
27744 KB |
Output is correct |
55 |
Correct |
412 ms |
23644 KB |
Output is correct |
56 |
Correct |
521 ms |
30480 KB |
Output is correct |
57 |
Correct |
60 ms |
5124 KB |
Output is correct |
58 |
Correct |
553 ms |
30540 KB |
Output is correct |
59 |
Correct |
273 ms |
18604 KB |
Output is correct |
60 |
Correct |
481 ms |
30524 KB |
Output is correct |
61 |
Correct |
387 ms |
30404 KB |
Output is correct |
62 |
Correct |
352 ms |
30256 KB |
Output is correct |
63 |
Correct |
349 ms |
29200 KB |
Output is correct |
64 |
Correct |
298 ms |
29172 KB |
Output is correct |
65 |
Correct |
410 ms |
30456 KB |
Output is correct |
66 |
Correct |
349 ms |
29012 KB |
Output is correct |
67 |
Correct |
370 ms |
30584 KB |
Output is correct |
68 |
Correct |
356 ms |
30328 KB |
Output is correct |
69 |
Correct |
342 ms |
30496 KB |
Output is correct |
70 |
Correct |
360 ms |
30432 KB |
Output is correct |
71 |
Correct |
365 ms |
29072 KB |
Output is correct |
72 |
Correct |
306 ms |
29204 KB |
Output is correct |
73 |
Correct |
851 ms |
33372 KB |
Output is correct |
74 |
Correct |
534 ms |
30556 KB |
Output is correct |
75 |
Correct |
682 ms |
28672 KB |
Output is correct |
76 |
Correct |
895 ms |
37808 KB |
Output is correct |
77 |
Correct |
447 ms |
19808 KB |
Output is correct |
78 |
Correct |
747 ms |
35644 KB |
Output is correct |
79 |
Correct |
844 ms |
33376 KB |
Output is correct |
80 |
Correct |
956 ms |
38336 KB |
Output is correct |
81 |
Correct |
339 ms |
12216 KB |
Output is correct |
82 |
Correct |
709 ms |
34276 KB |
Output is correct |
83 |
Correct |
633 ms |
26172 KB |
Output is correct |
84 |
Correct |
952 ms |
38236 KB |
Output is correct |
85 |
Correct |
623 ms |
34076 KB |
Output is correct |
86 |
Correct |
753 ms |
36776 KB |
Output is correct |
87 |
Correct |
412 ms |
29968 KB |
Output is correct |
88 |
Correct |
697 ms |
35624 KB |
Output is correct |
89 |
Correct |
691 ms |
35140 KB |
Output is correct |
90 |
Correct |
744 ms |
35536 KB |
Output is correct |
91 |
Correct |
513 ms |
32616 KB |
Output is correct |
92 |
Correct |
762 ms |
36820 KB |
Output is correct |
93 |
Correct |
422 ms |
31564 KB |
Output is correct |
94 |
Correct |
758 ms |
36956 KB |
Output is correct |
95 |
Correct |
472 ms |
30896 KB |
Output is correct |
96 |
Correct |
705 ms |
35600 KB |
Output is correct |