이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// #pragma GCC optimize("O3,unroll-loops,inline,no-stack-protector")
// #pragma GCC target("avx,avx2,sse3,ssse3,sse4.1,sse4.2,fma,bmi2,abm,popcnt,mmx,tune=native")
#include <bits/stdc++.h>
using namespace std;
#define trace(x) cerr << #x << ": " << (x) << endl;
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
using ll = long long;
#define int ll
constexpr int INF = numeric_limits<int>::max() / 2;
struct node {
int h, a, b;
};
void solve() {
int n;
cin >> n;
vector<node> v(n);
for (auto& i : v)
cin >> i.h >> i.a >> i.b;
vector<vector<int>> pref(n, vector<int>(n, -1));
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j)
if (v[i].a + i <= j && v[i].b + i >= j && j - v[j].a >= i && j - v[j].b <= i)
pref[n - i - 1][j] = abs(v[i].h - v[j].h);
for (int i = 1; i < n; ++i)
pref[i][0] = max(pref[i][0], pref[i - 1][0]), pref[0][i] = max(pref[0][i], pref[0][i - 1]);
for (int i = 1; i < n; ++i)
for (int j = 1; j < n; ++j)
pref[i][j] = max(pref[i][j], max(pref[i - 1][j], pref[i][j - 1]));
int q;
cin >> q;
while (q--) {
int l, r;
cin >> l >> r;
--l, --r;
cout << pref[n - l - 1][r] << '\n';
}
}
signed main() {
#ifdef LOCAL
freopen("input.in", "r", stdin);
#else
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int t = 1;
// cin >> t;
while (t--)
solve();
#ifdef LOCAL
cerr << '\n' << "time = " << clock() * 1.0 / CLOCKS_PER_SEC << '\n';
#endif
return 0;
}
# | 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... |