Submission #1149447

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149447		ShadowShark	Two Antennas (JOI19_antennas)	C++20	100 / 100	657 ms	38104 KiB

antennas

#include <bits/stdc++.h>
using namespace std;

const int maxN = 2e5 + 5, inf = 1e9 + 7;
int h[maxN], a[maxN], b[maxN], L[maxN], R[maxN], ans[maxN];

struct node {
    int val, mn, lazy;
} st[4 * maxN];

void down(int id) {
    int t = st[id].lazy;

    st[2 * id].val = max(st[2 * id].val, t - st[2 * id].mn);
    st[2 * id].lazy = max(st[2 * id].lazy, t);

    st[2 * id + 1].val = max(st[2 * id + 1].val, t - st[2 * id + 1].mn);
    st[2 * id + 1].lazy = max(st[2 * id + 1].lazy, t);

    st[id].lazy = 0;
}

void build(int id, int l, int r) {
    if (l == r) {
        st[id].val = -inf;
        st[id].mn = inf;
        st[id].lazy = 0;
        return ;
    }

    int mid = (l + r) >> 1;
    build(2 * id, l, mid);
    build(2 * id + 1, mid + 1, r);

    st[id].lazy = 0;
    st[id].mn = min(st[2 * id].mn, st[2 * id + 1].mn);
    st[id].val = max(st[2 * id].val, st[2 * id + 1].val);
}

void updatePoint(int id, int l, int r, int pos, int val) {
    if (l == r) {
        st[id].mn = val;
        return ;
    }

    int mid = (l + r) >> 1;
    down(id);
    if (pos <= mid) updatePoint(2 * id, l, mid, pos, val);
        else updatePoint(2 * id + 1, mid + 1, r, pos, val);

    st[id].val = max(st[2 * id].val, st[2 * id + 1].val);
    st[id].mn = min(st[2 * id].mn, st[2 * id + 1].mn);
}

void updateRange(int id, int l, int r, int u, int v, int val) {
    if (v < l || r < u) return ;

    if (u <= l && r <= v) {
        st[id].val = max(st[id].val, val - st[id].mn);
        st[id].lazy = max(st[id].lazy, val);
        return ;
    }

    int mid = (l + r) >> 1;
    down(id);
    updateRange(2 * id, l, mid, u, v, val);
    updateRange(2 * id + 1, mid + 1, r, u, v, val);

    st[id].val = max(st[2 * id].val, st[2 * id + 1].val);
}

int get(int id, int l, int r, int u, int v) {
    if (v < l || r < u) return -inf;
    if (u <= l && r <= v) return st[id].val;

    int mid = (l + r) >> 1;
    down(id);

    int A = get(2 * id, l, mid, u, v);
    int B = get(2 * id + 1, mid + 1, r, u, v);

    return max(A, B);
}

vector<int> Begin[maxN], End[maxN], query[maxN];

void solve(int n, int q) {
    build(1, 1, n);

    for (int i = 1; i <= n; i++) {
        if (i + a[i] <= n) Begin[i + a[i]].push_back(i);
        if (i + b[i] <= n) End[i + b[i]].push_back(i);
    }

    for (int i = 1; i <= q; i++)
        query[R[i]].push_back(i);

    for (int i = 1; i <= n; i++) {
        for (auto id: Begin[i])
            updatePoint(1, 1, n, id, h[id]);

        if (i - a[i] > 0) updateRange(1, 1, n, max(i - b[i], 1), i - a[i], h[i]);

        for (auto id: query[i])
            ans[id] = max(ans[id], get(1, 1, n, L[id], R[id]));

        for (auto id: End[i])
            updatePoint(1, 1, n, id, inf);
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++)
        cin >> h[i] >> a[i] >> b[i];

    int q;
    cin >> q;

    for (int i = 1; i <= q; i++) {
        cin >> L[i] >> R[i];
        ans[i] = -1;
    }

    solve(n, q);

    for (int i = 1; i <= n; i++) {
        Begin[i].clear();
        End[i].clear();
        query[i].clear();
    }

    for (int i = 1; i <= n / 2; i++) {
        swap(h[i], h[n + 1 - i]);
        swap(a[i], a[n + 1 - i]);
        swap(b[i], b[n + 1 - i]);
    }

    for (int i = 1; i <= q; i++) {
        L[i] = n + 1 - L[i];
        R[i] = n + 1 - R[i];
        swap(L[i], R[i]);
    }

    solve(n, q);

    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