Submission #1242874

#	Time	Username	Problem	Language	Result	Execution time	Memory
1242874		quannnguyen2009	Two Antennas (JOI19_antennas)	C++20	100 / 100	349 ms	62692 KiB

antennas

#include<bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define ii pair<int, int>
#define sz(v) (int)v.size()
#define all(v) v.begin(), v.end()
using namespace std;

const int N = 2e5+5, mod = 1e9+7, inf = 1e18;

int n, q, f;
int h[N], a[N], b[N], ans[N];
vector<int> on[N], off[N];
vector<ii> que[N];

int seg_mx[4*N], seg_mn[4*N], l_mx[4*N], l_mn[4*N], seg[4*N];

void push(int node) {
    l_mx[node<<1] = max(l_mx[node<<1], l_mx[node]);
    l_mx[node<<1|1] = max(l_mx[node<<1|1], l_mx[node]);
    l_mn[node<<1] = min(l_mn[node<<1], l_mn[node]);
    l_mn[node<<1|1] = min(l_mn[node<<1|1], l_mn[node]);
    seg[node<<1] = max(seg[node<<1], max(seg_mx[node<<1]-l_mn[node], l_mx[node]-seg_mn[node<<1]));
    seg[node<<1|1] = max(seg[node<<1|1], max(seg_mx[node<<1|1]-l_mn[node], l_mx[node]-seg_mn[node<<1|1]));
    l_mx[node] = -inf, l_mn[node] = inf;
}

void upd1(int node, int l, int r, int idx, int v) {
    if (idx<l || idx>r) return;
    if (l==r) {
        if (v==inf) {
            seg_mx[node] = -inf;
            seg_mn[node] = inf;
        } else {
            seg_mx[node] = seg_mn[node] = v;
        }
        return;
    }
    push(node);
    int mid = (l+r)>>1;
    upd1(node<<1, l, mid, idx, v);
    upd1(node<<1|1, mid+1, r, idx, v);
    seg_mx[node] = max(seg_mx[node<<1], seg_mx[node<<1|1]);
    seg_mn[node] = min(seg_mn[node<<1], seg_mn[node<<1|1]);
    seg[node] = max(seg[node<<1], seg[node<<1|1]);
}

void upd2(int node, int l, int r, int ql, int qr, int v) {
    if (l>qr || r<ql) return;
    else if (ql<=l && r<=qr) {
        l_mx[node] = max(l_mx[node], v);
        l_mn[node] = min(l_mn[node], v);
        seg[node] = max(seg[node], max(seg_mx[node]-v, v-seg_mn[node]));
        return;
    }
    push(node);
    int mid = (l+r)>>1;
    upd2(node<<1, l, mid, ql, qr, v);
    upd2(node<<1|1, mid+1, r, ql, qr, v);
    seg[node] = max(seg[node<<1], seg[node<<1|1]);
}

int get(int node, int l, int r, int ql, int qr) {
    if (l>qr || r<ql) return -inf;
    else if (ql<=l && r<=qr) return seg[node];
    push(node);
    int mid = (l+r)>>1;
    return max(get(node<<1, l, mid, ql, qr), get(node<<1|1, mid+1, r, ql, qr));
}

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];
        if (i+a[i]<=n) on[i+a[i]].pb(i);
        if (i+b[i]+1<=n) off[i+b[i]+1].pb(i);
    }
    for (int i=0; i<4*N; i++) {
        seg_mx[i] = seg[i] = l_mx[i] = -inf;
        seg_mn[i] = l_mn[i] = inf;
    }
    cin >> q;
    for (int i=1; i<=q; i++) {
        int l, r; cin >> l >> r;
        que[r].pb({i, l});
        ans[i] = -1;
    }
    for (int i=1; i<=n; i++) {
        for (int it: on[i]) upd1(1, 1, n, it, h[it]);
        for (int it: off[i]) upd1(1, 1, n, it, inf);
        if (i-a[i]>=1) upd2(1, 1, n, max(i-b[i], 1ll), i-a[i], h[i]);
        for (auto [id, l] : que[i]) ans[id] = max(ans[id], get(1, 1, n, l, i));
    }
    for (int i=1; i<=q; i++) cout << ans[i] << '\n';
}

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