#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], T[200005], out[200005];
bool act[200005];
vector<int> toact[200005], todeact[200005];
vector<ii> qu[200005];
struct node {
node *left, *right;
int S, E, val, mi, mx, mip, mxp;
node(int _s, int _e) : S(_s), E(_e), val(-1), mi(1e16), mx(-1e16), mip(1e16), mxp(-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 || mip == 1e16) return;
left->mip = min(left->mip, mip);
left->mxp = max(left->mxp, mxp);
if (left->mi != 1e16) left->val = max({left->val, llabs(left->mi - left->mxp), llabs(left->mx - left->mip)});
right->mip = min(right->mip, mip);
right->mxp = max(right->mxp, mxp);
if (right->mi != 1e16) right->val = max({right->val, llabs(right->mi - right->mxp), llabs(right->mx - right->mip)});
mip = 1e16;
mxp = -1e16;
}
void upd(int l, int r, int v) {
if (l > E || r < S) return;
if (l <= S && E <= r) {
mxp = max(mxp, v);
mip = min(mip, v);
if (mi != 1e16) val = max({val, llabs(mxp - mi), llabs(mip - mx)});
return;
}
prop();
left->upd(l, r, v);
right->upd(l, r, v);
val = max(left->val, right->val);
}
void act(int p) {
if (S == E) {
mi = mx = H[p];
return;
}
prop();
int M = (S + E) >> 1;
if (p <= M) left->act(p);
else right->act(p);
mi = min(left->mi, right->mi);
mx = max(left->mx, right->mx);
}
void deact(int p) {
if (S == E) {
mi = 1e16;
mx = -1e16;
return;
}
prop();
int M = (S + E) >> 1;
if (p <= M) left->deact(p);
else right->deact(p);
mi = min(left->mi, right->mi);
mx = max(left->mx, right->mx);
}
int qry(int l, int r) {
if (l > E || r < S) return -1;
if (l <= S && E <= r) return val;
prop();
return max(left->qry(l, r), right->qry(l, r));
}
} *root;
main() {
memset(T, -1, sizeof T);
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
root = new node(1, 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);
}
for (int i = 1; i <= N; i++) {
for (auto j : toact[i]) root->act(j);
for (auto j : todeact[i]) root->deact(j);
root->upd(max(1ll, i - B[i]), max(1ll, i - A[i]), H[i]);
for (auto u : qu[i]) out[u.second] = root->qry(u.first, i);
if (i + A[i] <= N) toact[i + A[i]].pb(i);
if (i + B[i] + 1 <= N) todeact[i + B[i] + 1].pb(i);
}
for (int i = 1; i <= Q; i++) cout << out[i] << '\n';
}
Compilation message
antennas.cpp:99:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
99 | main() {
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
15948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
15948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
412 ms |
51796 KB |
Output is correct |
| 2 |
Correct |
473 ms |
60160 KB |
Output is correct |
| 3 |
Correct |
288 ms |
46884 KB |
Output is correct |
| 4 |
Correct |
463 ms |
60172 KB |
Output is correct |
| 5 |
Correct |
179 ms |
36144 KB |
Output is correct |
| 6 |
Correct |
495 ms |
60092 KB |
Output is correct |
| 7 |
Correct |
374 ms |
54244 KB |
Output is correct |
| 8 |
Incorrect |
440 ms |
60052 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
15948 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
