Submission #1170396

#	Time	Username	Problem	Language	Result	Execution time	Memory
1170396		patgra	Two Antennas (JOI19_antennas)	C++20	100 / 100	590 ms	46988 KiB

antennas

#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 << 3 : 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 << "    ";
        if(t[i] == inf) { DC << "oo "; }
        else if(t[i] == -inf) { DC << "-oo "; }
        else if(t[i] == -2 * inf) { DC << "-2oo "; }
        else if(abs(t[i] - inf) <= maxH) { DC << "x" << t[i] - inf << ' '; }
        else 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;
    stack<int> toPush;
    int ogL = l, ogR = r;
    while(l / 2 != r / 2) {
        l /= 2, r /= 2;
        toPush.push(l);
        toPush.push(r);
    }
    l /= 2;
    while(l) toPush.push(l), l /= 2;
    while(toPush.size()) {
        DC << "   pushkin " << toPush.top() << eol;
        push(toPush.top()), toPush.pop();
    }
    DC << "--------------------After pushing all relevant" << eol;
    cerrAll();

    l = ogL, r = ogR;
    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] = (l >= tb ? 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] = (r >= tb ? 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 = -1;
    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';

}

• Subtask 1: 2 / 2
• Subtask 2: 11 / 11
• Subtask 3: 22 / 22
• Subtask 4: 65 / 65