#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 = 2e5 + 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 |
5 ms |
9812 KB |
Output is correct |
2 |
Correct |
5 ms |
9788 KB |
Output is correct |
3 |
Correct |
5 ms |
9740 KB |
Output is correct |
4 |
Correct |
6 ms |
9864 KB |
Output is correct |
5 |
Correct |
4 ms |
9812 KB |
Output is correct |
6 |
Correct |
5 ms |
9868 KB |
Output is correct |
7 |
Correct |
5 ms |
9864 KB |
Output is correct |
8 |
Correct |
4 ms |
9864 KB |
Output is correct |
9 |
Correct |
5 ms |
9812 KB |
Output is correct |
10 |
Correct |
5 ms |
9792 KB |
Output is correct |
11 |
Correct |
5 ms |
9812 KB |
Output is correct |
12 |
Correct |
6 ms |
9796 KB |
Output is correct |
13 |
Correct |
5 ms |
9736 KB |
Output is correct |
14 |
Correct |
6 ms |
9812 KB |
Output is correct |
15 |
Correct |
4 ms |
9740 KB |
Output is correct |
16 |
Correct |
4 ms |
9812 KB |
Output is correct |
17 |
Correct |
6 ms |
9824 KB |
Output is correct |
18 |
Correct |
5 ms |
9812 KB |
Output is correct |
19 |
Correct |
5 ms |
9812 KB |
Output is correct |
20 |
Correct |
6 ms |
9872 KB |
Output is correct |
21 |
Correct |
6 ms |
9812 KB |
Output is correct |
22 |
Correct |
5 ms |
9872 KB |
Output is correct |
23 |
Correct |
5 ms |
9812 KB |
Output is correct |
24 |
Correct |
6 ms |
9740 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9812 KB |
Output is correct |
2 |
Correct |
5 ms |
9788 KB |
Output is correct |
3 |
Correct |
5 ms |
9740 KB |
Output is correct |
4 |
Correct |
6 ms |
9864 KB |
Output is correct |
5 |
Correct |
4 ms |
9812 KB |
Output is correct |
6 |
Correct |
5 ms |
9868 KB |
Output is correct |
7 |
Correct |
5 ms |
9864 KB |
Output is correct |
8 |
Correct |
4 ms |
9864 KB |
Output is correct |
9 |
Correct |
5 ms |
9812 KB |
Output is correct |
10 |
Correct |
5 ms |
9792 KB |
Output is correct |
11 |
Correct |
5 ms |
9812 KB |
Output is correct |
12 |
Correct |
6 ms |
9796 KB |
Output is correct |
13 |
Correct |
5 ms |
9736 KB |
Output is correct |
14 |
Correct |
6 ms |
9812 KB |
Output is correct |
15 |
Correct |
4 ms |
9740 KB |
Output is correct |
16 |
Correct |
4 ms |
9812 KB |
Output is correct |
17 |
Correct |
6 ms |
9824 KB |
Output is correct |
18 |
Correct |
5 ms |
9812 KB |
Output is correct |
19 |
Correct |
5 ms |
9812 KB |
Output is correct |
20 |
Correct |
6 ms |
9872 KB |
Output is correct |
21 |
Correct |
6 ms |
9812 KB |
Output is correct |
22 |
Correct |
5 ms |
9872 KB |
Output is correct |
23 |
Correct |
5 ms |
9812 KB |
Output is correct |
24 |
Correct |
6 ms |
9740 KB |
Output is correct |
25 |
Correct |
73 ms |
15264 KB |
Output is correct |
26 |
Correct |
15 ms |
10820 KB |
Output is correct |
27 |
Correct |
96 ms |
17656 KB |
Output is correct |
28 |
Correct |
94 ms |
17736 KB |
Output is correct |
29 |
Correct |
67 ms |
15260 KB |
Output is correct |
30 |
Correct |
82 ms |
15232 KB |
Output is correct |
31 |
Correct |
76 ms |
16504 KB |
Output is correct |
32 |
Correct |
101 ms |
17728 KB |
Output is correct |
33 |
Correct |
86 ms |
17044 KB |
Output is correct |
34 |
Correct |
46 ms |
13772 KB |
Output is correct |
35 |
Correct |
102 ms |
17500 KB |
Output is correct |
36 |
Correct |
101 ms |
17744 KB |
Output is correct |
37 |
Correct |
54 ms |
13892 KB |
Output is correct |
38 |
Correct |
97 ms |
16748 KB |
Output is correct |
39 |
Correct |
24 ms |
11032 KB |
Output is correct |
40 |
Correct |
93 ms |
16780 KB |
Output is correct |
41 |
Correct |
65 ms |
14988 KB |
Output is correct |
42 |
Correct |
101 ms |
16728 KB |
Output is correct |
43 |
Correct |
32 ms |
12280 KB |
Output is correct |
44 |
Correct |
87 ms |
16844 KB |
Output is correct |
45 |
Correct |
23 ms |
11212 KB |
Output is correct |
46 |
Correct |
98 ms |
16836 KB |
Output is correct |
47 |
Correct |
30 ms |
11860 KB |
Output is correct |
48 |
Correct |
120 ms |
16728 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
349 ms |
99580 KB |
Execution killed with signal 6 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
9812 KB |
Output is correct |
2 |
Correct |
5 ms |
9788 KB |
Output is correct |
3 |
Correct |
5 ms |
9740 KB |
Output is correct |
4 |
Correct |
6 ms |
9864 KB |
Output is correct |
5 |
Correct |
4 ms |
9812 KB |
Output is correct |
6 |
Correct |
5 ms |
9868 KB |
Output is correct |
7 |
Correct |
5 ms |
9864 KB |
Output is correct |
8 |
Correct |
4 ms |
9864 KB |
Output is correct |
9 |
Correct |
5 ms |
9812 KB |
Output is correct |
10 |
Correct |
5 ms |
9792 KB |
Output is correct |
11 |
Correct |
5 ms |
9812 KB |
Output is correct |
12 |
Correct |
6 ms |
9796 KB |
Output is correct |
13 |
Correct |
5 ms |
9736 KB |
Output is correct |
14 |
Correct |
6 ms |
9812 KB |
Output is correct |
15 |
Correct |
4 ms |
9740 KB |
Output is correct |
16 |
Correct |
4 ms |
9812 KB |
Output is correct |
17 |
Correct |
6 ms |
9824 KB |
Output is correct |
18 |
Correct |
5 ms |
9812 KB |
Output is correct |
19 |
Correct |
5 ms |
9812 KB |
Output is correct |
20 |
Correct |
6 ms |
9872 KB |
Output is correct |
21 |
Correct |
6 ms |
9812 KB |
Output is correct |
22 |
Correct |
5 ms |
9872 KB |
Output is correct |
23 |
Correct |
5 ms |
9812 KB |
Output is correct |
24 |
Correct |
6 ms |
9740 KB |
Output is correct |
25 |
Correct |
73 ms |
15264 KB |
Output is correct |
26 |
Correct |
15 ms |
10820 KB |
Output is correct |
27 |
Correct |
96 ms |
17656 KB |
Output is correct |
28 |
Correct |
94 ms |
17736 KB |
Output is correct |
29 |
Correct |
67 ms |
15260 KB |
Output is correct |
30 |
Correct |
82 ms |
15232 KB |
Output is correct |
31 |
Correct |
76 ms |
16504 KB |
Output is correct |
32 |
Correct |
101 ms |
17728 KB |
Output is correct |
33 |
Correct |
86 ms |
17044 KB |
Output is correct |
34 |
Correct |
46 ms |
13772 KB |
Output is correct |
35 |
Correct |
102 ms |
17500 KB |
Output is correct |
36 |
Correct |
101 ms |
17744 KB |
Output is correct |
37 |
Correct |
54 ms |
13892 KB |
Output is correct |
38 |
Correct |
97 ms |
16748 KB |
Output is correct |
39 |
Correct |
24 ms |
11032 KB |
Output is correct |
40 |
Correct |
93 ms |
16780 KB |
Output is correct |
41 |
Correct |
65 ms |
14988 KB |
Output is correct |
42 |
Correct |
101 ms |
16728 KB |
Output is correct |
43 |
Correct |
32 ms |
12280 KB |
Output is correct |
44 |
Correct |
87 ms |
16844 KB |
Output is correct |
45 |
Correct |
23 ms |
11212 KB |
Output is correct |
46 |
Correct |
98 ms |
16836 KB |
Output is correct |
47 |
Correct |
30 ms |
11860 KB |
Output is correct |
48 |
Correct |
120 ms |
16728 KB |
Output is correct |
49 |
Runtime error |
349 ms |
99580 KB |
Execution killed with signal 6 |
50 |
Halted |
0 ms |
0 KB |
- |