Submission #1150191

#TimeUsernameProblemLanguageResultExecution timeMemory
1150191cot7302Two Antennas (JOI19_antennas)C++20
0 / 100
182 ms21784 KiB
#include <bits/stdc++.h> #define ALL(X) begin(X), end(X) using i64 = long long; using namespace std; template <class T> using vec = vector<T>; template <class T> istream& operator>>(istream& is, vec<T>& X) { for (auto& x : X) { is >> x; } return is; } template <class T> constexpr T infty = 0; template <> constexpr int infty<int> = 1'000'000'000; template <> constexpr i64 infty<i64> = 1'000'000'000'000'000'000; template <class AM> struct Seg { using A = typename AM::Act; using M = typename AM::Monoid; using G = typename A::value_type; using T = typename M::value_type; int N, log; vec<G> tg; vec<T> tr; Seg(int N) : N(N), log(__lg(N) + 1), tg(N, A::unit()), tr(N * 2, M::unit()) {} void __apply(int i, const G& t) { tr[i] = AM::act(tr[i], t); if (i < N) { tg[i] = A::op(tg[i], t); } } void push(int id) { id += N; for (int h = log; h > 0; h--) { int i = id >> h; if (tg[i] != A::unit()) { __apply(i * 2 + 0, tg[i]); __apply(i * 2 + 1, tg[i]); tg[i] = A::unit(); } } } void pull(int i) { for (i += N; i /= 2; ) { tr[i] = M::op(tr[i * 2 + 0], tr[i * 2 + 1]); if (tg[i] != A::unit()) { tr[i] = AM::act(tr[i], tg[i]); } } } void set(int i, const T& X) { push(i); tr[i + N] = X; pull(i); } void apply(int l, int r, const G& t) { if (l >= r) { return; } int il = l, ir = r; push(il), push(ir - 1); for (l += N, r += N; l < r; l /= 2, r /= 2) { if (l & 1) __apply(l++, t); if (r & 1) __apply(--r, t); } pull(il), pull(ir - 1); } T query(int l, int r) { if (l >= r) { return M::unit(); } push(l), push(r - 1); T ret_l{M::unit()}, ret_r{M::unit()}; for (l += N, r += N; l < r; l /= 2, r /= 2) { if (l & 1) ret_l = M::op(ret_l, tr[l++]); if (r & 1) ret_r = M::op(tr[--r], ret_r); } return M::op(ret_l, ret_r); } }; struct AM { struct Act { using value_type = int; static int unit() { return -infty<int> - 8888; } static int op(int l, int r) { return max(l, r); } }; struct Monoid { using value_type = pair<int, int>; static pair<int, int> unit() { return {-infty<int>, infty<int> + 888888}; } static pair<int, int> op(const pair<int, int>& l, const pair<int, int>& r) { return {max(l.first, r.first), min(l.second, r.second)}; } }; static pair<int, int> act(const pair<int, int>& l, int r) { return {max(l.first, r - l.second), l.second}; } }; void calc(int N, const vec<int>& H, const vec<int>& A, const vec<int>& B, const vec<vec<int>>& add, const vec<vec<int>>& del, const vec<vec<pair<int, int>>>& qq, vec<int>& ans) { Seg<AM> seg(N); for (int i = 0; i < N; i++) { for (auto j : add[i]) { seg.set(j, {-infty<int>, H[j]}); } for (auto j : del[i]) { seg.set(j, {-infty<int>, infty<int> + 888888}); } seg.apply(max(0, i - B[i]), max(0, i - A[i] + 1), H[i]); for (auto [l, id] : qq[i]) { ans[id] = max(ans[id], seg.query(l, i + 1).first); } } } int main() { cin.tie(nullptr)->sync_with_stdio(false); int N; cin >> N; vec<int> H(N), A(N), B(N); vec<vec<int>> add(N), del(N); for (int i = 0; i < N; i++) { cin >> H[i] >> A[i] >> B[i]; if (i + A[i] < N) { add[i + A[i]].emplace_back(i); } if (i + B[i] + 1 < N) { del[i + B[i] + 1].emplace_back(i); } } int Q; cin >> Q; vec<vec<pair<int, int>>> qq(N); vec<int> ans(Q, -infty<int>); for (int i = 0; i < Q; i++) { int l, r; cin >> l >> r; l -= 1, r -= 1; qq[r].emplace_back(l, i); } calc(N, H, A, B, add, del, qq, ans); for (auto& h : H) { h = infty<int> + 1 -h; } calc(N, H, A, B, add, del, qq, ans); for (int i = 0; i < Q; i++) { if (ans[i] < 0) { cout << "-1\n"; } else { cout << ans[i] << '\n'; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...