#include <bits/stdc++.h>
#define int long long
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
using namespace std;
#define MAXN 200005
const int INF = 1e16;
int n, q, h[MAXN], a[MAXN], b[MAXN];
vector<int> ok[MAXN];
vector<pair<int, int>> query[MAXN];
pair<int, int> save[MAXN];
int res[MAXN];
struct SMT {
int n;
vector<int> st, ts, lz;
SMT(int _n = 0){
n = _n;
st.assign((n << 2) + 5, +INF);
ts.assign((n << 2) + 5, -INF);
lz.assign((n << 2) + 5, -INF);
}
void update(int id, int l, int r, int p, int val) {
if (l == r) return st[id] = val, void();
int mid = (l + r) >> 1;
push(id);
if (p <= mid) update(id << 1, l, mid, p, val);
else update(id << 1 | 1, mid + 1, r, p, val);
st[id] = min(st[id << 1], st[id << 1 | 1]);
}
void update(int p, int val){
update(1, 1, n, p, val);
}
void push(int id){
if (lz[id] == -INF) return;
lz[id << 1] = max(lz[id << 1], lz[id]);
lz[id << 1 | 1] = max(lz[id << 1 | 1], lz[id]);
ts[id << 1] = max(ts[id << 1], lz[id] - st[id << 1]);
ts[id << 1 | 1] = max(ts[id << 1 | 1], lz[id] - st[id << 1 | 1]);
lz[id] = -INF;
}
void updateRange(int id, int l, int r, int u, int v, int val) {
if (v < l || r < u) return;
if (u <= l && r <= v){
ts[id] = max(ts[id], val - st[id]);
lz[id] = max(lz[id], val);
return;
}
int mid = (l + r) >> 1;
push(id);
updateRange(id << 1, l, mid, u, v, val);
updateRange(id << 1 | 1, mid + 1, r, u, v, val);
ts[id] = max(ts[id << 1], ts[id << 1 | 1]);
}
void updateRange(int u, int v, int val) {
updateRange(1, 1, n, u, v, val);
}
int get(int id, int l, int r, int u, int v) {
if (v < l || r < u) return -INF;
if (u <= l && r <= v) return ts[id];
int mid = (l + r) >> 1;
push(id);
return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
}
int get(int u, int v) {
return get(1, 1, n, u, v);
}
};
int M(int x){
x = min(n, x);
x = max(x, 1ll);
return x;
}
void process(){
SMT tree = SMT(n);
FOR(i, 1, n){
for (int &x : ok[i]){
if (x > 0){
tree.update(+x, h[x]);
} else {
tree.update(-x, INF);
}
}
if (i - a[i] > 0) tree.updateRange(M(i - b[i]), M(i - a[i]), h[i]);
for (pair<int, int> &x : query[i]){
res[x.second] = max(res[x.second], tree.get(x.first, i));
}
}
}
void solve(){
cin >> n;
FOR(i, 1, n){
cin >> h[i] >> a[i] >> b[i];
ok[M(i + a[i])].push_back(i);
ok[M(i + b[i]) + 1].push_back(-i);
}
cin >> q;
FOR(i, 1, q){
int l, r; cin >> l >> r;
res[i] = -1;
save[i] = make_pair(l, r);
query[r].push_back(make_pair(l, i));
}
process();
FOR(i, 1, n) h[i] *= -1;
process();
FOR(i, 1, q){
cout << res[i] << '\n';
}
}
#define task ""
int32_t main(){
if (fopen(task".inp","r")){
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
ios_base::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
solve();
return 0;
}
Compilation message (stderr)
antennas.cpp: In function 'int32_t main()':
antennas.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
123 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:124:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
124 | freopen(task".out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |