#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
#define int long long
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define ppb pop_back
#define eb emplace_back
#define g0(a) get<0>(a)
#define g1(a) get<1>(a)
#define g2(a) get<2>(a)
#define g3(a) get<3>(a)
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef double db;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
int N, Q, H[200005], A[200005], B[200005], out[200005];
vector<int> add[200005], del[200005];
vector<ii> qu[200005];
struct node {
node *left, *right;
int S, E, mx, mi, mxv, miv, val;
bool ip;
node(int _s, int _e) : S(_s), E(_e), val(-1e16), ip(0) {
mx = mxv = -1e16;
mi = miv = 1e16;
if (S == E) return;
int M = (S + E) >> 1;
left = new node(S, M);
right = new node(M + 1, E);
}
void prop() {
if (S == E || !ip) return;
left->mxv = max(left->mxv, mxv);
left->miv = min(left->miv, miv);
right->mxv = max(right->mxv, mxv);
right->miv = min(right->miv, miv);
if (left->mi != 1e16 && left->miv != 1e16) left->val = max({left->val, llabs(left->mi - left->mxv), llabs(left->mx - left->miv)});
if (right->mi != 1e16 && right->miv != 1e16) right->val = max({right->val, llabs(right->mi - right->mxv), llabs(right->mx - right->miv)});
ip = 0;
mxv = -1e16;
miv = 1e16;
}
void set(int p) {
if (S == E) {
mx = mi = H[S];
mxv = -1e16;
miv = 1e16;
return;
}
int M = (S + E) >> 1;
prop();
if (p <= M) left->set(p);
else right->set(p);
mx = max(left->mx, right->mx);
mi = min(left->mi, right->mi);
val = max(left->val, right->val);
}
void unset(int p) {
if (S == E) {
mx = mxv = -1e16;
mi = miv = 1e16;
return;
}
int M = (S + E) >> 1;
prop();
if (p <= M) left->unset(p);
else right->unset(p);
mx = max(left->mx, right->mx);
mi = min(left->mi, right->mi);
val = max(left->val, right->val);
}
void upd(int l, int r, int v) {
if (l > E || r < S) return;
if (l <= S && E <= r) {
mxv = max(mxv, v);
miv = min(miv, v);
if (mi != 1e16) val = max({val, llabs(mi - mxv), llabs(mx - miv)});
ip = 1;
return;
}
prop();
left->upd(l, r, v);
right->upd(l, r, v);
mx = max(left->mx, right->mx);
mi = min(left->mi, right->mi);
val = max(left->val, right->val);
}
int qry(int l, int r) {
if (l > E || r < S) return -1e16;
if (l <= S && E <= r) return val;
prop();
return max(left->qry(l, r), right->qry(l, r));
}
} *root;
main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
for (int i = 1; i <= N; i++) cin >> H[i] >> A[i] >> B[i];
cin >> Q;
for (int i = 1, l, r; i <= Q; i++) {
cin >> l >> r;
qu[r].eb(l, i);
}
root = new node(1, N);
for (int i = 1; i <= N; i++) {
for (auto j : del[i]) root->unset(j);
for (auto j : add[i]) root->set(j);
root->upd(max(1ll, i - B[i]), max(1ll, i - A[i]), H[i]);
for (auto j : qu[i]) {
out[j.second] = root->qry(j.first, i);
}
if (i + A[i] <= N) add[i + A[i]].pb(i);
if (i + B[i] + 1 <= N) del[i + B[i] + 1].pb(i);
}
for (int i = 1; i <= Q; i++) cout << (out[i] == -1e16 ? -1 : out[i]) << '\n';
}
Compilation message
antennas.cpp:109:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
109 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
382 ms |
59736 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
14412 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
