#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto& a : (b))
#define repIn2(a, b, c) for(auto& [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
constexpr int maxLog = 12;
int main() {
ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
int n, q;
cin >> n;
vector<int> h(n), a(n), b(n);
rep(i, 0, n) cin >> h[i] >> a[i] >> b[i];
if(n <= 2000) {
int st[n][n][maxLog];
repIn(i, st) repIn(ii, i) repIn(iii, ii) iii = -1;
rep(i, 0, n - 1) rep(j, i + 1, n) {
if(a[i] + i > j || b[i] + i < j) continue;
if(j - a[j] < i || j - b[j] > i) continue;
st[i][j][0] = st[j][i][0] = abs(h[i] - h[j]);
DC << i << ' ' << j << ' ' << st[i][j][0] << eol;;
}
rep(k, 1, maxLog) rep(i, 0, n) rep(j, 0, n) {
int i1 = min(n - 1, i + (1 << (k - 1)));
int j1 = min(n - 1, j + (1 << (k - 1)));
st[i][j][k] = max(max(st[i][j][k - 1], st[i][j1][k - 1]), max(st[i1][j][k - 1], st[i1][j1][k - 1]));
}
int l, r;
cin >> q;
rep(i, 0, q) {
cin >> l >> r;
l--; r--;
int k = 31 - __builtin_clz(r - l + 1);
int r1 = r - (1 << k) + 1;
int ans =max(max(st[l][l][k], st[l][r1][k]), max(st[r1][l][k], st[r1][r1][k]));
cout << ans << '\n';
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |