Submission #1274920

#TimeUsernameProblemLanguageResultExecution timeMemory
1274920hoangtien69Two Antennas (JOI19_antennas)C++20
0 / 100
179 ms42576 KiB
#include<bits/stdc++.h> using namespace std; const int MAXN = 2e5 + 5; #define int long long #define pii pair<int,int> const int INF = 1e18; int n; int a[MAXN], b[MAXN], h[MAXN]; int q; vector<pii> peal[MAXN]; vector<pii> query[MAXN]; int ans[MAXN]; struct Node { int maxx, minn, res; Node() : maxx(-INF), minn(INF), res(-INF) {} }; Node st[4 * MAXN]; pii lazy[4 * MAXN]; Node Merge(Node A, Node B) { Node result; result.maxx = max(A.maxx, B.maxx); result.minn = min(A.minn, B.minn); result.res = max(A.res, B.res); return result; } void build(int id, int l, int r) { if (l == r) { st[id] = Node(); return; } int m = (l + r) / 2; build(id * 2, l, m); build(id * 2 + 1, m + 1, r); st[id] = Merge(st[id * 2], st[id * 2 + 1]); } void push(int id, int l, int r) { lazy[id * 2].first = max(lazy[id * 2].first, lazy[id].first); lazy[id * 2].second = min(lazy[id * 2].second, lazy[id].second); lazy[id * 2 + 1].first = max(lazy[id * 2 + 1].first, lazy[id].first); lazy[id * 2 + 1].second = min(lazy[id * 2 + 1].second, lazy[id].second); st[id * 2].res = max({st[id * 2].res, st[id * 2].maxx - lazy[id].second, lazy[id].first - st[id * 2].minn}); st[id * 2 + 1].res = max({st[id * 2 + 1].res, st[id * 2 + 1].maxx - lazy[id].second, lazy[id].first - st[id * 2 + 1].minn}); lazy[id] = {-INF, INF}; } void update(int id, int l, int r, int pos, int val1, int val2) { if (l == r) { st[id].maxx = val1; st[id].minn = val2; st[id].res = -INF; return; } int m = (l + r) / 2; push(id, l, r); if (pos <= m) { update(id * 2, l, m, pos, val1, val2); } else { update(id * 2 + 1, m + 1, r, pos, val1, val2); } st[id] = Merge(st[id * 2], st[id * 2 + 1]); } void update_range(int id, int l, int r, int u, int v, int val) { if (r < u || v < l) return; if (u <= l && r <= v) { lazy[id].first = max(lazy[id].first, val); lazy[id].second = min(lazy[id].second, val); st[id].res = max({st[id].res, lazy[id].first - st[id].minn, st[id].maxx - lazy[id].second}); return; } push(id, l, r); int m = (l + r) / 2; update_range(id * 2, l, m, u, v, val); update_range(id * 2 + 1, m + 1, r, u, v, val); st[id] = Merge(st[id * 2], st[id * 2 + 1]); } Node get(int id, int l, int r, int u, int v) { if (v < l || r < u) return Node(); push(id, l, r); if (u <= l && r <= v) return st[id]; int m = (l + r) / 2; return Merge(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v)); } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n; for (int i = 1; i <= n; i++) { cin >> h[i] >> a[i] >> b[i]; } cin >> q; for (int i = 1; i <= q; i++) { int l, r; cin >> l >> r; query[r].push_back({l, i}); } for (int i = 1; i <= n; i++) { if (i + a[i] <= n) peal[i + a[i]].push_back({i, 1}); if (i + b[i] + 1 <= n) peal[i + b[i] + 1].push_back({i, -1}); } build(1, 1, n); for (int i = 1; i <= 4 * n; i++) { lazy[i] = {-INF, INF}; } for (int i = 1; i <= n; i++) { for (auto [pos, type] : peal[i]) { if (type == 1) { update(1, 1, n, pos, h[pos], h[pos]); } else { update(1, 1, n, pos, -INF, INF); } } int left = max(1LL, i - b[i]); int right = i - a[i]; if (left <= right) { update_range(1, 1, n, left, right, h[i]); } for (auto [left_query, id] : query[i]) { Node result = get(1, 1, n, left_query, i); ans[id] = result.res; ans[id] = max(-1LL, ans[id]); } } 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...