#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
const ll inf = 1e17;
class seg_tree
{
vector<ll> C, lazy, D;
public:
seg_tree(int n)
{
C.assign(4 * n + 5, -inf);
lazy.assign(4 * n + 5, inf);
D.assign(4 * n + 5, -inf);
}
#define lc id << 1
#define rc id << 1 | 1
void dolazy(int id, int l, int r)
{
if (lazy[id] != inf && l != r){
lazy[lc] = min(lazy[lc], lazy[id]);
lazy[rc] = min(lazy[rc], lazy[id]);
D[lc] = max(D[lc], C[lc] - lazy[lc]);
D[rc] = max(D[rc], C[rc] - lazy[rc]);
}
lazy[id] = inf;
}
void merges(int id)
{
C[id] = max(C[lc], C[rc]);
D[id] = max(D[lc], D[rc]);
}
void down(int id, int l, int r, int pos, ll val)
{
dolazy(id, l, r);
if (l > pos || r < pos)
return;
if (l == r){
C[id] = val;
return;
}
int mid = (l + r) / 2;
down(lc, l, mid, pos, val); down(rc, mid + 1, r, pos, val);
merges(id);
}
void update(int id, int l, int r, int L, int R, ll val)
{
dolazy(id, l, r);
if (l > R || L > r || L > R) return;
if (L <= l && r <= R){
lazy[id] = val;
D[id] = max(D[id], C[id] - lazy[id]);
return;
}
int mid = (l + r) / 2;
update(lc, l, mid, L, R, val); update(rc, mid + 1, r, L, R, val);
merges(id);
}
ll getmax(int id, int l, int r, int L, int R)
{
dolazy(id, l, r);
if (l > R || L > r) return -inf;
if (L <= l && r <= R){
return D[id];
}
int mid = (l + r) / 2;
return max(getmax(lc, l, mid, L, R), getmax(rc, mid + 1, r, L, R));
}
#undef lc
#undef rc
};
class Query
{
public:
int l, r;
};
int N, Q;
vector<int> add[maxn], del[maxn];
ll H[maxn]; int A[maxn], B[maxn];
vector<int> ask[maxn];
Query query[maxn];
ll res[maxn];
void solve(void)
{
for (int i = 1; i <= N; ++i){
add[i].clear(); del[i].clear();
ask[i].clear();
}
for (int i = 1; i <= N; ++i){
int s = i + A[i], e = i + B[i] + 1;
if (s <= N) add[s].pb(i);
if (e <= N) del[e].pb(i);
}
for (int i = 1; i <= Q; ++i){
ask[query[i].r].pb(i);
}
seg_tree tree(N);
for (int i = 1; i <= N; ++i){
for (auto & id : add[i])
tree.down(1, 1, N, id, H[id]);
for (auto & id : del[i])
tree.down(1, 1, N, id, -inf);
int s = max(0, i - A[i]), e = i - B[i];
tree.update(1, 1, N, max(1, e), s, H[i]);
for (auto & id : ask[i]){
int l = query[id].l;
res[id] = max(res[id], tree.getmax(1, 1, N, l, i));
}
}
}
signed main(void)
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if (fopen("A.INP", "r")){
freopen("A.INP", "r", stdin);
freopen("A.OUT", "w", stdout);
}
cin >> N;
for (int i = 1; i <= N; ++i){
cin >> H[i] >> A[i] >> B[i];
}
cin >> Q;
for (int i = 1; i <= Q; ++i){
cin >> query[i].l >> query[i].r;
res[i] = -1;
}
solve();
reverse(H + 1, H + 1 + N);
reverse(A + 1, A + 1 + N);
reverse(B + 1, B + 1 + N);
for (int i = 1; i <= Q; ++i){
query[i].l = N - query[i].l + 1;
query[i].r = N - query[i].r + 1;
swap(query[i].l, query[i].r);
}
solve();
for (int i = 1; i <= Q; ++i) cout << res[i] << '\n';
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:127:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("A.INP", "r", stdin);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~
antennas.cpp:128:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
freopen("A.OUT", "w", stdout);
~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
14456 KB |
Output is correct |
2 |
Correct |
19 ms |
14584 KB |
Output is correct |
3 |
Correct |
16 ms |
14584 KB |
Output is correct |
4 |
Correct |
19 ms |
14456 KB |
Output is correct |
5 |
Correct |
15 ms |
14584 KB |
Output is correct |
6 |
Correct |
15 ms |
14584 KB |
Output is correct |
7 |
Correct |
16 ms |
14584 KB |
Output is correct |
8 |
Correct |
16 ms |
14584 KB |
Output is correct |
9 |
Correct |
15 ms |
14584 KB |
Output is correct |
10 |
Correct |
16 ms |
14456 KB |
Output is correct |
11 |
Correct |
15 ms |
14456 KB |
Output is correct |
12 |
Correct |
16 ms |
14584 KB |
Output is correct |
13 |
Correct |
15 ms |
14584 KB |
Output is correct |
14 |
Correct |
22 ms |
14456 KB |
Output is correct |
15 |
Correct |
16 ms |
14584 KB |
Output is correct |
16 |
Correct |
16 ms |
14584 KB |
Output is correct |
17 |
Correct |
15 ms |
14456 KB |
Output is correct |
18 |
Correct |
16 ms |
14456 KB |
Output is correct |
19 |
Correct |
16 ms |
14584 KB |
Output is correct |
20 |
Correct |
16 ms |
14556 KB |
Output is correct |
21 |
Correct |
15 ms |
14456 KB |
Output is correct |
22 |
Correct |
16 ms |
14500 KB |
Output is correct |
23 |
Correct |
15 ms |
14456 KB |
Output is correct |
24 |
Correct |
16 ms |
14456 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
14456 KB |
Output is correct |
2 |
Correct |
19 ms |
14584 KB |
Output is correct |
3 |
Correct |
16 ms |
14584 KB |
Output is correct |
4 |
Correct |
19 ms |
14456 KB |
Output is correct |
5 |
Correct |
15 ms |
14584 KB |
Output is correct |
6 |
Correct |
15 ms |
14584 KB |
Output is correct |
7 |
Correct |
16 ms |
14584 KB |
Output is correct |
8 |
Correct |
16 ms |
14584 KB |
Output is correct |
9 |
Correct |
15 ms |
14584 KB |
Output is correct |
10 |
Correct |
16 ms |
14456 KB |
Output is correct |
11 |
Correct |
15 ms |
14456 KB |
Output is correct |
12 |
Correct |
16 ms |
14584 KB |
Output is correct |
13 |
Correct |
15 ms |
14584 KB |
Output is correct |
14 |
Correct |
22 ms |
14456 KB |
Output is correct |
15 |
Correct |
16 ms |
14584 KB |
Output is correct |
16 |
Correct |
16 ms |
14584 KB |
Output is correct |
17 |
Correct |
15 ms |
14456 KB |
Output is correct |
18 |
Correct |
16 ms |
14456 KB |
Output is correct |
19 |
Correct |
16 ms |
14584 KB |
Output is correct |
20 |
Correct |
16 ms |
14556 KB |
Output is correct |
21 |
Correct |
15 ms |
14456 KB |
Output is correct |
22 |
Correct |
16 ms |
14500 KB |
Output is correct |
23 |
Correct |
15 ms |
14456 KB |
Output is correct |
24 |
Correct |
16 ms |
14456 KB |
Output is correct |
25 |
Correct |
153 ms |
20548 KB |
Output is correct |
26 |
Correct |
35 ms |
15340 KB |
Output is correct |
27 |
Correct |
221 ms |
23260 KB |
Output is correct |
28 |
Correct |
235 ms |
23044 KB |
Output is correct |
29 |
Correct |
148 ms |
20600 KB |
Output is correct |
30 |
Correct |
164 ms |
20324 KB |
Output is correct |
31 |
Correct |
188 ms |
22140 KB |
Output is correct |
32 |
Correct |
234 ms |
23156 KB |
Output is correct |
33 |
Correct |
211 ms |
22760 KB |
Output is correct |
34 |
Correct |
115 ms |
18688 KB |
Output is correct |
35 |
Correct |
220 ms |
23176 KB |
Output is correct |
36 |
Correct |
235 ms |
23000 KB |
Output is correct |
37 |
Correct |
124 ms |
18952 KB |
Output is correct |
38 |
Correct |
238 ms |
22160 KB |
Output is correct |
39 |
Correct |
42 ms |
15752 KB |
Output is correct |
40 |
Correct |
216 ms |
22024 KB |
Output is correct |
41 |
Correct |
158 ms |
20112 KB |
Output is correct |
42 |
Correct |
221 ms |
22032 KB |
Output is correct |
43 |
Correct |
79 ms |
17320 KB |
Output is correct |
44 |
Correct |
217 ms |
22000 KB |
Output is correct |
45 |
Correct |
49 ms |
15980 KB |
Output is correct |
46 |
Correct |
220 ms |
21960 KB |
Output is correct |
47 |
Correct |
65 ms |
16652 KB |
Output is correct |
48 |
Correct |
217 ms |
22028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
596 ms |
39444 KB |
Output is correct |
2 |
Correct |
671 ms |
46596 KB |
Output is correct |
3 |
Correct |
438 ms |
36960 KB |
Output is correct |
4 |
Correct |
692 ms |
46520 KB |
Output is correct |
5 |
Correct |
275 ms |
29060 KB |
Output is correct |
6 |
Correct |
679 ms |
46608 KB |
Output is correct |
7 |
Correct |
573 ms |
42248 KB |
Output is correct |
8 |
Correct |
740 ms |
46468 KB |
Output is correct |
9 |
Correct |
88 ms |
19524 KB |
Output is correct |
10 |
Correct |
699 ms |
46632 KB |
Output is correct |
11 |
Correct |
374 ms |
34436 KB |
Output is correct |
12 |
Correct |
741 ms |
46648 KB |
Output is correct |
13 |
Correct |
374 ms |
44300 KB |
Output is correct |
14 |
Correct |
333 ms |
43952 KB |
Output is correct |
15 |
Correct |
326 ms |
43392 KB |
Output is correct |
16 |
Correct |
305 ms |
43280 KB |
Output is correct |
17 |
Correct |
367 ms |
44792 KB |
Output is correct |
18 |
Correct |
334 ms |
43652 KB |
Output is correct |
19 |
Correct |
346 ms |
43768 KB |
Output is correct |
20 |
Correct |
344 ms |
43736 KB |
Output is correct |
21 |
Correct |
333 ms |
44084 KB |
Output is correct |
22 |
Correct |
333 ms |
43904 KB |
Output is correct |
23 |
Correct |
340 ms |
43888 KB |
Output is correct |
24 |
Correct |
305 ms |
43184 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
14456 KB |
Output is correct |
2 |
Correct |
19 ms |
14584 KB |
Output is correct |
3 |
Correct |
16 ms |
14584 KB |
Output is correct |
4 |
Correct |
19 ms |
14456 KB |
Output is correct |
5 |
Correct |
15 ms |
14584 KB |
Output is correct |
6 |
Correct |
15 ms |
14584 KB |
Output is correct |
7 |
Correct |
16 ms |
14584 KB |
Output is correct |
8 |
Correct |
16 ms |
14584 KB |
Output is correct |
9 |
Correct |
15 ms |
14584 KB |
Output is correct |
10 |
Correct |
16 ms |
14456 KB |
Output is correct |
11 |
Correct |
15 ms |
14456 KB |
Output is correct |
12 |
Correct |
16 ms |
14584 KB |
Output is correct |
13 |
Correct |
15 ms |
14584 KB |
Output is correct |
14 |
Correct |
22 ms |
14456 KB |
Output is correct |
15 |
Correct |
16 ms |
14584 KB |
Output is correct |
16 |
Correct |
16 ms |
14584 KB |
Output is correct |
17 |
Correct |
15 ms |
14456 KB |
Output is correct |
18 |
Correct |
16 ms |
14456 KB |
Output is correct |
19 |
Correct |
16 ms |
14584 KB |
Output is correct |
20 |
Correct |
16 ms |
14556 KB |
Output is correct |
21 |
Correct |
15 ms |
14456 KB |
Output is correct |
22 |
Correct |
16 ms |
14500 KB |
Output is correct |
23 |
Correct |
15 ms |
14456 KB |
Output is correct |
24 |
Correct |
16 ms |
14456 KB |
Output is correct |
25 |
Correct |
153 ms |
20548 KB |
Output is correct |
26 |
Correct |
35 ms |
15340 KB |
Output is correct |
27 |
Correct |
221 ms |
23260 KB |
Output is correct |
28 |
Correct |
235 ms |
23044 KB |
Output is correct |
29 |
Correct |
148 ms |
20600 KB |
Output is correct |
30 |
Correct |
164 ms |
20324 KB |
Output is correct |
31 |
Correct |
188 ms |
22140 KB |
Output is correct |
32 |
Correct |
234 ms |
23156 KB |
Output is correct |
33 |
Correct |
211 ms |
22760 KB |
Output is correct |
34 |
Correct |
115 ms |
18688 KB |
Output is correct |
35 |
Correct |
220 ms |
23176 KB |
Output is correct |
36 |
Correct |
235 ms |
23000 KB |
Output is correct |
37 |
Correct |
124 ms |
18952 KB |
Output is correct |
38 |
Correct |
238 ms |
22160 KB |
Output is correct |
39 |
Correct |
42 ms |
15752 KB |
Output is correct |
40 |
Correct |
216 ms |
22024 KB |
Output is correct |
41 |
Correct |
158 ms |
20112 KB |
Output is correct |
42 |
Correct |
221 ms |
22032 KB |
Output is correct |
43 |
Correct |
79 ms |
17320 KB |
Output is correct |
44 |
Correct |
217 ms |
22000 KB |
Output is correct |
45 |
Correct |
49 ms |
15980 KB |
Output is correct |
46 |
Correct |
220 ms |
21960 KB |
Output is correct |
47 |
Correct |
65 ms |
16652 KB |
Output is correct |
48 |
Correct |
217 ms |
22028 KB |
Output is correct |
49 |
Correct |
596 ms |
39444 KB |
Output is correct |
50 |
Correct |
671 ms |
46596 KB |
Output is correct |
51 |
Correct |
438 ms |
36960 KB |
Output is correct |
52 |
Correct |
692 ms |
46520 KB |
Output is correct |
53 |
Correct |
275 ms |
29060 KB |
Output is correct |
54 |
Correct |
679 ms |
46608 KB |
Output is correct |
55 |
Correct |
573 ms |
42248 KB |
Output is correct |
56 |
Correct |
740 ms |
46468 KB |
Output is correct |
57 |
Correct |
88 ms |
19524 KB |
Output is correct |
58 |
Correct |
699 ms |
46632 KB |
Output is correct |
59 |
Correct |
374 ms |
34436 KB |
Output is correct |
60 |
Correct |
741 ms |
46648 KB |
Output is correct |
61 |
Correct |
374 ms |
44300 KB |
Output is correct |
62 |
Correct |
333 ms |
43952 KB |
Output is correct |
63 |
Correct |
326 ms |
43392 KB |
Output is correct |
64 |
Correct |
305 ms |
43280 KB |
Output is correct |
65 |
Correct |
367 ms |
44792 KB |
Output is correct |
66 |
Correct |
334 ms |
43652 KB |
Output is correct |
67 |
Correct |
346 ms |
43768 KB |
Output is correct |
68 |
Correct |
344 ms |
43736 KB |
Output is correct |
69 |
Correct |
333 ms |
44084 KB |
Output is correct |
70 |
Correct |
333 ms |
43904 KB |
Output is correct |
71 |
Correct |
340 ms |
43888 KB |
Output is correct |
72 |
Correct |
305 ms |
43184 KB |
Output is correct |
73 |
Correct |
1086 ms |
51960 KB |
Output is correct |
74 |
Correct |
720 ms |
47884 KB |
Output is correct |
75 |
Correct |
1004 ms |
46764 KB |
Output is correct |
76 |
Correct |
1470 ms |
57456 KB |
Output is correct |
77 |
Correct |
638 ms |
36220 KB |
Output is correct |
78 |
Correct |
1056 ms |
54660 KB |
Output is correct |
79 |
Correct |
1225 ms |
52724 KB |
Output is correct |
80 |
Correct |
1273 ms |
57612 KB |
Output is correct |
81 |
Correct |
441 ms |
27100 KB |
Output is correct |
82 |
Correct |
975 ms |
53000 KB |
Output is correct |
83 |
Correct |
901 ms |
44020 KB |
Output is correct |
84 |
Correct |
1269 ms |
57576 KB |
Output is correct |
85 |
Correct |
668 ms |
51608 KB |
Output is correct |
86 |
Correct |
828 ms |
55008 KB |
Output is correct |
87 |
Correct |
416 ms |
45584 KB |
Output is correct |
88 |
Correct |
806 ms |
54284 KB |
Output is correct |
89 |
Correct |
782 ms |
53628 KB |
Output is correct |
90 |
Correct |
983 ms |
54816 KB |
Output is correct |
91 |
Correct |
539 ms |
48364 KB |
Output is correct |
92 |
Correct |
860 ms |
54876 KB |
Output is correct |
93 |
Correct |
431 ms |
46960 KB |
Output is correct |
94 |
Correct |
900 ms |
55072 KB |
Output is correct |
95 |
Correct |
490 ms |
47756 KB |
Output is correct |
96 |
Correct |
789 ms |
54052 KB |
Output is correct |