#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];
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;
cin >> q;
vector<int> ans(q + 2, -1);
vector<int> qq(q + 2);
vector<int> Q[n + 2];
for(int i = 1; i <= q; i++){
int l, r;
cin >> l >> r;
Q[l].pb(i);
Q[r + 1].pb(-i);
qq[i] = l;
}
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);
}
}
for(int j = 0; j < Q[i].size(); j++){
int id = Q[i][j];
if(id > 0){
curr.insert(id);
}
else {
curr.erase(-id);
}
}
for(set<int>::iterator itr = curr.begin(); itr != curr.end(); itr++){
ans[*itr] = max(ans[*itr],
max(
query(segx, 1, max(i - B[i], qq[*itr]), i - A[i], 0, S - 1, true) - H[i] ,
H[i] - query(segn, 1, max(i - B[i], qq[*itr]), 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);
}
}
}
for(int i = 1; i <= q; i++) cout << ans[i] << "\n";
}
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:76:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < sweep[i].size(); j++){
~~^~~~~~~~~~~~~~~~~
antennas.cpp:83:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int j = 0; j < Q[i].size(); j++){
~~^~~~~~~~~~~~~
antennas.cpp:101: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 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
376 KB |
Output is correct |
3 |
Correct |
8 ms |
376 KB |
Output is correct |
4 |
Correct |
8 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
7 ms |
376 KB |
Output is correct |
7 |
Correct |
8 ms |
376 KB |
Output is correct |
8 |
Correct |
9 ms |
380 KB |
Output is correct |
9 |
Correct |
6 ms |
376 KB |
Output is correct |
10 |
Correct |
8 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
8 ms |
376 KB |
Output is correct |
13 |
Correct |
6 ms |
376 KB |
Output is correct |
14 |
Correct |
6 ms |
376 KB |
Output is correct |
15 |
Correct |
6 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
376 KB |
Output is correct |
18 |
Correct |
7 ms |
380 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
6 ms |
376 KB |
Output is correct |
21 |
Correct |
7 ms |
376 KB |
Output is correct |
22 |
Correct |
7 ms |
376 KB |
Output is correct |
23 |
Correct |
6 ms |
376 KB |
Output is correct |
24 |
Correct |
7 ms |
376 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
376 KB |
Output is correct |
3 |
Correct |
8 ms |
376 KB |
Output is correct |
4 |
Correct |
8 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
7 ms |
376 KB |
Output is correct |
7 |
Correct |
8 ms |
376 KB |
Output is correct |
8 |
Correct |
9 ms |
380 KB |
Output is correct |
9 |
Correct |
6 ms |
376 KB |
Output is correct |
10 |
Correct |
8 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
8 ms |
376 KB |
Output is correct |
13 |
Correct |
6 ms |
376 KB |
Output is correct |
14 |
Correct |
6 ms |
376 KB |
Output is correct |
15 |
Correct |
6 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
376 KB |
Output is correct |
18 |
Correct |
7 ms |
380 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
6 ms |
376 KB |
Output is correct |
21 |
Correct |
7 ms |
376 KB |
Output is correct |
22 |
Correct |
7 ms |
376 KB |
Output is correct |
23 |
Correct |
6 ms |
376 KB |
Output is correct |
24 |
Correct |
7 ms |
376 KB |
Output is correct |
25 |
Execution timed out |
3068 ms |
9892 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
311 ms |
39668 KB |
Output is correct |
2 |
Correct |
343 ms |
43132 KB |
Output is correct |
3 |
Correct |
244 ms |
32836 KB |
Output is correct |
4 |
Correct |
388 ms |
43136 KB |
Output is correct |
5 |
Correct |
141 ms |
20520 KB |
Output is correct |
6 |
Correct |
344 ms |
43136 KB |
Output is correct |
7 |
Correct |
298 ms |
38468 KB |
Output is correct |
8 |
Correct |
360 ms |
43136 KB |
Output is correct |
9 |
Correct |
45 ms |
6808 KB |
Output is correct |
10 |
Correct |
346 ms |
43136 KB |
Output is correct |
11 |
Correct |
207 ms |
26024 KB |
Output is correct |
12 |
Correct |
357 ms |
43136 KB |
Output is correct |
13 |
Correct |
249 ms |
40692 KB |
Output is correct |
14 |
Correct |
234 ms |
40904 KB |
Output is correct |
15 |
Correct |
200 ms |
40924 KB |
Output is correct |
16 |
Correct |
219 ms |
42212 KB |
Output is correct |
17 |
Correct |
252 ms |
40868 KB |
Output is correct |
18 |
Correct |
215 ms |
40784 KB |
Output is correct |
19 |
Correct |
225 ms |
40560 KB |
Output is correct |
20 |
Correct |
229 ms |
40828 KB |
Output is correct |
21 |
Correct |
241 ms |
40300 KB |
Output is correct |
22 |
Correct |
227 ms |
40688 KB |
Output is correct |
23 |
Correct |
230 ms |
40696 KB |
Output is correct |
24 |
Correct |
222 ms |
41336 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
376 KB |
Output is correct |
2 |
Correct |
7 ms |
376 KB |
Output is correct |
3 |
Correct |
8 ms |
376 KB |
Output is correct |
4 |
Correct |
8 ms |
376 KB |
Output is correct |
5 |
Correct |
6 ms |
376 KB |
Output is correct |
6 |
Correct |
7 ms |
376 KB |
Output is correct |
7 |
Correct |
8 ms |
376 KB |
Output is correct |
8 |
Correct |
9 ms |
380 KB |
Output is correct |
9 |
Correct |
6 ms |
376 KB |
Output is correct |
10 |
Correct |
8 ms |
376 KB |
Output is correct |
11 |
Correct |
5 ms |
376 KB |
Output is correct |
12 |
Correct |
8 ms |
376 KB |
Output is correct |
13 |
Correct |
6 ms |
376 KB |
Output is correct |
14 |
Correct |
6 ms |
376 KB |
Output is correct |
15 |
Correct |
6 ms |
376 KB |
Output is correct |
16 |
Correct |
6 ms |
376 KB |
Output is correct |
17 |
Correct |
7 ms |
376 KB |
Output is correct |
18 |
Correct |
7 ms |
380 KB |
Output is correct |
19 |
Correct |
5 ms |
376 KB |
Output is correct |
20 |
Correct |
6 ms |
376 KB |
Output is correct |
21 |
Correct |
7 ms |
376 KB |
Output is correct |
22 |
Correct |
7 ms |
376 KB |
Output is correct |
23 |
Correct |
6 ms |
376 KB |
Output is correct |
24 |
Correct |
7 ms |
376 KB |
Output is correct |
25 |
Execution timed out |
3068 ms |
9892 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |