#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
ll lMin[800002], rMax[800002];
ll rMaxLazy[800002];
ll ans[800002];
void init(int i, int l, int r){
ans[i] = -2e18, lMin[i] = 1e18, rMax[i] = rMaxLazy[i] = -1e18;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void propagate(int i, int l, int r){
if(rMaxLazy[i] == -1e18) return;
ans[i] = max(ans[i], rMaxLazy[i] - lMin[i]);
rMax[i] = max(rMax[i], rMaxLazy[i]);
if(l!=r){
rMaxLazy[i*2] = max(rMaxLazy[i*2], rMaxLazy[i]);
rMaxLazy[i*2+1] = max(rMaxLazy[i*2+1], rMaxLazy[i]);
}
rMaxLazy[i] = -1e18;
}
void update(int i, int l, int r, int s, int e, ll v, bool R){
propagate(i, l, r);
if(r<s || e<l) return;
if(s<=l && r<=e){
if(R){
rMaxLazy[i] = v;
propagate(i, l, r);
}
else{
assert(s==e);
lMin[i] = v;
ans[i] = max(ans[i], rMax[i] - lMin[i]);
}
return;
}
int m = (l+r)>>1;
update(i*2, l, m, s, e, v, R);
update(i*2+1, m+1, r, s, e, v, R);
lMin[i] = min(lMin[i*2], lMin[i*2+1]);
rMax[i] = max(rMax[i*2], rMax[i*2+1]);
ans[i] = max(ans[i*2], ans[i*2+1]);
}
ll query(int i, int l, int r, int s, int e){
propagate(i, l, r);
if(r<s || e<l) return -1;
if(s<=l && r<=e) return ans[i];
int m = (l+r)>>1;
return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} tree;
int n, q;
ll h[200002];
int a[200002], b[200002];
ll ans[200002];
int l[200002], r[200002];
vector<pair<int, int> > query[200002]; /// (쿼리 번호, l)
vector<pair<int, ll> > update[200002];
void solve(){
for(int i=1; i<=n; i++){
query[i].clear();
update[i].clear();
}
for(int i=1; i<=q; i++){
query[r[i]].push_back(make_pair(i, l[i]));
}
for(int i=1; i<=n; i++){
update[min(i+a[i], n+1)].push_back(make_pair(i, h[i]));
update[min(i+b[i]+1, n+1)].push_back(make_pair(i, 1e18));
}
tree.init(1, 1, n);
for(int i=1; i<=n; i++){
for(auto p: update[i]){
tree.update(1, 1, n, p.first, p.first, p.second, 0);
}
tree.update(1, 1, n, i-b[i], i-a[i], h[i], 1);
for(auto p: query[i]){
ans[p.first] = max(ans[p.first], tree.query(1, 1, n, p.second, i));
}
}
}
int main(){
scanf("%d", &n);
for(int i=1; i<=n; i++){
scanf("%lld %d %d", &h[i], &a[i], &b[i]);
}
scanf("%d", &q);
for(int i=1; i<=q; i++){
scanf("%d %d", &l[i], &r[i]);
ans[i] = -1;
}
solve();
reverse(h+1, h+n+1);
reverse(a+1, a+n+1);
reverse(b+1, b+n+1);
for(int i=1; i<=q; i++){
l[i] = n+1-l[i];
r[i] = n+1-r[i];
swap(l[i], r[i]);
}
solve();
for(int i=1; i<=q; i++) printf("%lld\n", ans[i]);
}
Compilation message
antennas.cpp: In function 'int main()':
antennas.cpp:97:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
97 | scanf("%d", &n);
| ~~~~~^~~~~~~~~~
antennas.cpp:99:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
99 | scanf("%lld %d %d", &h[i], &a[i], &b[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:101:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
101 | scanf("%d", &q);
| ~~~~~^~~~~~~~~~
antennas.cpp:103:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
103 | scanf("%d %d", &l[i], &r[i]);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
455 ms |
41900 KB |
Output is correct |
| 2 |
Correct |
500 ms |
44536 KB |
Output is correct |
| 3 |
Incorrect |
337 ms |
41896 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
9684 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
