Submission #1170385

#TimeUsernameProblemLanguageResultExecution timeMemory
1170385patgraTwo Antennas (JOI19_antennas)C++20
0 / 100
230 ms40668 KiB
#include <bits/stdc++.h> #define rep(a,b,c) for(auto a = (b); a != (c); a++) #define repD(a,b,c) for(auto a = (b); a != (c); a--) #define repIn(a, b) for(auto& a : (b)) #define repIn2(a, b, c) for(auto& [a, b] : (c)) constexpr bool dbg = 0; #define DEBUG if constexpr(dbg) #define DC DEBUG std::cerr #define eol std::endl #define ll long long #define pb push_back using namespace std; constexpr int tb = (dbg ? 1 << 5 : 1 << 19), maxH = 1e9 + 7; constexpr ll inf = 2137e15; // [ on / off ] ; [ max (M - hi) ] ; [ min(turned on hi) to calc <- ] ; { M = max(M, x) => lazy propagation } ll tMinH[2 * tb], tMaxAns[2 * tb], lazy[2 * tb]; int n, q; void cerrTree(ll t[]) { if constexpr(!dbg) return; rep(i, 1, 2 * tb) { if(__builtin_popcount(i) == 1) DC << " "; DC << t[i] << ' '; if(__builtin_popcount(i + 1) == 1) DC << eol; } } void cerrAll() { DC << " TreeMinH: " << eol; cerrTree(tMinH); DC << " TreeMaxAns: " << eol; cerrTree(tMaxAns); DC << " Lazy propagation: " << eol; cerrTree(lazy); DC << eol; } void push(int v) { auto l = lazy[v]; lazy[v] = -2 * inf; tMaxAns[2 * v] = max(tMaxAns[2 * v], l - tMinH[2 * v]); tMaxAns[2 * v + 1] = max(tMaxAns[2 * v + 1], l - tMinH[2 * v + 1]); lazy[2 * v] = max(lazy[2 * v], l); lazy[2 * v + 1] = max(lazy[2 * v + 1], l); // assert(tMaxAns[v] == max(tMaxAns[2 * v], tMaxAns[2 * v + 1])); } void tTurn(int i) { DC << " " << (abs(tMinH[i + tb] - inf) <= maxH ? "on " : "off ") << i << eol; i += tb; int ii = i / 2; stack<int> st; while(ii) st.push(ii), ii /= 2; while(st.size()) push(st.top()), st.pop(); if(abs(tMinH[i] - inf) <= maxH) tMinH[i] -= inf; else tMinH[i] += inf; while(i / 2) i /= 2, tMinH[i] = min(tMinH[2 * i], tMinH[2 * i + 1]); cerrAll(); } void maxEq(int l, int r, ll x) { DC << " max= (" << l << ' ' << r << ' ' << x << ')' << eol; l += tb, r += tb; tMaxAns[l] = max(tMaxAns[l], x - tMinH[l]); tMaxAns[r] = max(tMaxAns[r], x - tMinH[r]); while(l / 2 != r / 2) { if(l % 2 == 0) tMaxAns[l + 1] = max(tMaxAns[l + 1], x - tMinH[l + 1]), lazy[l + 1] = max(lazy[l + 1], x); if(r % 2 == 1) tMaxAns[r - 1] = max(tMaxAns[r - 1], x - tMinH[r - 1]), lazy[r - 1] = max(lazy[r - 1], x); l /= 2; r /= 2; tMaxAns[l] = max(tMaxAns[l * 2], tMaxAns[l * 2 + 1]); tMaxAns[r] = max(tMaxAns[r * 2], tMaxAns[r * 2 + 1]); } l /= 2; while(l) tMaxAns[l] = max(tMaxAns[l * 2], tMaxAns[l * 2 + 1]), l /= 2; cerrAll(); } ll tq(int l, int r) { DC << " tq(" << l << ' ' << r << ") -> "; l += tb, r += tb; stack<int> toPush; int ogL = l, ogR = r; l /= 2, r /= 2; while(l / 2 != r / 2) { toPush.push(l); toPush.push(r); l /= 2, r /= 2; } while(l) toPush.push(l), l /= 2; while(toPush.size()) push(toPush.top()), toPush.pop(); l = ogL, r = ogR; ll ans = max(tMaxAns[l], tMaxAns[r]); while(l / 2 != r / 2) { if(l % 2 == 0) ans = max(ans, tMaxAns[l + 1]); if(r % 2 == 1) ans = max(ans, tMaxAns[r - 1]); l /= 2; r /= 2; } DC << ans << eol; cerrAll(); return ans; } void miotla(vector<pair<pair<int, int>, int>> queries, vector<pair<int, int>> updates, vector<ll>& answers, vector<ll> a, vector<ll> b, vector<ll> h) { rep(i, 0, n) tMinH[i + tb] = h[i] + inf; rep(i, n, tb) tMinH[i + tb] = inf; repD(i, tb - 1, 0) tMinH[i] = min(tMinH[i * 2], tMinH[i * 2 + 1]); repIn(i, tMaxAns) i = -inf; repIn(i, lazy) i = -2 * inf; auto itu = updates.begin(); auto itq = queries.begin(); DC << "Sweep" << eol; cerrAll(); rep(i, 0, n) { DC << ' ' << i << eol; while(itu != updates.end() && itu -> first <= i) tTurn(abs(itu++ -> second) - 1); if(i - a[i] >= 0) maxEq(max(0ll, i - b[i]), max(0ll, i - a[i]), h[i]); while(itq != queries.end() && itq -> first.first == i) answers[itq -> second] = max(answers[itq -> second], tq(itq -> first.second, i)), itq++; } } int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); cin >> n; vector<ll> h(n), a(n), b(n); rep(i, 0, n) cin >> h[i] >> a[i] >> b[i]; vector<pair<int, int>> updates; // PP - [second] activates; PN - [-second] deactivates; rep(i, 0, n) updates.pb({i + a[i], i + 1}), updates.pb({i + b[i] + 1, -i - 1}); ranges::sort(updates); cin >> q; vector<ll> answers(q, -1); vector<pair<pair<int, int>, int>> queries(q); // RL int l, r; rep(i, 0, q) cin >> l >> r, queries[i] = {{r - 1, l - 1}, i}; ranges::sort(queries); miotla(queries, updates, answers, a, b, h); ranges::reverse(a); ranges::reverse(b); ranges::reverse(h); updates.clear(); rep(i, 0, n) updates.pb({i + a[i], i + 1}), updates.pb({i + b[i] + 1, -i - 1}); ranges::sort(updates); repIn2(rl, ind, queries) rl = {n - rl.second - 1, n - rl.first - 1}; ranges::sort(queries); miotla(queries, updates, answers, a, b, h); repIn(i, answers) cout << 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...