Submission #570139

#TimeUsernameProblemLanguageResultExecution timeMemory
570139timreizinTwo Antennas (JOI19_antennas)C++17
0 / 100
3041 ms7240 KiB
#include <iostream> #include <vector> #include <numeric> #include <cmath> #include <set> #include <array> #include <algorithm> using namespace std; using ll = long long; const ll INF = 1e15; struct segtree { int n; vector<ll> mx, mod, tree; void push(int v) { mod[v << 1] = max(mod[v << 1], mod[v]); mod[v << 1 | 1] = max(mod[v << 1 | 1], mod[v]); tree[v << 1] = max(tree[v << 1], mx[v << 1] + mod[v]); tree[v << 1 | 1] = max(tree[v << 1 | 1], mx[v << 1 | 1] + mod[v]); } segtree(int n) : n(n) { mx.resize(4 * n, -INF); mod.resize(4 * n, 0); tree.resize(4 * n, -INF); } ll get(int a, int b, int l, int r, int v) { if (a > r || b < l) return -INF; if (a == l && b == r) return tree[v]; int m = (l + r) >> 1; push(v); return max(get(a, min(b, m), l, m, v << 1), get(max(a, m + 1), b, m + 1, r, v << 1 | 1)); } ll get(int a, int b) { return get(a, b, 0, n - 1, 1); } void updateH(int p, ll val, int l, int r, int v) { if (l > r) return; if (l == r) { mx[v] = val; tree[v] = val + mod[v]; return; } int m = (l + r) >> 1; push(v); if (p <= m) updateH(p, val, l, m, v << 1); else updateH(p, val, m + 1, r, v << 1 | 1); tree[v] = max(tree[v << 1], tree[v << 1 | 1]); mx[v] = max(mx[v << 1], mx[v << 1 | 1]); } void updateH(int p, ll val) { updateH(p, val, 0, n - 1, 1); } void updateM(int a, int b, ll val, int l, int r, int v) { if (a > r || b < l) return; if (a == l && b == r) { mod[v] = max(mod[v], val); tree[v] = max(tree[v], mx[v] + mod[v]); return; } int m = (l + r) >> 1; push(v); updateM(a, min(b, m), val, l, m, v << 1); updateM(max(a, m + 1), b, val, m + 1, r, v << 1 | 1); tree[v] = max(tree[v << 1], tree[v << 1 | 1]); mx[v] = max(mx[v << 1], mx[v << 1 | 1]); } void updateM(int a, int b, ll val) { updateM(a, b, val, 0, n - 1, 1); } }; vector<ll> solve(vector<ll> h, vector<pair<int, int>> ab, vector<pair<int, int>> queries) { int n = (int)h.size(); int q = (int)queries.size(); vector<int> inds(q); vector<pair<pair<int, int>, int>> events; segtree st(n); events.reserve(2 * n); iota(inds.begin(), inds.end(), 0); sort(inds.begin(), inds.end(), [&queries](int a, int b){ return queries[a].second < queries[b].second; }); for (int i = 0; i < n; ++i) { events.emplace_back(pair(i + ab[i].first, 0), i); events.emplace_back(pair(i + ab[i].second, 1), i); } sort(events.begin(), events.end()); vector<ll> result(q, -1); for (int i = 0, indE = 0, indQ = 0; i < n; ++i) { while (indE < 2 * n && events[indE].first <= pair(i, 0)) { st.updateH(events[indE].second, -h[events[indE].second]); ++indE; } if (i - ab[i].first >= 0) st.updateM(max(0, i - ab[i].second), i - ab[i].first, h[i]); while (indQ < q && queries[inds[indQ]].second == i) { result[inds[indQ]] = max(result[inds[indQ]], st.get(queries[inds[indQ]].first, queries[inds[indQ]].second)); ++indQ; } while (indE < 2 * n && events[indE].first <= pair(i, 1)) { st.updateH(events[indE].second, -INF); ++indE; } } reverse(h.begin(), h.end()); reverse(ab.begin(), ab.end()); for (auto &i : queries) i = {n - i.second - 1, n - i.first - 1}; events.clear(); sort(inds.begin(), inds.end(), [&queries](int a, int b){ return queries[a].second < queries[b].second; }); for (int i = 0; i < n; ++i) { events.emplace_back(pair(i + ab[i].first, 0), i); events.emplace_back(pair(i + ab[i].second, 1), i); } sort(events.begin(), events.end()); st = segtree(n); for (int i = 0, indE = 0, indQ = 0; i < n; ++i) { while (indE < 2 * n && events[indE].first <= pair(i, 0)) { st.updateH(events[indE].second, -h[events[indE].second]); ++indE; } if (i - ab[i].first >= 0) st.updateM(max(0, i - ab[i].second), i - ab[i].first, h[i]); while (indQ < q && queries[inds[indQ]].second == i) { result[inds[indQ]] = max(result[inds[indQ]], st.get(queries[inds[indQ]].first, queries[inds[indQ]].second)); ++indQ; } while (indE < 2 * n && events[indE].first <= pair(i, 1)) { st.updateH(events[indE].second, -INF); ++indE; } } return result; } vector<ll> brute(vector<ll> h, vector<pair<int, int>> ab, vector<pair<int, int>> queries) { int n = (int)h.size(); int q = (int)queries.size(); vector<ll> res(n, -1); for (int i = 0; i < q; ++i) { for (int j = queries[i].first; j <= queries[i].second; ++j) { for (int k = j + ab[j].first; k <= min(queries[i].second, j + ab[j].second); ++k) { if (k - j >= ab[k].first && k - j <= ab[k].second) res[i] = max(res[i], abs(h[j] - h[k])); } } cout << res[i] << '\n'; } return res; } int main() { cin.tie(0)->sync_with_stdio(0); int n; cin >> n; vector<ll> h(n); vector<pair<int, int>> ab(n); for (int i = 0; i < n; ++i) { cin >> h[i] >> ab[i].first >> ab[i].second; } int q; cin >> q; vector<pair<int, int>> queries(q); for (auto &[l, r] : queries) { cin >> l >> r; --l; --r; } brute(h, ab, queries); 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 */ /* 2 10 2 4 1 1 1 1 1 2 */ //10 1 2 1 100
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...