Submission #1138966

#TimeUsernameProblemLanguageResultExecution timeMemory
1138966VMaksimoski008Two Antennas (JOI19_antennas)C++20
100 / 100
603 ms59400 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; const ll inf = 1e18; struct segment_tree { int n; vector<ll> tree, mn, lazy; segment_tree(int _n) : n(_n), tree(4*n, -inf), lazy(4*n, -inf), mn(4*n, inf) {} void pull(int u, ll x) { tree[u] = max(tree[u], x - mn[u]); lazy[u] = max(lazy[u], x); } void push(int u, int tl, int tr) { if(lazy[u] == -inf) return ; if(tl != tr) { pull(2*u, lazy[u]); pull(2*u+1, lazy[u]); } lazy[u] = -inf; } void set_mn(int u, int tl, int tr, int p, ll v) { if(tl == tr) { mn[u] = v; } else { push(u, tl, tr); int tm = (tl + tr) / 2; if(p <= tm) set_mn(2*u, tl, tm, p, v); else set_mn(2*u+1, tm+1, tr, p, v); mn[u] = min(mn[2*u], mn[2*u+1]); } } void set_mx(int u, int tl, int tr, int l, int r, ll v) { if(tl > r || l > tr) return ; if(l <= tl && tr <= r) { pull(u, v); push(u, tl, tr); return ; } push(u, tl, tr); int tm = (tl + tr) / 2; set_mx(2*u, tl, tm, l, r, v); set_mx(2*u+1, tm+1, tr, l, r, v); tree[u] = max(tree[2*u], tree[2*u+1]); } ll query(int u, int tl, int tr, int l, int r) { if(tl > r || l > tr) return -inf; if(l <= tl && tr <= r) return tree[u]; push(u, tl, tr); int tm = (tl + tr) / 2; return max(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r)); } void set_mn(int p, ll v) { set_mn(1, 1, n, p, v); } void set_mx(int l, int r, ll v) { set_mx(1, 1, n, l, r, v); } ll query(int l, int r) { return query(1, 1, n, l, r); } }; signed main() { int n; cin >> n; vector<int> h(n+1), a(n+1), b(n+1), in[2*n+1], out[2*n+1]; for(int i=1; i<=n; i++) cin >> h[i] >> a[i] >> b[i]; int q; cin >> q; vector<ll> ans(q+1, -1); vector<pair<int, int> > qus[n+1]; for(int i=1; i<=q; i++) { int l, r; cin >> l >> r; qus[r].push_back({ l, i }); } for(int i=1; i<=n; i++) { in[i+a[i]].push_back(i); out[i+b[i]].push_back(i); } auto work = [&]() { segment_tree sgt(n); for(int i=1; i<=n; i++) { for(int id : in[i]) sgt.set_mn(id, h[id]); sgt.set_mx(i-b[i], i-a[i], h[i]); for(auto [j, id] : qus[i]) ans[id] = max(ans[id], sgt.query(j, i)); for(int id : out[i]) sgt.set_mn(id, 1e18); } }; work(); for(int i=1; i<=n; i++) h[i] *= -1; work(); for(int i=1; i<=q; i++) 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...