#include<bits/stdc++.h>
#include<fstream>
#pragma GCC optimize("Ofast,O3,unroll-loops")
#pragma GCC target("avx2")
using namespace std;
//ifstream fin("FEEDING.INP");
//ofstream fout("FEEDING.OUT");
#define sz(a) (int)a.size()
#define ll long long
#define pb push_back
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define ld long double
#define vt vector
#include<fstream>
#define fi first
#define se second
#define pll pair<ll, ll>
#define pii pair<int, int>
const int base = 74;
const ll mod = 1e9 + 7, inf = 1e9 + 5, mxv = 1005, mxn = 4e5 + 5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int n;
ll h[mxn + 1], a[mxn + 1], b[mxn + 1];
ll mxval[4 * mxn + 1], mnval[4 * mxn + 1], mxupd[4 * mxn + 1], mnupd[4 * mxn + 1], res[4 * mxn + 1], ans[mxn + 1];
vt<pii>queries[mxn + 1], comp[mxn + 1];
void change(int nd, ll mx, ll mn){
mxupd[nd] = max(mxupd[nd], mx); mnupd[nd] = min(mnupd[nd], mn);
res[nd] = max(res[nd], mxupd[nd] - mnval[nd]);
res[nd] = max(res[nd], mxval[nd] - mnupd[nd]);
}
void push(int nd){
ll mx = mxupd[nd], mn = mnupd[nd];
change(nd << 1, mx, mn); change(nd << 1 | 1, mx, mn);
mxupd[nd] = -inf; mnupd[nd] = inf;
}
void updsingle(int nd, int l, int r, int id, ll mn, ll mx){
if(id < l || id > r)return;
if(l == r){
mxval[nd] = mx; mnval[nd] = mn; mxupd[nd] = -inf; mnupd[nd] = inf;
return;
}
push(nd);
int mid = (l + r) >> 1;
updsingle(nd << 1, l, mid, id, mn, mx); updsingle(nd << 1 | 1, mid + 1, r, id, mn, mx);
mnval[nd] = min(mnval[nd << 1], mnval[nd << 1 | 1]);
mxval[nd] = max(mxval[nd << 1], mxval[nd << 1 | 1]);
}
void updrange(int nd, int l, int r, int ql, int qr, int v){
if(ql > r || qr < l)return;
if(ql <= l && qr >= r){
change(nd, v, v);
return;
}
int mid = (l + r) >> 1;
push(nd);
updrange(nd << 1, l, mid, ql, qr, v); updrange(nd << 1 | 1, mid + 1, r, ql, qr, v);
res[nd] = max(res[nd << 1], res[nd << 1 | 1]);
}
int get(int nd, int l, int r, int ql, int qr){
if(ql > r || qr < l)return(-1);
if(ql <= l && qr >= r)return(res[nd]);
push(nd);
int mid = (l + r) >> 1;
return(max(get(nd << 1, l, mid, ql, qr), get(nd << 1 | 1, mid + 1, r, ql, qr)));
}
signed main()
{
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++)cin >> h[i] >> a[i] >> b[i];
for(int i = 1; i <= 4 * n; i++){
res[i] = -1; mxval[i] = mxupd[i] = -inf; mnval[i] = mnupd[i] = inf;
}
int q; cin >> q;
for(int i = 0; i < q; i++){
int l, r; cin >> l >> r;
queries[r].pb(make_pair(l, i));
}
for(int i = 1; i <= n; i++){
for(auto [type, id]: comp[i]){
if(type == 1){
updsingle(1, 1, n, id, h[id], h[id]);
}else{
updsingle(1, 1, n, id, inf, -inf);
}
}
if(i - a[i] >= 1)updrange(1, 1, n, max(i - b[i], (ll)1), i - a[i], h[i]);
for(auto [l, id]: queries[i]){
ans[id] = get(1, 1, n, l, i);
}
comp[i + a[i]].pb(make_pair(1, i)); comp[i + b[i] + 1].pb(make_pair(-1, i));
}
for(int i = 0; i < q; i++){
cout << ans[i] << "\n";
}
return(0);
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:82:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
82 | for(auto [type, id]: comp[i]){
| ^
antennas.cpp:91:18: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
91 | for(auto [l, id]: queries[i]){
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
19196 KB |
Output is correct |
2 |
Correct |
9 ms |
19220 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
9 ms |
19260 KB |
Output is correct |
5 |
Correct |
9 ms |
19156 KB |
Output is correct |
6 |
Correct |
9 ms |
19156 KB |
Output is correct |
7 |
Correct |
9 ms |
19156 KB |
Output is correct |
8 |
Correct |
9 ms |
19156 KB |
Output is correct |
9 |
Correct |
9 ms |
19136 KB |
Output is correct |
10 |
Correct |
9 ms |
19156 KB |
Output is correct |
11 |
Correct |
9 ms |
19156 KB |
Output is correct |
12 |
Correct |
10 ms |
19188 KB |
Output is correct |
13 |
Correct |
9 ms |
19236 KB |
Output is correct |
14 |
Correct |
9 ms |
19156 KB |
Output is correct |
15 |
Correct |
9 ms |
19156 KB |
Output is correct |
16 |
Correct |
9 ms |
19132 KB |
Output is correct |
17 |
Correct |
9 ms |
19156 KB |
Output is correct |
18 |
Correct |
9 ms |
19156 KB |
Output is correct |
19 |
Correct |
9 ms |
19156 KB |
Output is correct |
20 |
Correct |
9 ms |
19156 KB |
Output is correct |
21 |
Correct |
9 ms |
19156 KB |
Output is correct |
22 |
Correct |
9 ms |
19156 KB |
Output is correct |
23 |
Correct |
11 ms |
19216 KB |
Output is correct |
24 |
Correct |
9 ms |
19212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
19196 KB |
Output is correct |
2 |
Correct |
9 ms |
19220 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
9 ms |
19260 KB |
Output is correct |
5 |
Correct |
9 ms |
19156 KB |
Output is correct |
6 |
Correct |
9 ms |
19156 KB |
Output is correct |
7 |
Correct |
9 ms |
19156 KB |
Output is correct |
8 |
Correct |
9 ms |
19156 KB |
Output is correct |
9 |
Correct |
9 ms |
19136 KB |
Output is correct |
10 |
Correct |
9 ms |
19156 KB |
Output is correct |
11 |
Correct |
9 ms |
19156 KB |
Output is correct |
12 |
Correct |
10 ms |
19188 KB |
Output is correct |
13 |
Correct |
9 ms |
19236 KB |
Output is correct |
14 |
Correct |
9 ms |
19156 KB |
Output is correct |
15 |
Correct |
9 ms |
19156 KB |
Output is correct |
16 |
Correct |
9 ms |
19132 KB |
Output is correct |
17 |
Correct |
9 ms |
19156 KB |
Output is correct |
18 |
Correct |
9 ms |
19156 KB |
Output is correct |
19 |
Correct |
9 ms |
19156 KB |
Output is correct |
20 |
Correct |
9 ms |
19156 KB |
Output is correct |
21 |
Correct |
9 ms |
19156 KB |
Output is correct |
22 |
Correct |
9 ms |
19156 KB |
Output is correct |
23 |
Correct |
11 ms |
19216 KB |
Output is correct |
24 |
Correct |
9 ms |
19212 KB |
Output is correct |
25 |
Correct |
62 ms |
23500 KB |
Output is correct |
26 |
Correct |
21 ms |
19924 KB |
Output is correct |
27 |
Correct |
98 ms |
25200 KB |
Output is correct |
28 |
Correct |
89 ms |
25272 KB |
Output is correct |
29 |
Correct |
61 ms |
23528 KB |
Output is correct |
30 |
Correct |
63 ms |
23268 KB |
Output is correct |
31 |
Correct |
70 ms |
24400 KB |
Output is correct |
32 |
Correct |
95 ms |
25268 KB |
Output is correct |
33 |
Correct |
99 ms |
24832 KB |
Output is correct |
34 |
Correct |
48 ms |
22228 KB |
Output is correct |
35 |
Correct |
88 ms |
25140 KB |
Output is correct |
36 |
Correct |
91 ms |
25312 KB |
Output is correct |
37 |
Correct |
54 ms |
22204 KB |
Output is correct |
38 |
Correct |
100 ms |
24300 KB |
Output is correct |
39 |
Correct |
21 ms |
20136 KB |
Output is correct |
40 |
Correct |
86 ms |
24284 KB |
Output is correct |
41 |
Correct |
66 ms |
22924 KB |
Output is correct |
42 |
Correct |
97 ms |
24268 KB |
Output is correct |
43 |
Correct |
41 ms |
21116 KB |
Output is correct |
44 |
Correct |
88 ms |
24352 KB |
Output is correct |
45 |
Correct |
23 ms |
20392 KB |
Output is correct |
46 |
Correct |
100 ms |
24324 KB |
Output is correct |
47 |
Correct |
31 ms |
20696 KB |
Output is correct |
48 |
Correct |
95 ms |
24380 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
227 ms |
58648 KB |
Output is correct |
2 |
Correct |
272 ms |
67552 KB |
Output is correct |
3 |
Correct |
208 ms |
53044 KB |
Output is correct |
4 |
Correct |
259 ms |
67600 KB |
Output is correct |
5 |
Correct |
103 ms |
41420 KB |
Output is correct |
6 |
Correct |
269 ms |
67708 KB |
Output is correct |
7 |
Correct |
223 ms |
61080 KB |
Output is correct |
8 |
Correct |
299 ms |
67604 KB |
Output is correct |
9 |
Correct |
45 ms |
26752 KB |
Output is correct |
10 |
Correct |
273 ms |
67520 KB |
Output is correct |
11 |
Correct |
194 ms |
49368 KB |
Output is correct |
12 |
Correct |
334 ms |
67568 KB |
Output is correct |
13 |
Correct |
176 ms |
64868 KB |
Output is correct |
14 |
Correct |
156 ms |
64848 KB |
Output is correct |
15 |
Correct |
151 ms |
65532 KB |
Output is correct |
16 |
Correct |
141 ms |
66008 KB |
Output is correct |
17 |
Correct |
191 ms |
64920 KB |
Output is correct |
18 |
Correct |
144 ms |
65232 KB |
Output is correct |
19 |
Correct |
185 ms |
64804 KB |
Output is correct |
20 |
Correct |
158 ms |
64892 KB |
Output is correct |
21 |
Correct |
169 ms |
64912 KB |
Output is correct |
22 |
Correct |
177 ms |
65152 KB |
Output is correct |
23 |
Correct |
157 ms |
64972 KB |
Output is correct |
24 |
Correct |
158 ms |
65716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
19196 KB |
Output is correct |
2 |
Correct |
9 ms |
19220 KB |
Output is correct |
3 |
Correct |
10 ms |
19156 KB |
Output is correct |
4 |
Correct |
9 ms |
19260 KB |
Output is correct |
5 |
Correct |
9 ms |
19156 KB |
Output is correct |
6 |
Correct |
9 ms |
19156 KB |
Output is correct |
7 |
Correct |
9 ms |
19156 KB |
Output is correct |
8 |
Correct |
9 ms |
19156 KB |
Output is correct |
9 |
Correct |
9 ms |
19136 KB |
Output is correct |
10 |
Correct |
9 ms |
19156 KB |
Output is correct |
11 |
Correct |
9 ms |
19156 KB |
Output is correct |
12 |
Correct |
10 ms |
19188 KB |
Output is correct |
13 |
Correct |
9 ms |
19236 KB |
Output is correct |
14 |
Correct |
9 ms |
19156 KB |
Output is correct |
15 |
Correct |
9 ms |
19156 KB |
Output is correct |
16 |
Correct |
9 ms |
19132 KB |
Output is correct |
17 |
Correct |
9 ms |
19156 KB |
Output is correct |
18 |
Correct |
9 ms |
19156 KB |
Output is correct |
19 |
Correct |
9 ms |
19156 KB |
Output is correct |
20 |
Correct |
9 ms |
19156 KB |
Output is correct |
21 |
Correct |
9 ms |
19156 KB |
Output is correct |
22 |
Correct |
9 ms |
19156 KB |
Output is correct |
23 |
Correct |
11 ms |
19216 KB |
Output is correct |
24 |
Correct |
9 ms |
19212 KB |
Output is correct |
25 |
Correct |
62 ms |
23500 KB |
Output is correct |
26 |
Correct |
21 ms |
19924 KB |
Output is correct |
27 |
Correct |
98 ms |
25200 KB |
Output is correct |
28 |
Correct |
89 ms |
25272 KB |
Output is correct |
29 |
Correct |
61 ms |
23528 KB |
Output is correct |
30 |
Correct |
63 ms |
23268 KB |
Output is correct |
31 |
Correct |
70 ms |
24400 KB |
Output is correct |
32 |
Correct |
95 ms |
25268 KB |
Output is correct |
33 |
Correct |
99 ms |
24832 KB |
Output is correct |
34 |
Correct |
48 ms |
22228 KB |
Output is correct |
35 |
Correct |
88 ms |
25140 KB |
Output is correct |
36 |
Correct |
91 ms |
25312 KB |
Output is correct |
37 |
Correct |
54 ms |
22204 KB |
Output is correct |
38 |
Correct |
100 ms |
24300 KB |
Output is correct |
39 |
Correct |
21 ms |
20136 KB |
Output is correct |
40 |
Correct |
86 ms |
24284 KB |
Output is correct |
41 |
Correct |
66 ms |
22924 KB |
Output is correct |
42 |
Correct |
97 ms |
24268 KB |
Output is correct |
43 |
Correct |
41 ms |
21116 KB |
Output is correct |
44 |
Correct |
88 ms |
24352 KB |
Output is correct |
45 |
Correct |
23 ms |
20392 KB |
Output is correct |
46 |
Correct |
100 ms |
24324 KB |
Output is correct |
47 |
Correct |
31 ms |
20696 KB |
Output is correct |
48 |
Correct |
95 ms |
24380 KB |
Output is correct |
49 |
Correct |
227 ms |
58648 KB |
Output is correct |
50 |
Correct |
272 ms |
67552 KB |
Output is correct |
51 |
Correct |
208 ms |
53044 KB |
Output is correct |
52 |
Correct |
259 ms |
67600 KB |
Output is correct |
53 |
Correct |
103 ms |
41420 KB |
Output is correct |
54 |
Correct |
269 ms |
67708 KB |
Output is correct |
55 |
Correct |
223 ms |
61080 KB |
Output is correct |
56 |
Correct |
299 ms |
67604 KB |
Output is correct |
57 |
Correct |
45 ms |
26752 KB |
Output is correct |
58 |
Correct |
273 ms |
67520 KB |
Output is correct |
59 |
Correct |
194 ms |
49368 KB |
Output is correct |
60 |
Correct |
334 ms |
67568 KB |
Output is correct |
61 |
Correct |
176 ms |
64868 KB |
Output is correct |
62 |
Correct |
156 ms |
64848 KB |
Output is correct |
63 |
Correct |
151 ms |
65532 KB |
Output is correct |
64 |
Correct |
141 ms |
66008 KB |
Output is correct |
65 |
Correct |
191 ms |
64920 KB |
Output is correct |
66 |
Correct |
144 ms |
65232 KB |
Output is correct |
67 |
Correct |
185 ms |
64804 KB |
Output is correct |
68 |
Correct |
158 ms |
64892 KB |
Output is correct |
69 |
Correct |
169 ms |
64912 KB |
Output is correct |
70 |
Correct |
177 ms |
65152 KB |
Output is correct |
71 |
Correct |
157 ms |
64972 KB |
Output is correct |
72 |
Correct |
158 ms |
65716 KB |
Output is correct |
73 |
Correct |
491 ms |
70160 KB |
Output is correct |
74 |
Correct |
375 ms |
68400 KB |
Output is correct |
75 |
Correct |
452 ms |
62540 KB |
Output is correct |
76 |
Correct |
619 ms |
77448 KB |
Output is correct |
77 |
Correct |
245 ms |
48080 KB |
Output is correct |
78 |
Correct |
453 ms |
74364 KB |
Output is correct |
79 |
Correct |
496 ms |
70824 KB |
Output is correct |
80 |
Correct |
630 ms |
77452 KB |
Output is correct |
81 |
Correct |
167 ms |
34868 KB |
Output is correct |
82 |
Correct |
455 ms |
72668 KB |
Output is correct |
83 |
Correct |
439 ms |
58732 KB |
Output is correct |
84 |
Correct |
560 ms |
77388 KB |
Output is correct |
85 |
Correct |
296 ms |
70176 KB |
Output is correct |
86 |
Correct |
412 ms |
73480 KB |
Output is correct |
87 |
Correct |
237 ms |
67028 KB |
Output is correct |
88 |
Correct |
393 ms |
74780 KB |
Output is correct |
89 |
Correct |
348 ms |
71488 KB |
Output is correct |
90 |
Correct |
515 ms |
73992 KB |
Output is correct |
91 |
Correct |
250 ms |
68020 KB |
Output is correct |
92 |
Correct |
433 ms |
73528 KB |
Output is correct |
93 |
Correct |
215 ms |
66724 KB |
Output is correct |
94 |
Correct |
411 ms |
73940 KB |
Output is correct |
95 |
Correct |
204 ms |
67576 KB |
Output is correct |
96 |
Correct |
316 ms |
74420 KB |
Output is correct |