#include<bits/stdc++.h> using namespace std; void local() { #define taskname "" if (fopen(taskname".inp", "r")) { freopen(taskname".inp", "r", stdin); freopen(taskname".out", "w", stdout); } } #define ll long long #define fi first #define se second #define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0); template<class X, class Y> bool mini(X &a, const Y &b) {return (a > b) ? a = b, true : false;} template<class X, class Y> bool maxi(X &a, const Y &b) {return (a < b) ? a = b, true : false;} const int N = 2e5 + 5; int n; int h[N], a[N], b[N]; int q; pair<int, int> que[N]; namespace sub2 { bool check() { return n <= 2e3; } struct SegmentTree { using T = int; vector<T> st; int n; void init(int n_) { n = n_; st.assign((n + 5) << 2, -2e9 - 1); } void update(int x, int v, int l, int r, int id) { if(l > x || r < x) return; if(l == r) { maxi(st[id], v); return; } int mid = (l + r) >> 1; update(x, v, l, mid, id << 1); update(x, v, mid + 1, r, id << 1 | 1); st[id] = max(st[id << 1], st[id << 1 | 1]); } T get(int x, int y, int l, int r, int id) { if(l > y || r < x) return -2e9 - 1; if(l >= x && r <= y) return st[id]; int mid = (l + r) >> 1; return max(get(x, y, l, mid, id << 1), get(x, y, mid + 1, r, id << 1 | 1)); } }; vector<pair<int, int>> event[N]; bool isin(int i, int x, int y) { return x <= i && i <= y; } int ans[N]; void solve() { for(int i = 1; i <= q; i++) { auto[l, r] = que[i]; event[r].emplace_back(l, i); } SegmentTree T; T.init(n); for(int i = 1; i <= n; i++) { for(int j = 1; j < i; j++) { if(isin(abs(i - j), a[j], b[j]) && isin(abs(i - j), a[i], b[i])) { T.update(j, abs(h[i] - h[j]), 1, n, 1); } } for(auto[l, id] : event[i]) { ans[id] = T.get(l, i, 1, n, 1); } } for(int i = 1; i <= q; i++) cout << (ans[i] == -2e9 - 1 ? -1 : ans[i]) << '\n'; } } namespace sub3 { bool check() { return q == 1 && que[1].fi == 1 && que[1].se == n; } struct SegmentTree { using T = pair<int, int>; vector<T> st; int n; void init(int n_) { n = n_; st.assign((n + 5) << 2, make_pair(-1, -1)); } T merge(T a, T b) { T c; if(a.fi == -1) return b; if(b.fi == -1) return a; c.fi = min(a.fi, b.fi); c.se = max(a.se, b.se); return c; } void update(int x, int v, int l, int r, int id) { if(l > x || r < x) return; if(l == r) { st[id].fi = v; st[id].se = v; return; } int mid = (l + r) >> 1; update(x, v, l, mid, id << 1); update(x, v, mid + 1, r, id << 1 | 1); st[id] = merge(st[id << 1], st[id << 1 | 1]); } T get(int x, int y, int l, int r, int id) { if(l > y || r < x) return make_pair(-1, -1); if(l >= x && r <= y) return st[id]; int mid = (l + r) >> 1; return merge(get(x, y, l, mid, id << 1), get(x, y, mid + 1, r, id << 1 | 1)); } }; vector<pair<int, int>> event[N]; int res = -1; void solve() { for(int i = 1; i <= n; i++) { event[max(0, i - b[i])].emplace_back(i, 1); event[max(0, i - a[i] + 1)].emplace_back(i, -1); event[min(n + 1, i + a[i])].emplace_back(i, 1); event[min(n + 1, i + b[i] + 1)].emplace_back(i, -1); } SegmentTree T; T.init(n); for(int i = 1; i <= n; i++) { for(auto[id, t] : event[i]) { if(t == 1) { T.update(id, h[id], 1, n, 1); } else { T.update(id, -1, 1, n, 1); } } pair<int, int> cur = T.get(max(1, i - b[i]), max(0, i - a[i]), 1, n, 1); if(cur.fi == -1) continue; maxi(res, h[i] - cur.fi); maxi(res, cur.se - h[i]); } cout << res; } } namespace sub4 { struct NODE { int val, lb, ub; NODE() { val = -2e9; lb = 1e9 + 1; ub = -1; } } st[N << 2]; void re_update(int id) { maxi(st[id].val, st[id].ub - st[id].lb); } void down(int id) { maxi(st[id << 1].ub, st[id].ub); re_update(id << 1); maxi(st[id << 1 | 1].ub, st[id].ub); re_update(id << 1 | 1); st[id].ub = 0; } void update_point(int x, int v, int l, int r, int id) { if(l > x || r < x) return; if(l == r) { st[id].lb = v; st[id].ub = -1; re_update(id); return; } int mid = (l + r) >> 1; down(id); update_point(x, v, l, mid, id << 1); update_point(x, v, mid + 1, r, id << 1 | 1); st[id].lb = min(st[id << 1].lb, st[id << 1 | 1].lb); st[id].val = max(st[id << 1].val, st[id << 1 | 1].val); re_update(id); } void update_ran(int x, int y, int v, int l, int r, int id) { if(l > y || r < x) return; if(l >= x && r <= y) { maxi(st[id].ub, v); re_update(id); return; } int mid = (l + r) >> 1; down(id); update_ran(x, y, v, l, mid, id << 1); update_ran(x, y, v, mid + 1, r, id << 1 | 1); st[id].val = max(st[id << 1].val, st[id << 1 | 1].val); re_update(id); } int get(int x, int y, int l, int r, int id) { if(l > y || r < x) return -1; if(l >= x && r <= y) { return st[id].val; } int mid = (l + r) >> 1; down(id); return max(get(x, y, l, mid, id << 1), get(x, y, mid + 1, r, id << 1 | 1)); } int ans[N]; vector<pair<int, int>> event[N]; vector<pair<int, int>> event_que[N]; void onward() { for(int i = 1; i < (N << 2); i++) st[i] = NODE(); for(int i = 0; i <= n + 1; i++) event[i].clear(), event_que[i].clear(); for(int i = 1; i <= q; i++) { auto[l, r] = que[i]; event_que[r].emplace_back(l, i); } for(int i = 1; i <= n; i++) { event[max(1, i - b[i])].emplace_back(i, 1); event[max(1, i - a[i] + 1)].emplace_back(i, 0); event[min(n + 1, i + a[i])].emplace_back(i, 1); event[min(n + 1, i + b[i] + 1)].emplace_back(i, 0); } for(int i = 1; i <= n; i++) { for(auto[id, t] : event[i]) { if(t) { update_point(id, h[id], 1, n, 1); } else { update_point(id, 1e9 + 1, 1, n, 1); } } update_ran(max(1, i - b[i]), max(0, i - a[i]), h[i], 1, n, 1); for(auto[l, id] : event_que[i]) { maxi(ans[id], get(l, i, 1, n, 1)); } } } void backward() { for(int i = 1; i < (N << 2); i++) st[i] = NODE(); for(int i = 0; i <= n + 1; i++) event[i].clear(), event_que[i].clear(); for(int i = 1; i <= q; i++) { auto[l, r] = que[i]; event_que[l].emplace_back(r, i); } for(int i = 1; i <= n; i++) { event[max(0, i - a[i])].emplace_back(i, 1); event[max(0, i - b[i] - 1)].emplace_back(i, 0); } for(int i = n; i > 0; i--) { for(auto[id, t] : event[i]) { cout << i << ' ' << id << ' ' << t << '\n'; if(t) { update_point(id, h[id], 1, n, 1); } else { update_point(id, 1e9 + 1, 1, n, 1); } } update_ran(min(n + 1, i + a[i]), min(n, i + b[i]), h[i], 1, n, 1); for(auto[r, id] : event_que[i]) { maxi(ans[id], get(i, r, 1, n, 1)); } } } void solve() { memset(ans, -1, sizeof(ans)); onward(); backward(); for(int i = 1; i <= q; i++) cout << ans[i] << '\n'; } } int main() { fastio; local(); cin >> n; for(int i = 1; i <= n; i++) { cin >> h[i] >> a[i] >> b[i]; } cin >> q; for(int i = 1; i <= q; i++) { int l, r; cin >> l >> r; que[i] = make_pair(l, r); } sub4::solve(); }

antennas.cpp: In function 'void local()':
antennas.cpp:7:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 |         freopen(taskname".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
antennas.cpp:8:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 |         freopen(taskname".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~