Submission #1185964

#	Time	Username	Problem	Language	Result	Execution time	Memory
1185964		Sharky	Two Antennas (JOI19_antennas)	C++20	100 / 100	550 ms	64716 KiB

antennas

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

#define int long long
const int N = 2e5 + 5;
const int inf = 1e18;

int n, q, h[N], a[N], b[N], L[N], R[N], ans[N];
vector<pair<int, int>> ev[2 * N], qry[N];

struct segtree {
    int size = 1;
    vector<pair<int, int>> seg; // max(-x), max(y-x)
    vector<int> lazy;
    void init(int sz) {
        while (size < sz) size *= 2;
        seg.assign(2 * size + 10, {-inf, -inf});
        lazy.assign(2 * size + 10, 0);
    }
    void push(int id) {
        // cout << "push: " << id << " " << lazy[id] << " " << seg[id].first << '\n';
        seg[id].second = max(seg[id].second, lazy[id] + seg[id].first); // seg[id].second is permanent!
        if (id < size) {
            for (int i = 0; i < 2; i++) lazy[id * 2 + i] = max(lazy[id * 2 + i], lazy[id]);
        }
        lazy[id] = 0;
    }
    void pull(int id) {
        seg[id].first = max(seg[id * 2].first, seg[id * 2 + 1].first);
        seg[id].second = max({seg[id * 2].second, seg[id * 2 + 1].second});
    }
    void update(int ql, int qr, int v, int l, int r, int id) {
        if (ql > qr) return;
        push(id);
        if (qr < l || r < ql) return;
        if (ql <= l && r <= qr) {
            lazy[id] = max(lazy[id], v);
            push(id);
            return;
        }
        int mid = (l + r) / 2;
        update(ql, qr, v, l, mid, id * 2);
        update(ql, qr, v, mid + 1, r, id * 2 + 1);
        pull(id);
    }
    void activate(int pos, int v, int l, int r, int id) {
        push(id);
        if (pos < l || r < pos) return;
        if (pos <= l && r <= pos) {
            seg[id].first = max(seg[id].first, v);
            seg[id].second = -inf;
            return;
        }
        int mid = (l + r) / 2;
        activate(pos, v, l, mid, id * 2);
        activate(pos, v, mid + 1, r, id * 2 + 1);
        pull(id);
    }
    void deactivate(int pos, int l, int r, int id) {
        push(id);
        if (pos < l || r < pos) return;
        if (pos <= l && r <= pos) {
            seg[id].first = -inf;
            return;
        }
        int mid = (l + r) / 2;
        deactivate(pos, l, mid, id * 2);
        deactivate(pos, mid + 1, r, id * 2 + 1);
        pull(id);
    }
    int query(int ql, int qr, int l, int r, int id) {
        if (ql > qr) return -1;
        push(id);
        if (qr < l || r < ql) return -1;
        if (ql <= l && r <= qr) {
            // cout << l << " " << r << " return " << seg[id].second << '\n';
            return seg[id].second;
        }
        int mid = (l + r) / 2;
        return max(query(ql, qr, l, mid, id * 2), query(ql, qr, mid + 1, r, id * 2 + 1));
    }
    void activate(int i) {
        // cout << "activate " << i << '\n';
        activate(i, -h[i], 1, n, 1);
    }
    void deactivate(int i) {
        // cout << "deactivate " << i << '\n';
        deactivate(i, 1, n, 1);
    }
    void print_tree(int l, int r, int id) {
        int mid = (l + r) / 2;
        // cout << l << " " << r << " " << seg[id].second << '\n';
        if (l == r) return;
        print_tree(l, mid, id * 2);
        print_tree(mid + 1, r, id * 2 + 1);
    }
};

void solve() {
    for (int i = 1; i <= n; i++) {
        ev[i + a[i]].push_back({i, 1});
        ev[i + b[i] + 1].push_back({i, -1});
    }
    segtree ST;
    ST.init(n + 1);
    for (int i = 1; i <= q; i++) qry[R[i]].push_back({L[i], i});
    for (int i = 1; i <= n; i++) {
        for (auto& [x, y] : ev[i]) {
            if (y == 1) ST.activate(x);
            else ST.deactivate(x);
            // cout << "printtree\n";
            // ST.print_tree(1, n, 1);
        }
        // cout << "update: " << max(1LL, i - b[i]) << " " << i - a[i] << ' ' << h[i] << '\n';
        ST.update(max(1LL, i - b[i]), i - a[i], h[i], 1, n, 1);
        for (auto& [l, id] : qry[i]) {
            // cout << ST.query(1, 1, 1, n, 1) << '\n';
            // cout << ST.query(2, 2, 1, n, 1) << '\n';
            // cout << ST.query(1, 2, 1, n, 1) << '\n';
            // cout << ST.query(3, 3, 1, n, 1) << '\n';
            // cout << ST.query(4, 4, 1, n, 1) << '\n';
            // cout << ST.query(3, 4, 1, n, 1) << '\n';
            // cout << l << " " << i << " " << ST.query(l, i, 1, n, 1) << '\n';
            ans[id] = max(ans[id], ST.query(l, i, 1, n, 1));
        }
        // cout << "printtree\n";
        // ST.print_tree(1, n, 1);
    }
    for (int i = 1; i <= n; i++) {
        ev[i].clear();
        qry[i].clear();
    }
}

int32_t main() {
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> h[i] >> a[i] >> b[i];
    cin >> q;
    for (int i = 1; i <= q; i++) {
        cin >> L[i] >> R[i];
        ans[i] = -1;
    }
    solve();
    reverse(h + 1, h + n + 1);
    reverse(a + 1, a + n + 1);
    reverse(b + 1, b + n + 1);
    for (int i = 1; i <= q; i++) {
        L[i] = n - L[i] + 1, R[i] = n - R[i] + 1;
        swap(L[i], R[i]);
    }
    // for (int i = 1; i <= n; i++) cout << h[i] << " " << a[i] << " " << b[i] << '\n';
    // for (int i = 1; i <= q; i++) cout << L[i] << " " << R[i] << '\n';
    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