Submission #1222898

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222898		minhpk	Two Antennas (JOI19_antennas)	C++20	0 / 100	182 ms	49016 KiB

antennas

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

#define ll long long

using namespace std;

vector <array<ll, 2>> V[200001], Q[200001];
ll n, q, a_idx, b_idx, H[200000], A[200000], B[200000], F[200000];

const ll INF_POS = 1e18;
const ll INF_NEG = -1e18;

struct SegTree {
    ll mx[800004], mn[800004];
    ll lazymx[800004], lazymn[800004];
    ll st[800004];

    void init() {
        for (int i = 0; i < 800004; ++i) {
            mx[i] = st[i] = lazymx[i] = INF_NEG;
            mn[i] = lazymn[i] = INF_POS;
        }
    }

    void update_st_from_lazy(ll id) {
        if (lazymx[id] != INF_NEG) {
            st[id] = max(st[id], lazymx[id] - mn[id]);
        }
        if (lazymn[id] != INF_POS) {
            st[id] = max(st[id], mx[id] - lazymn[id]);
        }
    }

    void push(ll id) {
        if (lazymx[id] == INF_NEG && lazymn[id] == INF_POS) return;

        lazymx[id*2] = max(lazymx[id*2], lazymx[id]);
        lazymx[id*2+1] = max(lazymx[id*2+1], lazymx[id]);
        lazymn[id*2] = min(lazymn[id*2], lazymn[id]);
        lazymn[id*2+1] = min(lazymn[id*2+1], lazymn[id]);
        
        update_st_from_lazy(id*2);
        update_st_from_lazy(id*2+1);

        lazymx[id] = INF_NEG;
        lazymn[id] = INF_POS;
    }

    void pt_update(ll id, ll l, ll r, ll q_idx, ll val) {
        if (l == r) {
            if (val == INF_POS) {
                mx[id] = INF_NEG;
                mn[id] = INF_POS;
            } else {
                mx[id] = mn[id] = val;
            }
            st[id] = INF_NEG;
            return;
        }
        
        push(id); 
        
        ll mid = (l + r) / 2;
        if (q_idx <= mid) {
            pt_update(id * 2, l, mid, q_idx, val);
        } else {
            pt_update(id * 2 + 1, mid + 1, r, q_idx, val);
        }
        
        mx[id] = max(mx[id*2], mx[id*2+1]);
        mn[id] = min(mn[id*2], mn[id*2+1]);
        st[id] = max(st[id*2], st[id*2+1]);
    }

    void range_update(ll id, ll l, ll r, ll ql, ll qr, ll w) {
        if (qr < l || r < ql) return;
        else if (ql <= l && r <= qr) {
            lazymx[id] = max(lazymx[id], w);
            lazymn[id] = min(lazymn[id], w);
            update_st_from_lazy(id);
            return;
        }

        push(id);
        
        ll mid = (l + r) / 2;
        range_update(id * 2, l, mid, ql, qr, w);
        range_update(id * 2 + 1, mid + 1, r, ql, qr, w);
        
        st[id] = max(st[id*2], st[id*2+1]);
    }

    ll query(ll id, ll l, ll r, ll ql, ll qr) {
        if (qr < l || r < ql) return INF_NEG;
        else if (ql <= l && r <= qr) return st[id];
        
        push(id);
        
        ll mid = (l + r) / 2;
        return max(query(id * 2, l, mid, ql, qr), query(id * 2 + 1, mid + 1, r, ql, qr));
    }
};

SegTree ST;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> H[i] >> A[i] >> B[i];
        if (i + A[i] < n) V[i + A[i]].push_back({1, i});
        if (i + B[i] + 1 < n) V[i + B[i] + 1].push_back({-1, i});
    }

    ST.init();

    cin >> q;
    for (int i = 0; i < q; ++i) {
        cin >> a_idx >> b_idx;
        --a_idx; --b_idx;
        Q[b_idx].push_back({i, a_idx});
    }

    for (int i = 0; i < n; ++i) {
        for (auto [type, element_idx] : V[i]) {
            if (type == 1) {
                ST.pt_update(1, 0, n - 1, element_idx, H[element_idx]);
            } else if (type == -1) {
                ST.pt_update(1, 0, n - 1, element_idx, INF_POS);
            }
        }
        
        ll lower_bound_j = max(0LL, i - B[i]);
        ll upper_bound_j = i - A[i];
        
        if (upper_bound_j >= 0) {
             ST.range_update(1, 0, n - 1, lower_bound_j, min(upper_bound_j, n-1LL), H[i]);
        }
        
        for (auto [query_id, query_l] : Q[i]) {
            F[query_id] = max(F[query_id], ST.query(1, 0, n - 1, query_l, i));
        }
    }

    for (int i = 0; i < q; ++i) cout << F[i] << '\n';
    return 0;
}

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