제출 #866969

#제출 시각아이디문제언어결과실행 시간메모리
866969lolismekTwo Antennas (JOI19_antennas)C++14
0 / 100
172 ms44908 KiB
#include <iostream> #include <vector> #define pii pair <int, int> using namespace std; const int NMAX = 2e5; const int INF = 1e9 + 10; // ? int n, q; int v[NMAX + 1]; pii ant[NMAX + 1]; pii quer[NMAX + 1]; vector <int> inds[NMAX + 1]; vector <pii> ev[NMAX + 1]; int qans[NMAX + 1]; namespace AINT{ struct Node{ int maxi, mini, diff, lazy; }seg[NMAX + 1]; Node Merge(Node l, Node r){ Node ans; ans.maxi = max(l.maxi, r.maxi); ans.mini = min(l.mini, r.mini); ans.diff = max(ans.maxi - ans.mini, max(l.diff, r.diff)); ans.lazy = +INF; return ans; } void propag(int node, int l, int r){ seg[node].mini = min(seg[node].mini, seg[node].lazy); seg[node].diff = max(seg[node].diff, seg[node].maxi - seg[node].mini); if(l < r){ seg[2 * node].lazy = min(seg[2 * node].lazy, seg[node].lazy); seg[2 * node + 1].lazy = min(seg[2 * node + 1].lazy, seg[node].lazy); } seg[node].lazy = +INF; } void build(int node, int l, int r){ if(l == r){ seg[node].maxi = -INF; seg[node].mini = +INF; seg[node].diff = seg[node].maxi - seg[node].mini; seg[node].lazy = +INF; return; } int mid = (l + r) / 2; build(2 * node, l, mid); build(2 * node + 1, mid + 1, r); seg[node] = Merge(seg[2 * node], seg[2 * node + 1]); } void updatemx(int node, int l, int r, int pos, int val){ propag(node, l, r); if(l == r){ seg[node].maxi = val; seg[node].mini = +INF; seg[node].diff = seg[node].maxi - seg[node].mini; return; } int mid = (l + r) / 2; if(pos <= mid){ updatemx(2 * node, l, mid, pos, val); }else{ updatemx(2 * node + 1, mid + 1, r, pos, val); } propag(2 * node, l, mid); propag(2 * node + 1, mid + 1, r); seg[node].maxi = max(seg[2 * node].maxi, seg[2 * node + 1].maxi); seg[node].diff = max(seg[2 * node].diff, seg[2 * node + 1].diff); } void updatemn(int node, int l, int r, int ul, int ur, int val){ propag(node, l, r); if(ul <= l && r <= ur){ seg[node].lazy = val; propag(node, l, r); return; } int mid = (l + r) / 2; if(ul <= mid){ updatemn(2 * node, l, mid, ul, ur, val); } if(mid + 1 <= ur){ updatemn(2 * node + 1, mid + 1, r, ul, ur, val); } propag(2 * node, l, mid); propag(2 * node + 1, mid + 1, r); //seg[node] = Merge(seg[2 * node], seg[2 * node + 1]); seg[node].diff = max(seg[2 * node].diff, seg[2 * node + 1].diff); } int query(int node, int l, int r, int ql, int qr){ propag(node, l, r); if(ql <= l && r <= qr){ return seg[node].diff; } int mid = (l + r) / 2, ans = -INF; if(ql <= mid){ ans = max(ans, query(2 * node, l, mid, ql, qr)); } if(mid + 1 <= qr){ ans = max(ans, query(2 * node + 1, mid + 1, r, ql, qr)); } return ans; } int querymaxi(int node, int l, int r, int ql, int qr){ propag(node, l, r); if(ql <= l && r <= qr){ return seg[node].maxi; } int mid = (l + r) / 2, ans = -INF; if(ql <= mid){ ans = max(ans, querymaxi(2 * node, l, mid, ql, qr)); } if(mid + 1 <= qr){ ans = max(ans, querymaxi(2 * node + 1, mid + 1, r, ql, qr)); } return ans; } } void solve(){ // clears for(int i = 1; i <= n; i++){ ev[i].clear(); inds[i].clear(); } for(int i = 1; i <= n; i++){ if(i + ant[i].first <= n){ ev[i + ant[i].first].push_back({i, +1}); } if(i + ant[i].second + 1 <= n){ ev[i + ant[i].second + 1].push_back({i, -1}); } } AINT::build(1, 1, n); for(int i = 1; i <= q; i++){ inds[quer[i].second].push_back(i); } for(int i = 1; i <= n; i++){ // process events for(pii e : ev[i]){ if(e.second == +1){ AINT::updatemx(1, 1, n, e.first, v[e.first]); }else{ AINT::updatemx(1, 1, n, i, -INF); } } // update with current element if(i - ant[i].first >= 1){ AINT::updatemn(1, 1, n, max(1, i - ant[i].second), i - ant[i].first, v[i]); } // answer queries for(int ind : inds[i]){ qans[ind] = max(qans[ind], AINT::query(1, 1, n, quer[ind].first, quer[ind].second)); } } } int main(){ cin >> n; for(int i = 1; i <= n; i++){ cin >> v[i]; cin >> ant[i].first >> ant[i].second; } cin >> q; for(int i = 1; i <= q; i++){ cin >> quer[i].first >> quer[i].second; qans[i] = -1; } solve(); // reverse for(int i = 1; i <= n / 2; i++){ swap(v[i], v[n - i + 1]); swap(ant[i], ant[n - i + 1]); } for(int i = 1; i <= q; i++){ quer[i].first = n - quer[i].first + 1; quer[i].second = n - quer[i].second + 1; swap(quer[i].first, quer[i].second); } solve(); for(int i = 1; i <= q; i++){ cout << qans[i] << '\n'; } return 0; } /* 5 10 2 4 1 1 1 2 1 3 1 1 1 100 1 1 5 1 2 2 3 1 3 1 4 1 5 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...