Submission #1177331

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177331		JohnTitor	Two Antennas (JOI19_antennas)	C++20	100 / 100	392 ms	27728 KiB

antennas

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

// offline processing
// - process query by increasing r
// - when we add a new element r, we update ans[l], which is the best result starting from l for each l
// -
// - consider the elements r can look at
//
// we want a segment tree that will handle the following:
// - hold 2 arrays a[i] and c[i]
// - query the max of a[i] - c[i]
// - update a range a[i] = max(a[i], x)
// - if we start with a = 0 normally then we can get the answer from max - min everytime we update x

constexpr int INF = 1e9 + 1;
int n;
constexpr int MAX_N = 2e5;

// answer for the positions that's already done
int ft[MAX_N + 1];
void update_done(int u, int result) {
    for (; u > 0; u -= u & -u) ft[u] = max(ft[u], result);
}

int get_done(int u) {
    int res = -INF;
    for (; u <= n; u += u & -u) res = max(res, ft[u]);
    return res;
}

class segment_tree_t {
public:
    class node_t {
    public:
        int max_a;
        int max_minus;
        int min_c;
    } st[MAX_N * 4];

    void build(int i = 1, int l = 1, int r = n) {
        auto &&[max_a, max_minus, min_c] = st[i];

        max_a = -INF;
        max_minus = -INF;
        min_c = INF;
        if (l != r) {
            int m = (l + r) / 2;
            build(i * 2, l, m);
            build(i * 2 + 1, m + 1, r);
        }
    }

    void recalculate(int i, int l, int r) {
        auto &&[max_a, max_minus, min_c] = st[i];
        if (l != r) {
            auto &&left = st[i * 2];
            auto &&right = st[i * 2 + 1];
            min_c = min(left.min_c, right.min_c);
            max_minus = max(left.max_minus, right.max_minus);
        } else {
            max_minus = -INF;
        }
        max_minus = max(max_minus, max_a - min_c);
    }

    void down(int i) {
        auto &&[max_a, max_minus, min_c] = st[i];
        auto &&left = st[i * 2];
        auto &&right = st[i * 2 + 1];
        left.max_a = max(left.max_a, max_a);
        left.max_minus = max(left.max_minus, max_a - left.min_c);
        right.max_a = max(right.max_a, max_a);
        right.max_minus = max(right.max_minus, max_a - right.min_c);
        max_a = -INF;
    }

    void update_c(int i, int l, int r, int u, int c) {
        if (l == r) {
            auto &&[max_a, max_minus, min_c] = st[i];
            assert(l == u);
            min_c = c;
            max_a = -INF;
        } else {
            down(i);
            int m = (l + r) / 2;
            if (m >= u) update_c(i * 2, l, m, u, c);
            else update_c(i * 2 + 1, m + 1, r, u, c);
        }
        recalculate(i, l, r);
    }

    void update_a(int i, int l, int r, int u, int v, int a) {
        if (l > v || r < u) return;
        if (u <= l && v >= r) {
            auto &&[max_a, max_minus, min_c] = st[i];
            max_a = max(max_a, a);
            recalculate(i, l, r);
        } else {
            down(i);
            int m = (l + r) / 2;
            update_a(i * 2, l, m, u, v, a);
            update_a(i * 2 + 1, m + 1, r, u, v, a);
            recalculate(i, l, r);
        }
    }

    int get_max_minus(int i, int l, int r, int u, int v) {
        if (l > v || r < u) return -INF;
        auto &&[max_a, max_minus, min_c] = st[i];
        if (u <= l && v >= r) return max_minus;
        down(i);
        int m = (l + r) / 2;
        return max(get_max_minus(i * 2, l, m, u, v), get_max_minus(i * 2 + 1, m + 1, r, u, v));
    }
} tree;

int q;
int h[MAX_N + 1];
int a[MAX_N + 1];
int b[MAX_N + 1];
int ans[MAX_N + 1];

vector<int> turn_on[MAX_N + 1];
vector<int> turn_off[MAX_N + 1];

vector<tuple<int, int, int>> queries;
void solve() {
    tree.build();
    int i = 1;
    fill(ft + 1, ft + n + 1, -INF);
    for (auto &&[r, l, id] : queries) {
        while (i <= r) {
            for (auto &&j : turn_on[i]) tree.update_c(1, 1, n, j, h[j]);
            for (auto &&j : turn_off[i]) {
                // this element is done, it can't be used to update the answer anymore, but the existing answer can still be
                // used
                update_done(j, tree.get_max_minus(1, 1, n, j, j));
                tree.update_c(1, 1, n, j, INF);
            }
            int l_i = i - b[i];
            int r_i = i - a[i];
            l_i = max(l_i, 1);
            if (l_i <= r_i) tree.update_a(1, 1, n, l_i, r_i, h[i]);
            i++;
        }
        // to answer a query, we use the existing answer and the done answer
        ans[id] = max(ans[id], get_done(l));
        ans[id] = max(ans[id], tree.get_max_minus(1, 1, n, l, r));
    }
}

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

    cin >> n;
    assert(n <= 2e5);
    for (int i = 1; i <= n; i++) cin >> h[i] >> a[i] >> b[i];
    for (int i = 1; i <= n; i++) {
        int l = i + a[i];
        int r = i + b[i];
        if (l <= n) turn_on[l].push_back(i);
        if (r + 1 <= n) turn_off[r + 1].push_back(i);
    }
    cin >> q;
    assert(q <= 2e5);
    for (int i = 1; i <= q; i++) {
        static int l, r;
        cin >> l >> r;
        queries.emplace_back(r, l, i);
        assert(l <= r);
    }
    sort(queries.begin(), queries.end());
    fill(ans + 1, ans + q + 1, -1);
    solve();
    for (int i = 1; i <= n; i++) h[i] = -h[i];
    solve();
    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