Submission #613664

#TimeUsernameProblemLanguageResultExecution timeMemory
613664tengiz05Two Antennas (JOI19_antennas)C++17
13 / 100
3035 ms14784 KiB
#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 decrease(int l, int r, int x) {
    for (int i = l; i < r; i++) {
        A[i] -= x;
        historyMax[i] = max(historyMax[i], A[i]);
    }
}
void increase(int l, int r, int x) {
    for (int i = l; i < r; i++) {
        A[i] += x;
    }
}
int query(int l, int r) {
    i64 res = -1;
    for (int i = l; i < r; i++) {
        res = max(res, historyMax[i]);
    }
    return res;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    for (int i = 0; i < N; i++) {
        A[i] = -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, h[p]);
            } else {
                update(p, -inf);
            }
            k++;
        }
        int L = max(0, i - b[i]);
        int R = max(0, i - a[i] + 1);
        decrease(L, R, h[i]);
        for (auto [l, id] : Q[i]) {
            ans[id] = query(l, i + 1);
        }
        increase(L, R, h[i]);
    }
    
    for (int i = 0; i < N; i++) {
        A[i] = -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, -h[p]);
            } else {
                update(p, -inf);
            }
            k++;
        }
        int L = max(0, i - b[i]);
        int R = max(0, i - a[i] + 1);
        decrease(L, R, -h[i]);
        for (auto [l, id] : Q[i]) {
            ans[id] = max(ans[id], query(l, i + 1));
        }
        increase(L, R, -h[i]);
    }
    
    for (int i = 0; i < q; i++) {
        cout << ans[i] << "\n";
    }
    
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...