#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define MAX 200100
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
struct node {
ll mxval, mnval;
ll ans;
node() {
mxval = mnval = ans = -1;
}
};
node operator+(const node& n1, const node& n2) {
node ret;
ret.mnval = n1.mnval == -1 ? n2.mnval : (n2.mnval == -1 ? n1.mnval : min(n1.mnval, n2.mnval));
ret.mxval = max(n1.mxval, n2.mxval);
ret.ans = max(n1.ans, n2.ans);
return ret;
}
struct segtree {
ll N, s;
vector<node> tree;
vector<ll> l, r;
vector<ll> lmx, lmn; //lazy max min
void init(ll x = 1) {
if (x >= s) {
l[x] = r[x] = x - s + 1;
return;
}
init(x * 2);
init(x * 2 + 1);
l[x] = l[x * 2];
r[x] = r[x * 2 + 1];
}
segtree() {}
segtree(ll N) {
segtree::N = N;
s = 1LL << (ll)ceil(log2(N));
tree.resize(2 * s + 1);
l.resize(2 * s + 1);
r.resize(2 * s + 1);
lmx.resize(2 * s + 1, -1);
lmn.resize(2 * s + 1, -1);
init();
}
void prop(ll loc) {
if (loc >= s) return;
lmx[loc * 2] = max(lmx[loc * 2], lmx[loc]);
lmx[loc * 2 + 1] = max(lmx[loc * 2 + 1], lmx[loc]);
if (lmx[loc] != -1) lmn[loc * 2] = min(lmn[loc * 2], lmn[loc]);
if (lmx[loc] != -1) lmn[loc * 2 + 1] = min(lmn[loc * 2 + 1], lmn[loc]);
if (lmn[loc * 2] == -1) lmn[loc * 2] = lmn[loc];
if (lmn[loc * 2 + 1] == -1) lmn[loc * 2 + 1] = lmn[loc];
ll res = -1;
if (tree[loc * 2].mxval != -1 && lmx[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mxval - lmx[loc * 2]));
if (tree[loc * 2].mxval != -1 && lmn[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mxval - lmn[loc * 2]));
if (tree[loc * 2].mnval != -1 && lmx[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mnval - lmx[loc * 2]));
if (tree[loc * 2].mnval != -1 && lmn[loc * 2] != -1) res = max(res, abs(tree[loc * 2].mnval - lmn[loc * 2]));
tree[loc * 2].ans = max(tree[loc * 2].ans, res);
res = -1;
if (tree[loc * 2 + 1].mxval != -1 && lmx[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mxval - lmx[loc * 2 + 1]));
if (tree[loc * 2 + 1].mxval != -1 && lmn[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mxval - lmn[loc * 2 + 1]));
if (tree[loc * 2 + 1].mnval != -1 && lmx[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mnval - lmx[loc * 2 + 1]));
if (tree[loc * 2 + 1].mnval != -1 && lmn[loc * 2 + 1] != -1) res = max(res, abs(tree[loc * 2 + 1].mnval - lmn[loc * 2 + 1]));
tree[loc * 2 + 1].ans = max(tree[loc * 2 + 1].ans, res);
lmx[loc] = lmn[loc] = -1;
}
void update(ll low, ll high, ll h, ll loc = 1) {
prop(loc);
if (high == 0) return;
low = max(1LL, low);
if (tree[loc].mnval == -1) return;
prop(loc);
if (low == l[loc] && high == r[loc]) {
lmx[loc] = max(lmx[loc], h);
lmn[loc] = min(lmn[loc], h);
if (lmn[loc] == -1) lmn[loc] = h;
ll res = 0;
if (tree[loc].mnval != -1) res = max(res, abs(h - tree[loc].mnval));
if (tree[loc].mxval != -1) res = max(res, abs(h - tree[loc].mxval));
tree[loc].ans = max(tree[loc].ans, res);
return;
}
if (high <= r[loc * 2]) update(low, high, h, loc * 2);
else if (low >= l[loc * 2 + 1]) update(low, high, h, loc * 2 + 1);
else update(low, r[loc * 2], h, loc * 2), update(l[loc * 2 + 1], high, h, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
void togle(ll x, ll v, ll loc = 1) {
prop(loc);
if (l[loc] == r[loc]) {
tree[loc].mnval = tree[loc].mxval = v;
return;
}
if (x <= r[loc * 2]) togle(x, v, loc * 2);
else togle(x, v, loc * 2 + 1);
tree[loc] = tree[loc * 2] + tree[loc * 2 + 1];
}
ll query(ll low, ll high, ll loc = 1) {
prop(loc);
if (low == l[loc] && high == r[loc]) return tree[loc].ans;
if (high <= r[loc * 2]) return query(low, high, loc * 2);
if (low >= l[loc * 2 + 1]) return query(low, high, loc * 2 + 1);
return max(query(low, r[loc * 2], loc * 2), query(l[loc * 2 + 1], high, loc * 2 + 1));
}
};
struct query {
ll l, r;
ll ind;
query() {}
query(ll l, ll r, ll ind) :l(l), r(r), ind(ind) {}
};
vector<query> qarr[MAX];
vector<ll> on[MAX], off[MAX];
ll ans[MAX];
ll H[MAX];
ll l[MAX], r[MAX];
signed main() {
ios::sync_with_stdio(false), cin.tie(0);
ll N;
cin >> N;
ll i;
ll a, b;
for (i = 1; i <= N; i++) {
cin >> H[i] >> a >> b;
l[i] = max(i - b, 0LL);
r[i] = max(i - a, 0LL);
on[min(N + 1, i + a)].push_back(i);
off[min(N + 1, i + b + 1)].push_back(i);
}
ll Q;
cin >> Q;
for (i = 1; i <= Q; i++) {
cin >> a >> b;
qarr[b].push_back(query(a, b, i));
}
segtree seg(N);
for (i = 1; i <= N; i++) {
for (auto x : on[i]) seg.togle(x, H[x]);
for (auto x : off[i]) seg.togle(x, -1);
seg.update(l[i], r[i], H[i]);
for (auto q : qarr[i]) ans[q.ind] = seg.query(q.l, i);
}
for (i = 1; i <= Q; i++) cout << ans[i] << ln;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
655 ms |
52932 KB |
Output is correct |
| 2 |
Correct |
748 ms |
53916 KB |
Output is correct |
| 3 |
Correct |
456 ms |
50524 KB |
Output is correct |
| 4 |
Correct |
734 ms |
53924 KB |
Output is correct |
| 5 |
Correct |
319 ms |
35768 KB |
Output is correct |
| 6 |
Correct |
723 ms |
58456 KB |
Output is correct |
| 7 |
Correct |
710 ms |
56020 KB |
Output is correct |
| 8 |
Incorrect |
739 ms |
58460 KB |
Output isn't correct |
| 9 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
14404 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
