#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T> bool chmin(T &a, T b) { return b < a && (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b && (a = b, true); }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U> void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T> void debug(T l, T r) { while (l != r) cerr << *l << " \n"[next(l) == r], ++l; }
#else
#define DE(...) 0
#define debug(...) 0
#endif
const int MAX_N = 200010, MAX_Q = 200010, inf = 1e9;
int n, h[MAX_N], a[MAX_N], b[MAX_N];
int q, ql[MAX_Q], qr[MAX_Q], res[MAX_Q];
struct sgt {
struct node {
int amn = inf, bmx = -inf, res = -inf;
void chb(int b) {
DE(amn, b);
chmax(bmx, b);
chmax(res, bmx - amn);
}
void cha(int a) {
bmx = -inf;
amn = a;
}
// a push is required before upd
void upd(node a, node b) {
chmax(res, max(a.res, b.res));
amn = min(a.amn, b.amn);
}
};
int n;
vector<node> val;
sgt (int n) : n(n) { val.resize(n<<1); }
void update(int i) {
if (i >= n) return;
push(i);
val[i].upd(val[i<<1], val[i<<1|1]);
}
void push(int i) {
if (i >= n) return;
int &b = val[i].bmx;
if (b == -inf) return;
val[i<<1].chb(b), val[i<<1|1].chb(b);
b = -inf;
}
void pa(int &i) {
i += n;
for (int j = 18;j > 0;--j)
push(i>>j);
}
void modia(int i, int a) {
pa(i);
val[i].cha(a);
for (;i>>=1;)
update(i);
}
void chmxb(int l, int r, int b) {
pa(l), pa(r);
int sl = l, sr = r;
for (;l < r;l>>=1, r>>=1) {
if (l&1) val[l++].chb(b);
if (r&1) val[--r].chb(b);
}
for (;sl>>=1, sr>>=1;)
update(sl), update(sr);
}
int qry(int l, int r) {
int res = -inf;
pa(l), pa(r);
for (;l < r;l>>=1, r>>=1) {
if (l&1) chmax(res, val[l++].res);
if (r&1) chmax(res, val[--r].res);
}
return res;
}
};
vector<pair<int,int>> allq[MAX_N];
void solve() {
vector<vector<int>> in(n+10), out(n+10);
for (int i = 0;i < n;++i) {
int l = i + a[i], r = i + b[i];
in[ min(n, l) ].pb(i);
out[ min(n, r) ].pb(i);
}
sgt tree(n);
for (int i = 0;i < n;++i) {
for (int id : in[i]) {
DE("modia ", id, h[id]);
tree.modia(id, h[id]);
}
int l = i - b[i], r = i - a[i];
chmax(l, 0), chmax(r, -1);
DE(i, l, r, h[i]);
tree.chmxb(l, r+1, h[i]);
for (auto [l, id] : allq[i]) {
chmax(res[id], tree.qry(l, i+1));
}
for (int id : out[i]) {
tree.modia(id, inf);
}
}
}
int32_t main() {
ios_base::sync_with_stdio(0), cin.tie(0);
cin >> n ;
for (int i = 0;i < n;++i)
cin >> h[i] >> a[i] >> b[i];
cin >> q;
for (int i = 0;i < q;++i) {
cin >> ql[i] >> qr[i], --ql[i], --qr[i];
allq[ qr[i] ].pb( ql[i], i );
res[i] = -1;
}
solve();
for (int i = 0;i < n;++i) {
h[i] = inf - h[i];
}
solve();
for (int i = 0;i < q;++i)
cout << res[i] << '\n';
}
Compilation message
antennas.cpp: In member function 'void sgt::node::chb(int)':
antennas.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
antennas.cpp:26:4: note: in expansion of macro 'DE'
26 | DE(amn, b);
| ^~
antennas.cpp: In function 'void solve()':
antennas.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
antennas.cpp:100:4: note: in expansion of macro 'DE'
100 | DE("modia ", id, h[id]);
| ^~
antennas.cpp:14:17: warning: statement has no effect [-Wunused-value]
14 | #define DE(...) 0
| ^
antennas.cpp:106:3: note: in expansion of macro 'DE'
106 | DE(i, l, r, h[i]);
| ^~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
6 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
5 ms |
5108 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Correct |
4 ms |
5120 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
5 ms |
5228 KB |
Output is correct |
9 |
Correct |
4 ms |
5100 KB |
Output is correct |
10 |
Correct |
4 ms |
5100 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5100 KB |
Output is correct |
13 |
Correct |
4 ms |
5100 KB |
Output is correct |
14 |
Correct |
4 ms |
5100 KB |
Output is correct |
15 |
Correct |
4 ms |
5100 KB |
Output is correct |
16 |
Correct |
4 ms |
5100 KB |
Output is correct |
17 |
Correct |
4 ms |
5120 KB |
Output is correct |
18 |
Correct |
5 ms |
5100 KB |
Output is correct |
19 |
Correct |
5 ms |
5100 KB |
Output is correct |
20 |
Correct |
5 ms |
5120 KB |
Output is correct |
21 |
Correct |
4 ms |
5100 KB |
Output is correct |
22 |
Correct |
4 ms |
5100 KB |
Output is correct |
23 |
Correct |
4 ms |
5100 KB |
Output is correct |
24 |
Correct |
4 ms |
5100 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
6 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
5 ms |
5108 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Correct |
4 ms |
5120 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
5 ms |
5228 KB |
Output is correct |
9 |
Correct |
4 ms |
5100 KB |
Output is correct |
10 |
Correct |
4 ms |
5100 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5100 KB |
Output is correct |
13 |
Correct |
4 ms |
5100 KB |
Output is correct |
14 |
Correct |
4 ms |
5100 KB |
Output is correct |
15 |
Correct |
4 ms |
5100 KB |
Output is correct |
16 |
Correct |
4 ms |
5100 KB |
Output is correct |
17 |
Correct |
4 ms |
5120 KB |
Output is correct |
18 |
Correct |
5 ms |
5100 KB |
Output is correct |
19 |
Correct |
5 ms |
5100 KB |
Output is correct |
20 |
Correct |
5 ms |
5120 KB |
Output is correct |
21 |
Correct |
4 ms |
5100 KB |
Output is correct |
22 |
Correct |
4 ms |
5100 KB |
Output is correct |
23 |
Correct |
4 ms |
5100 KB |
Output is correct |
24 |
Correct |
4 ms |
5100 KB |
Output is correct |
25 |
Correct |
85 ms |
11116 KB |
Output is correct |
26 |
Correct |
17 ms |
5996 KB |
Output is correct |
27 |
Correct |
130 ms |
13676 KB |
Output is correct |
28 |
Correct |
132 ms |
13800 KB |
Output is correct |
29 |
Correct |
97 ms |
11116 KB |
Output is correct |
30 |
Correct |
94 ms |
11092 KB |
Output is correct |
31 |
Correct |
106 ms |
12652 KB |
Output is correct |
32 |
Correct |
132 ms |
13620 KB |
Output is correct |
33 |
Correct |
117 ms |
13292 KB |
Output is correct |
34 |
Correct |
68 ms |
9260 KB |
Output is correct |
35 |
Correct |
127 ms |
13548 KB |
Output is correct |
36 |
Correct |
130 ms |
13612 KB |
Output is correct |
37 |
Correct |
74 ms |
9580 KB |
Output is correct |
38 |
Correct |
132 ms |
12752 KB |
Output is correct |
39 |
Correct |
23 ms |
6380 KB |
Output is correct |
40 |
Correct |
130 ms |
12628 KB |
Output is correct |
41 |
Correct |
91 ms |
10684 KB |
Output is correct |
42 |
Correct |
120 ms |
12732 KB |
Output is correct |
43 |
Correct |
45 ms |
7660 KB |
Output is correct |
44 |
Correct |
124 ms |
12732 KB |
Output is correct |
45 |
Correct |
26 ms |
6508 KB |
Output is correct |
46 |
Correct |
124 ms |
12740 KB |
Output is correct |
47 |
Correct |
41 ms |
7300 KB |
Output is correct |
48 |
Correct |
127 ms |
12740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
435 ms |
28780 KB |
Output is correct |
2 |
Correct |
492 ms |
31360 KB |
Output is correct |
3 |
Correct |
329 ms |
23456 KB |
Output is correct |
4 |
Correct |
514 ms |
31260 KB |
Output is correct |
5 |
Correct |
203 ms |
17316 KB |
Output is correct |
6 |
Correct |
487 ms |
31368 KB |
Output is correct |
7 |
Correct |
448 ms |
27644 KB |
Output is correct |
8 |
Correct |
475 ms |
31512 KB |
Output is correct |
9 |
Correct |
62 ms |
9172 KB |
Output is correct |
10 |
Correct |
501 ms |
31356 KB |
Output is correct |
11 |
Correct |
278 ms |
21364 KB |
Output is correct |
12 |
Correct |
482 ms |
31484 KB |
Output is correct |
13 |
Correct |
244 ms |
28816 KB |
Output is correct |
14 |
Correct |
232 ms |
28684 KB |
Output is correct |
15 |
Correct |
269 ms |
28792 KB |
Output is correct |
16 |
Correct |
236 ms |
29080 KB |
Output is correct |
17 |
Correct |
237 ms |
28524 KB |
Output is correct |
18 |
Correct |
253 ms |
29220 KB |
Output is correct |
19 |
Correct |
229 ms |
28364 KB |
Output is correct |
20 |
Correct |
245 ms |
28856 KB |
Output is correct |
21 |
Correct |
230 ms |
28756 KB |
Output is correct |
22 |
Correct |
232 ms |
28876 KB |
Output is correct |
23 |
Correct |
230 ms |
28396 KB |
Output is correct |
24 |
Correct |
225 ms |
28540 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
5100 KB |
Output is correct |
2 |
Correct |
6 ms |
5100 KB |
Output is correct |
3 |
Correct |
4 ms |
5100 KB |
Output is correct |
4 |
Correct |
5 ms |
5108 KB |
Output is correct |
5 |
Correct |
4 ms |
5100 KB |
Output is correct |
6 |
Correct |
4 ms |
5120 KB |
Output is correct |
7 |
Correct |
4 ms |
5100 KB |
Output is correct |
8 |
Correct |
5 ms |
5228 KB |
Output is correct |
9 |
Correct |
4 ms |
5100 KB |
Output is correct |
10 |
Correct |
4 ms |
5100 KB |
Output is correct |
11 |
Correct |
4 ms |
5100 KB |
Output is correct |
12 |
Correct |
4 ms |
5100 KB |
Output is correct |
13 |
Correct |
4 ms |
5100 KB |
Output is correct |
14 |
Correct |
4 ms |
5100 KB |
Output is correct |
15 |
Correct |
4 ms |
5100 KB |
Output is correct |
16 |
Correct |
4 ms |
5100 KB |
Output is correct |
17 |
Correct |
4 ms |
5120 KB |
Output is correct |
18 |
Correct |
5 ms |
5100 KB |
Output is correct |
19 |
Correct |
5 ms |
5100 KB |
Output is correct |
20 |
Correct |
5 ms |
5120 KB |
Output is correct |
21 |
Correct |
4 ms |
5100 KB |
Output is correct |
22 |
Correct |
4 ms |
5100 KB |
Output is correct |
23 |
Correct |
4 ms |
5100 KB |
Output is correct |
24 |
Correct |
4 ms |
5100 KB |
Output is correct |
25 |
Correct |
85 ms |
11116 KB |
Output is correct |
26 |
Correct |
17 ms |
5996 KB |
Output is correct |
27 |
Correct |
130 ms |
13676 KB |
Output is correct |
28 |
Correct |
132 ms |
13800 KB |
Output is correct |
29 |
Correct |
97 ms |
11116 KB |
Output is correct |
30 |
Correct |
94 ms |
11092 KB |
Output is correct |
31 |
Correct |
106 ms |
12652 KB |
Output is correct |
32 |
Correct |
132 ms |
13620 KB |
Output is correct |
33 |
Correct |
117 ms |
13292 KB |
Output is correct |
34 |
Correct |
68 ms |
9260 KB |
Output is correct |
35 |
Correct |
127 ms |
13548 KB |
Output is correct |
36 |
Correct |
130 ms |
13612 KB |
Output is correct |
37 |
Correct |
74 ms |
9580 KB |
Output is correct |
38 |
Correct |
132 ms |
12752 KB |
Output is correct |
39 |
Correct |
23 ms |
6380 KB |
Output is correct |
40 |
Correct |
130 ms |
12628 KB |
Output is correct |
41 |
Correct |
91 ms |
10684 KB |
Output is correct |
42 |
Correct |
120 ms |
12732 KB |
Output is correct |
43 |
Correct |
45 ms |
7660 KB |
Output is correct |
44 |
Correct |
124 ms |
12732 KB |
Output is correct |
45 |
Correct |
26 ms |
6508 KB |
Output is correct |
46 |
Correct |
124 ms |
12740 KB |
Output is correct |
47 |
Correct |
41 ms |
7300 KB |
Output is correct |
48 |
Correct |
127 ms |
12740 KB |
Output is correct |
49 |
Correct |
435 ms |
28780 KB |
Output is correct |
50 |
Correct |
492 ms |
31360 KB |
Output is correct |
51 |
Correct |
329 ms |
23456 KB |
Output is correct |
52 |
Correct |
514 ms |
31260 KB |
Output is correct |
53 |
Correct |
203 ms |
17316 KB |
Output is correct |
54 |
Correct |
487 ms |
31368 KB |
Output is correct |
55 |
Correct |
448 ms |
27644 KB |
Output is correct |
56 |
Correct |
475 ms |
31512 KB |
Output is correct |
57 |
Correct |
62 ms |
9172 KB |
Output is correct |
58 |
Correct |
501 ms |
31356 KB |
Output is correct |
59 |
Correct |
278 ms |
21364 KB |
Output is correct |
60 |
Correct |
482 ms |
31484 KB |
Output is correct |
61 |
Correct |
244 ms |
28816 KB |
Output is correct |
62 |
Correct |
232 ms |
28684 KB |
Output is correct |
63 |
Correct |
269 ms |
28792 KB |
Output is correct |
64 |
Correct |
236 ms |
29080 KB |
Output is correct |
65 |
Correct |
237 ms |
28524 KB |
Output is correct |
66 |
Correct |
253 ms |
29220 KB |
Output is correct |
67 |
Correct |
229 ms |
28364 KB |
Output is correct |
68 |
Correct |
245 ms |
28856 KB |
Output is correct |
69 |
Correct |
230 ms |
28756 KB |
Output is correct |
70 |
Correct |
232 ms |
28876 KB |
Output is correct |
71 |
Correct |
230 ms |
28396 KB |
Output is correct |
72 |
Correct |
225 ms |
28540 KB |
Output is correct |
73 |
Correct |
714 ms |
35436 KB |
Output is correct |
74 |
Correct |
524 ms |
32444 KB |
Output is correct |
75 |
Correct |
620 ms |
33660 KB |
Output is correct |
76 |
Correct |
784 ms |
42012 KB |
Output is correct |
77 |
Correct |
370 ms |
23256 KB |
Output is correct |
78 |
Correct |
675 ms |
38624 KB |
Output is correct |
79 |
Correct |
690 ms |
38248 KB |
Output is correct |
80 |
Correct |
763 ms |
40216 KB |
Output is correct |
81 |
Correct |
263 ms |
16156 KB |
Output is correct |
82 |
Correct |
648 ms |
36732 KB |
Output is correct |
83 |
Correct |
595 ms |
31348 KB |
Output is correct |
84 |
Correct |
843 ms |
41996 KB |
Output is correct |
85 |
Correct |
405 ms |
34456 KB |
Output is correct |
86 |
Correct |
490 ms |
38124 KB |
Output is correct |
87 |
Correct |
267 ms |
30332 KB |
Output is correct |
88 |
Correct |
508 ms |
38492 KB |
Output is correct |
89 |
Correct |
428 ms |
35704 KB |
Output is correct |
90 |
Correct |
472 ms |
38532 KB |
Output is correct |
91 |
Correct |
330 ms |
31916 KB |
Output is correct |
92 |
Correct |
473 ms |
37428 KB |
Output is correct |
93 |
Correct |
277 ms |
30268 KB |
Output is correct |
94 |
Correct |
496 ms |
38420 KB |
Output is correct |
95 |
Correct |
297 ms |
31116 KB |
Output is correct |
96 |
Correct |
518 ms |
37936 KB |
Output is correct |