#include <iostream>
#include <vector>
#include <algorithm>
#include <random>
#include <iomanip>
#include <cassert>
#include <deque>
#include <functional>
#include <set>
#include <queue>
#include <unordered_map>
#include <map>
#include <iomanip>
#include <complex>
#define int long long
using namespace std;
struct antenna {
int a, b, h;
antenna() {}
antenna(int a, int b, int h): a(a), b(b), h(h) {}
};
int n;
const int maxn = 100;
const int inf = 1e15;
vector<antenna> a;
int tree[maxn * 4];
int mn[maxn * 4];
int smn[maxn * 4];
int mnVal[maxn * 4];
int h[maxn];
void init() {
fill(tree, tree + maxn * 4, -inf * 2);
fill(mn, mn + maxn * 4, -inf);
fill(smn, smn + maxn * 4, inf);
fill(mnVal, mnVal + maxn * 4, inf);
fill(h, h + maxn, inf);
}
void tag(int i, int x) {
tree[i] = max(tree[i], x - mnVal[i]);
mn[i] = max(x, mn[i]);
}
void push(int i) {
tag(i * 2 + 1, mn[i]);
tag(i * 2 + 2, mn[i]);
}
void merge(int i, int l, int r) {
tree[i] = max({ tree[i], tree[l], tree[r] });
mn[i] = min(mn[l], mn[r]);
mnVal[i] = min(mnVal[l], mnVal[r]);
smn[i] = min(smn[l], smn[r]);
if (mn[l] != mn[r]) {
smn[i] = min(smn[i], max(mn[l], mn[r]));
}
}
void chmax(int i, int l, int r, int ql, int qr, int x) {
if (qr <= l || r <= ql || mn[i] >= x) {
return;
}
if (ql <= l && r <= qr && smn[i] > x) {
tag(i, x);
return;
}
int m = (l + r) / 2;
push(i);
chmax(i * 2 + 1, l, m, ql, qr, x);
chmax(i * 2 + 2, m, r, ql, qr, x);
merge(i, i * 2 + 1, i * 2 + 2);
}
void setinf(int i, int l, int r, int qi) {
if (qi < l || r <= qi) {
return;
}
if (l + 1 == r) {
mn[i] = -inf;
return;
}
int m = (l + r) / 2;
push(i);
setinf(i * 2 + 1, l, m, qi);
setinf(i * 2 + 2, m, r, qi);
merge(i, i * 2 + 1, i * 2 + 2);
}
void updval(int i, int l, int r, int qi, int x) {
if (qi < l || r <= qi) {
return;
}
if (l + 1 == r) {
tree[i] = max(tree[i], mn[i] - x);
mnVal[i] = x;
return;
}
int m = (l + r) / 2;
push(i);
updval(i * 2 + 1, l, m, qi, x);
updval(i * 2 + 2, m, r, qi, x);
merge(i, i * 2 + 1, i * 2 + 2);
}
void enable(int j) {
h[j] = a[j].h;
setinf(0, 0, n, j);
updval(0, 0, n, j, h[j]);
}
void disable(int j) {
h[j] = inf;
updval(0, 0, n, j, h[j]);
}
int get(int i, int l, int r, int ql, int qr) {
if (qr <= l || r <= ql) {
return -2;
}
if (ql <= l && r <= qr) {
return tree[i];
}
int m = (l + r) / 2;
push(i);
int res = max(get(i * 2 + 1, l, m, ql, qr), get(i * 2 + 2, m, r, ql, qr));
merge(i, i * 2 + 1, i * 2 + 2);
return res;
}
int32_t main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
a.resize(n);
for (int i = 0; i < n; ++i) {
int x, y, h;
cin >> h >> x >> y;
a[i] = antenna(x, y, h);
}
vector<vector<pair<int, int>>> queries(n + 1);
int q;
cin >> q;
vector<int> ans(q, -1);
for (int i = 0; i < q; ++i) {
int l, r;
cin >> l >> r;
queries[r - 1].push_back({ l - 1, i });
}
auto solve = [&] {
init();
vector<vector<int>> add(n + 1);
vector<vector<int>> del(n + 1);
for (int i = 0; i < n; ++i) {
add[min(i + a[i].a, n)].push_back(i);
del[min(i + a[i].b + 1, n)].push_back(i);
for (int j : add[i]) {
enable(j);
}
for (int j : del[i]) {
disable(j);
}
int L = max(0ll, i - a[i].b);
int R = max(0ll, i - a[i].a + 1);
chmax(0, 0, n, L, R, a[i].h);
for (auto [l, j] : queries[i]) {
ans[j] = max(ans[j], get(0, 0, n, l, i + 1));
}
}
};
solve();
for (int i = 0; i < n; ++i) {
a[i].h *= -1;
}
solve();
for (int i : ans) {
cout << i << '\n';
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
74 ms |
34760 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
0 ms |
340 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 11 |
| 3 |
Halted |
0 ms |
0 KB |
- |
