Submission #613695

#	Time	Username	Problem	Language	Result	Execution time	Memory
613695		tengiz05	Two Antennas (JOI19_antennas)	C++17	13 / 100	3091 ms	14104 KiB

antennas

#include <bits/stdc++.h>

using i64 = long long;
using namespace std;

constexpr int N = 2E5;
constexpr i64 inf = 1E18;

i64 A[N], historyMax[N];
void update(int p, i64 x) {
    A[p] = x;
}
void add(int l, int r, i64 x) {
    for (int i = l; i < r; i++) {
        A[i] += x;
        historyMax[i] = max(historyMax[i], A[i]);
    }
}
int query(int l, int r) {
    i64 res = -1;
    for (int i = l; i < r; i++) {
        res = max(res, historyMax[i]);
    }
    return res;
    //~ return s.rangeQuery(l, r).allmax;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    for (int i = 0; i < N; i++) {
        A[i] = -2 * inf;
        historyMax[i] = -1;
    }
    
    int n;
    cin >> n;
    
    vector<int> h(n), a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> h[i] >> a[i] >> b[i];
    }
    
    vector<array<int, 3>> g;
    for (int i = 0; i < n; i++) {
        g.push_back({i + a[i], 1, i});
        g.push_back({i + b[i] + 1, -1, i});
    }
    
    sort(g.begin(), g.end());
    
    int q;
    cin >> q;
    
    vector<vector<array<int, 2>>> Q(n);
    vector<int> ans(q);
    for (int i = 0; i < q; i++) {
        int l, r;
        cin >> l >> r;
        l--;
        r--;
        Q[r].push_back({l, i});
    }
    
    int k = 0;
    
    for (int i = 0; i < n; i++) {
        while (k < int(g.size()) && g[k][0] == i) {
            int p = g[k][2];
            if (g[k][1] == 1) {
                update(p, -inf + h[p]);
            } else {
                update(p, -2 * inf);
            }
            k++;
        }
        int L = max(0, i - b[i]);
        int R = max(0, i - a[i] + 1);
        add(L, R, -h[i]);
        add(L, R, inf);
        for (auto [l, id] : Q[i]) {
            ans[id] = query(l, i + 1);
        }
        add(L, R, -inf);
        add(L, R, h[i]);
    }
    
    for (int i = 0; i < N; i++) {
        A[i] = -2 * inf;
        historyMax[i] = -1;
    }
    
    k = 0;
    
    for (int i = 0; i < n; i++) {
        while (k < int(g.size()) && g[k][0] == i) {
            int p = g[k][2];
            if (g[k][1] == 1) {
                update(p, -inf + -h[p]);
            } else {
                update(p, -2 * inf);
            }
            k++;
        }
        int L = max(0, i - b[i]);
        int R = max(0, i - a[i] + 1);
        add(L, R, h[i]);
        add(L, R, inf);
        for (auto [l, id] : Q[i]) {
            ans[id] = max(ans[id], query(l, i + 1));
        }
        add(L, R, -inf);
        add(L, R, -h[i]);
    }
    
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
    
    return 0;
}

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