Submission #1139404

#	Time	Username	Problem	Language	Result	Execution time	Memory
1139404		tempofun	Two Antennas (JOI19_antennas)	C++20	22 / 100	289 ms	44084 KiB

antennas

#include <bits/stdc++.h>
#define ar array
//#define ll long long

using namespace std;

using ll = long long;
using pii = pair<ll, ll>;
using pll = pair<ll, ll>;

const ll mod = 1e9 + 7;
const ll inf = 1e18;
const ll maxn = 1e5 + 5;

struct segment_tree {
    ll n;
    vector<ll> tree, mn, lazy;
    segment_tree(ll _n) : n(_n), tree(4*n, -inf), lazy(4*n, -inf), mn(4*n, inf) {}

    void pull(ll u, ll x) {
        tree[u] = max(tree[u], x - mn[u]);
        lazy[u] = max(lazy[u], x);
    }

    void push(ll u, ll tl, ll tr) {
        if(lazy[u] == -inf) return ;
        if(tl != tr) {
            pull(2*u, lazy[u]);
            pull(2*u+1, lazy[u]);
        }
        lazy[u] = -inf;
    }

    void set_mn(ll u, ll tl, ll tr, ll p, ll v) {
        if(tl == tr) {
            mn[u] = v;
        } else {
            push(u, tl, tr);
            ll tm = (tl + tr) / 2;
            if(p <= tm) set_mn(2*u, tl, tm, p, v);
            else set_mn(2*u+1, tm+1, tr, p, v);
            mn[u] = min(mn[2*u], mn[2*u+1]);
        }
    }

    void set_mx(ll u, ll tl, ll tr, ll l, ll r, ll v) {
        if(tl > r || l > tr) return ;

        if(l <= tl && tr <= r) {
            pull(u, v);
            push(u, tl, tr);
            return ;
        }

        ll tm = (tl + tr) / 2;
        set_mx(2*u, tl, tm, l, r, v);
        set_mx(2*u+1, tm+1, tr, l, r, v);
        tree[u] = max(tree[2*u], tree[2*u+1]);
    }

    ll query(ll u, ll tl, ll tr, ll l, ll r) {
        if(tl > r || l > tr) return -inf;
        if(l <= tl && tr <= r) return tree[u];
        push(u, tl, tr);
        ll tm = (tl + tr) / 2;
        return max(query(2*u, tl, tm, l, r), query(2*u+1, tm+1, tr, l, r));
    }

    void set_mn(ll p, ll v) { set_mn(1, 1, n, p, v); }
    void set_mx(ll l, ll r, ll v) { set_mx(1, 1, n, l, r, v); }
    ll query(ll l, ll r) { return query(1, 1, n, l, r); }
};

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    ll n; cin >> n;
    vector<ll> h(n+1), a(n+1), b(n+1);
    vector<vector<ll>> in(n+1), out(n+1);
    for(ll i=1; i<=n; i++) cin >> h[i] >> a[i] >> b[i];

    ll q; cin >> q;
    vector<ll> ans(q+1, -1);
    vector<pii> qus[n+1];

    for(ll i=1; i<=q; i++) {
        ll l, r; cin >> l >> r;
        qus[r].push_back({ l, i });
    }

    for(ll i=1; i<=n; i++) {
        ll l = min(n, i+a[i]);
        ll r = min(n, i+b[i]);
        in[l].push_back(i);
        out[r].push_back(i);
    }

    auto work = [&]() {
        segment_tree sgt(n);
        for(ll i=1; i<=n; i++) {
            for(ll id : in[i]) sgt.set_mn(id, h[id]);
            ll l = max(1ll, i-b[i]);
            ll r = max(1ll, i-a[i]);
            sgt.set_mx(l, r, h[i]);

            for(auto [j, id] : qus[i])
                ans[id] = max(ans[id], sgt.query(j, i));
            for(ll id : out[i]) sgt.set_mn(id, 1e18);
        }
    };

    work();
    for(ll i=1; i<=n; i++) h[i] *= -1;
    work();
    for(ll i=1; i<=q; i++) cout << ans[i] << '\n';
}

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