제출 #604305

#제출 시각아이디문제언어결과실행 시간메모리
604305GusterGoose27Two Antennas (JOI19_antennas)C++11
2 / 100
608 ms418924 KiB
#pragma GCC optimize("Ofast") #pragma GCC target("avx2") #include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; const int MAXN = 2e5; const int inf = 1e9; const int bsize = 447; const int MAX_blocks = 447; pii valid_dists[MAXN]; int height[MAXN]; bool active[MAXN]; vector<int> toggle_l[MAXN]; // actual station is to the left vector<int> toggle_r[MAXN]; // station to the right vector<pii> lqueries[MAXN]; vector<pii> rqueries[MAXN]; vector<pii> lans[MAXN]; vector<pii> rans[MAXN]; pii act_queries[MAXN]; int t1[MAXN]; int t2[MAXN]; int bsize_precomp[MAX_blocks][MAX_blocks]; int num_blocks = 0; bool f = 0; int n, q; class stree { public: int mn = inf; int mx = 0; stree *l = nullptr; stree *r = nullptr; int lp, rp; stree(int lv, int rv) { lp = lv; rp = rv; if (lp == rp) { if (active[lp]) { mn = height[lp]; mx = height[lp]; } } else { int m = (lp+rp)/2; l = new stree(lp, m); r = new stree(m+1, rp); mn = min(l->mn, r->mn); mx = max(l->mx, r->mx); } } stree(stree *lt, stree *rt) { l = lt; r = rt; mn = min(l->mn, r->mn); mx = max(l->mx, r->mx); lp = l->lp; rp = r->rp; } int mx_in_range(int lv, int rv) { if (lp > rv || rp < lv) return 0; if (lp >= lv && rp <= rv) return mx; return max(l->mx_in_range(lv, rv), r->mx_in_range(lv, rv)); } int mn_in_range(int lv, int rv) { if (lp > rv || rp < lv) return inf; if (lp >= lv && rp <= rv) return mn; return min(l->mn_in_range(lv, rv), r->mn_in_range(lv, rv)); } pii diff_in_range(int lv, int rv) { if (lp > rv || rp < lv) return pii(inf, 0); if (lp >= lv && rp <= rv) return pii(mn, mx); pii a = l->diff_in_range(lv, rv); pii b = r->diff_in_range(lv, rv); return pii(min(a.first, b.first), max(a.second, b.second)); } void update(int p) { if (lp > p || rp < p) return; if (lp == p && rp == p) { if (active[p]) { mn = height[lp]; mx = height[lp]; } else { mn = inf; mx = 0; } return; } l->update(p); r->update(p); mn = min(l->mn, r->mn); mx = max(l->mx, r->mx); } }; int mxdif_l(int i, int r) { if (r > i-valid_dists[i].first) return -1; pii p = lans[i][t1[i]++]; return max(height[i]-p.first, p.second-height[i]); } int mxdif_r(int i, int l) { if (l < i+valid_dists[i].first) return -1; pii p = rans[i][t2[i]++]; return max(height[i]-p.first, p.second-height[i]); } void make_ldif(int i, int r) { if (r > i-valid_dists[i].first) return; lqueries[i].emplace_back(pii(max(r, i-valid_dists[i].second), i-valid_dists[i].first)); } void make_rdif(int i, int l) { if (l < i+valid_dists[i].first) return; rqueries[i].emplace_back(pii(i+valid_dists[i].first, min(l, i+valid_dists[i].second))); } void solve() { for (int i = 0; i < num_blocks; i++) { for (int j = i; j < num_blocks; j++) { if (i == j) { int r = bsize*i; int best = -1; for (int k = bsize*i+1; k < bsize*(i+1); k++) { if (f) best = max(best, mxdif_l(k, r)); else make_ldif(k, r); } if (f) bsize_precomp[i][j] = best; continue; } if (f) bsize_precomp[i][j] = bsize_precomp[i][j-1]; int r = bsize*i; for (int k = bsize*j; k < bsize*(j+1); k++) { if (f) bsize_precomp[i][j] = max(bsize_precomp[i][j], mxdif_l(k, r)); else make_ldif(k, r); } } } for (int i = 0; i < q; i++) { int x = act_queries[i].first; int y = act_queries[i].second; int best = -1; int lv = (x-1)/bsize+1; if (x == 0) lv = 0; int rv = (y+1)/bsize-1; if (lv > rv) { for (int k = x+1; k <= y; k++) { if (f) best = max(best, mxdif_l(k, x)); else make_ldif(k, x); } if (f) cout << best << "\n"; continue; } if (f) best = bsize_precomp[lv][rv]; for (int k = x; k < lv*bsize; k++) { if (f) best = max(best, mxdif_r(k, y)); else make_rdif(k, y); } for (int k = y; k >= (rv+1)*bsize; k--) { if (best) best = max(best, mxdif_l(k, x)); else make_ldif(k, x); } if (f) cout << best << "\n"; } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n; num_blocks = n/bsize; for (int i = 0; i < n; i++) { int x, y; cin >> height[i] >> x >> y; valid_dists[i] = pii(x, y); if (x+i < n) toggle_l[x+i].push_back(i); if (i+y+1 < n) toggle_l[i+y+1].push_back(i); if (i-x >= 0) toggle_r[i-x].push_back(i); if (i-y-1 >= 0) toggle_r[i-y-1].push_back(i); } cin >> q; for (int i = 0; i < q; i++) { int x, y; cin >> x >> y; x--; y--; act_queries[i] = pii(x, y); } solve(); stree *cur_tree = new stree(0, n-1); for (int i = 0; i < n; i++) { for (int v: toggle_l[i]) { active[v] = 1-active[v]; cur_tree->update(v); } lans[i].resize(lqueries[i].size()); int t = 0; for (pii query: lqueries[i]) { lans[i][t++] = cur_tree->diff_in_range(query.first, query.second); } } fill(active, active+n, 0); cur_tree = new stree(0, n-1); for (int i = n-1; i >= 0; i--) { for (int v: toggle_r[i]) { active[v] = 1-active[v]; cur_tree->update(v); } rans[i].resize(rqueries[i].size()); int t = 0; for (pii query: rqueries[i]) { rans[i][t++] = cur_tree->diff_in_range(query.first, query.second); } } f = 1; solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...