#include<bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define ii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define INF 100000000000000000
#define modulo 1000000007
#define mod 998244353
#define int long long int
using namespace std;
vector<int> segn, segx;
int S;
int get(int a, int b, bool mx){
return (mx ? max(a, b) : min(a, b));
}
void build(vector<int>& seg, bool mx){
S = (1ll << (int)ceil(log2(seg.size())));
int l = S - seg.size();
for(int i = 0; i < l; i++)seg.pb(mx?0:INF);
reverse(all(seg));
for(int i = 1; i < seg.size(); i += 2) seg.pb(get(seg[i - 1], seg[i], mx));
seg.pb('a' + 't' + 'a' + 'k' + 'a' + 'n');
reverse(all(seg));
}
int query(vector<int>& seg, int j, int a, int b, int x, int y, bool mx){
if(y < a || b < x) return(mx ? 0 : INF);
if(a <= x && y <= b) return seg[j];
return get(query(seg, j * 2, a, b, x, (x + y) / 2, mx), query(seg, j * 2 + 1, a ,b, (x + y) / 2 + 1, y, mx), mx);
}
void update(vector<int>& seg, int j, int v,bool mx){
seg[j] = v;
j /= 2;
while(j > 0){
seg[j] = get(seg[j * 2], seg[j * 2 + 1], mx);
j /= 2;
}
}
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// freopen("q.gir","r",stdin);
// freopen("q.cik","w",stdout);
int n;
cin >> n;
vector<int> H(n + 1);
vector<int> A(n + 1);
vector<int> B(n+ 1);
vector<int> sweep[3 * n];
vector<int> Q[3 * n];
set<int> curr;
for(int i = 1; i <= n; i++){
cin >> H[i] >> A[i] >> B[i];
sweep[i + A[i]].pb(i);
sweep[i + B[i]].pb(-i);
}
segn = vector<int>(n + 1, INF);
segx = vector<int>(n + 1, 0);
build(segx, true);
build(segn, false);
int q, ans = -1;
cin >> q;
for(int i = 1; i <= q; i++){
int l, r;
cin >> l >> r;
Q[l].pb(i);
Q[r].pb(-i);
}
for(int i = 1; i <= n; i++){
for(int j = 0; j < sweep[i].size(); j++){
int id = sweep[i][j];
if(id > 0){
update(segx, segx.size() - S + id, H[id], true);
update(segn, segn.size() - S + id, H[id], false);
}
}
ans = max(ans,
max(
query(segx, 1, i - B[i], i - A[i], 0, S - 1, true) - H[i] ,
H[i] - query(segn, 1, i - B[i], i - A[i], 0, S - 1, false)
)
);
for(int j = 0; j < sweep[i].size(); j++){
int id = sweep[i][j];
if(id < 0){
id = -id;
update(segx, segx.size() - S + id, 0, true);
update(segn, segn.size() - S + id, INF, false);
}
}
}
cout << ans;
}
Compilation message
antennas.cpp: In function 'void build(std::vector<long long int>&, bool)':
antennas.cpp:22:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 1; i < seg.size(); i += 2) seg.pb(get(seg[i - 1], seg[i], mx));
~~^~~~~~~~~~~~
antennas.cpp: In function 'int32_t main()':
antennas.cpp:73:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < sweep[i].size(); j++){
~~^~~~~~~~~~~~~~~~~
antennas.cpp:86:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < sweep[i].size(); j++){
~~^~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
352 ms |
52240 KB |
Output is correct |
2 |
Correct |
368 ms |
57088 KB |
Output is correct |
3 |
Correct |
254 ms |
42568 KB |
Output is correct |
4 |
Correct |
350 ms |
57140 KB |
Output is correct |
5 |
Correct |
165 ms |
26752 KB |
Output is correct |
6 |
Correct |
378 ms |
57220 KB |
Output is correct |
7 |
Correct |
325 ms |
50744 KB |
Output is correct |
8 |
Correct |
354 ms |
56960 KB |
Output is correct |
9 |
Correct |
43 ms |
8984 KB |
Output is correct |
10 |
Correct |
354 ms |
57084 KB |
Output is correct |
11 |
Correct |
200 ms |
34724 KB |
Output is correct |
12 |
Correct |
370 ms |
57012 KB |
Output is correct |
13 |
Correct |
244 ms |
54516 KB |
Output is correct |
14 |
Correct |
234 ms |
54728 KB |
Output is correct |
15 |
Correct |
222 ms |
54748 KB |
Output is correct |
16 |
Correct |
247 ms |
56012 KB |
Output is correct |
17 |
Correct |
246 ms |
54520 KB |
Output is correct |
18 |
Correct |
237 ms |
54736 KB |
Output is correct |
19 |
Correct |
240 ms |
54512 KB |
Output is correct |
20 |
Correct |
245 ms |
54512 KB |
Output is correct |
21 |
Correct |
232 ms |
54252 KB |
Output is correct |
22 |
Correct |
237 ms |
54384 KB |
Output is correct |
23 |
Correct |
241 ms |
54776 KB |
Output is correct |
24 |
Correct |
228 ms |
55196 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
376 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |