제출 #112587

#제출 시각아이디문제언어결과실행 시간메모리
112587KCSCTwo Antennas (JOI19_antennas)C++14
0 / 100
500 ms26872 KiB
#include <bits/stdc++.h> using namespace std; const int DIM = 200005; const int INF = 1000000007; int sgt1[DIM << 2], sgt2[DIM << 2], lzy[DIM << 2], ans[DIM]; vector<int> upd[DIM], lst[DIM]; struct Antenna { int h, a, b; } arr[DIM]; struct Query { int l, r; } qry[DIM]; void updateLazy(int nd, int le, int ri) { sgt2[nd] = max(sgt2[nd], lzy[nd] - sgt1[nd]); if (le != ri) { lzy[nd << 1] = max(lzy[nd << 1], lzy[nd]); lzy[nd << 1 | 1] = max(lzy[nd << 1 | 1], lzy[nd]); } lzy[nd] = 0; } void build(int nd, int le, int ri) { sgt1[nd] = INF; sgt2[nd] = -1; lzy[nd] = 0; if (le != ri) { int md = (le + ri) >> 1; build(nd << 1, le, md); build(nd << 1 | 1, md + 1, ri); } } void update1(int nd, int le, int ri, int ps, int vl) { updateLazy(nd, le, ri); if (le == ri) { sgt1[nd] = vl; } else { int md = (le + ri) >> 1; if (ps <= md) { update1(nd << 1, le, md, ps, vl); } else { update1(nd << 1 | 1, md + 1, ri, ps, vl); } sgt1[nd] = min(sgt1[nd << 1], sgt1[nd << 1 | 1]); } } void update2(int nd, int le, int ri, int st, int en, int vl) { updateLazy(nd, le, ri); if (st <= le and ri <= en) { lzy[nd] = max(lzy[nd], vl); updateLazy(nd, le, ri); } else { int md = (le + ri) >> 1; if (st <= md) { update2(nd << 1, le, md, st, en, vl); } if (md < en) { update2(nd << 1 | 1, md + 1, ri, st, en, vl); } sgt2[nd] = max(sgt2[nd << 1], sgt2[nd << 1 | 1]); } } int query(int nd, int le, int ri, int st, int en) { updateLazy(nd, le, ri); if (st <= le and ri <= en) { return sgt2[nd]; } else { int md = (le + ri) >> 1; if (en <= md) { return query(nd << 1, le, md, st, en); } else if (md < st) { return query(nd << 1 | 1, md + 1, ri, st, en); } else { return max(query(nd << 1, le, md, st, en), query(nd << 1 | 1, md + 1, ri, st, en)); } } } int main(void) { #ifdef HOME freopen("antennas.in", "r", stdin); freopen("antennas.out", "w", stdout); #endif int N; cin >> N; for (int i = 1; i <= N; ++i) { cin >> arr[i].h >> arr[i].a >> arr[i].b; } int Q; cin >> Q; for (int i = 1; i <= Q; ++i) { cin >> qry[i].l >> qry[i].r; ans[i] = -1; } for (int g = 1; g <= 2; ++g) { for (int i = 1; i <= N; ++i) { if (i + arr[i].a <= N) { upd[i + arr[i].a].push_back(i); } if (i + arr[i].b < N) { upd[i + arr[i].b + 1].push_back(-i); } } for (int i = 1; i <= Q; ++i) { lst[qry[i].r].push_back(i); } build(1, 1, N); for (int i = 1; i <= N; ++i) { for (int x : upd[i]) { if (x > 0) { update1(1, 1, N, x, arr[x].h); } else { update1(1, 1, N, x, INF); } } if (i - arr[i].a >= 1) { update2(1, 1, N, max(1, i - arr[i].b), i - arr[i].a, arr[i].h); } for (int x : lst[i]) { ans[x] = max(ans[x], query(1, 1, N, qry[x].l, qry[x].r)); } } for (int i = 1; i <= N; ++i) { upd[i].clear(); lst[i].clear(); } for (int i = 1, j = N; i <= j; ++i, --j) { swap(arr[i], arr[j]); } for (int i = 1; i <= Q; ++i) { qry[i] = {N - qry[i].r + 1, N - qry[i].l + 1}; } } for (int i = 1; i <= Q; ++i) { cout << ans[i] << "\n"; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...