Submission #1184106

#	Time	Username	Problem	Language	Result	Execution time	Memory
1184106		OI_Account	Two Antennas (JOI19_antennas)	C++20	0 / 100	259 ms	33000 KiB

antennas

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

typedef long long ll;

const int N = 200'000;
const ll INF = 1'000'000'000'000'000'000;

int n, q;
int a[N + 10], b[N + 10];
ll h[N + 10], res[N + 10];
ll maxH[4 * N + 10], ans[4 * N + 10], lazy[4 * N + 10];
vector<int> st[N + 10], en[N + 10];
vector<pair<int, int>> query[N + 10];

void readInput() {
    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++) {
        int l, r;
        cin >> l >> r;
        query[r].push_back({l, i});
    }
}

void shift(int, int, int);

ll get(int st, int en, int id = 1, int l = 1, int r = n + 1) {
    if (en <= l || r <= st)
        return -INF;
    if (st <= l && r <= en)
        return ans[id];
    shift(id, l, r);
    int mid = (l + r) >> 1;
    return max(get(st, en, id << 1, l, mid), get(st, en, id << 1 | 1, mid, r));
}

void updateAns(int st, int en, ll val, int id = 1, int l = 1, int r = n + 1) {
    if (en <= l || r <= st)
        return;
    if (st <= l && r <= en) {
        ans[id] = max(ans[id], maxH[id] + val);
        lazy[id] = max(lazy[id], val);
        return;
    }
    shift(id, l, r);
    int mid = (l + r) >> 1;
    updateAns(st, en, val, id << 1, l, mid);
    updateAns(st, en, val, id << 1 | 1, mid, r);
    ans[id] = max(ans[id << 1], ans[id << 1 | 1]);
}

void updateH(int idx, ll val, int id = 1, int l = 1, int r = n + 1) {
    if (idx < l || r <= idx)
        return;
    if (l + 1 == r) {
        maxH[id] = val;
        return;
    }
    shift(id, l, r);
    int mid = (l + r) >> 1;
    updateH(idx, val, id << 1, l, mid);
    updateH(idx, val, id << 1 | 1, mid, r);
    maxH[id] = max(maxH[id << 1], maxH[id << 1 | 1]);
}

void shift(int id, int l, int r) {
    if (lazy[id] == -INF)
        return;
    int mid = (l + r) >> 1;
    updateAns(l, r, lazy[id], id << 1, l, mid);
    updateAns(l, r, lazy[id], id << 1 | 1, mid, r);
    lazy[id] = -INF;
}

void build(int id = 1, int l = 1, int r = n + 1) {
    ans[id] = -1;
    maxH[id] = lazy[id] = -INF;
    if (l + 1 == r)
        return;
    int mid = (l + r) >> 1;
    build(id << 1, l, mid);
    build(id << 1 | 1, mid, r);
}

void calcStEn() {
    for (int i = 1; i <= n; i++) {
        int u = i + a[i], v = i + b[i];
        if (u <= n)
            st[u].push_back(i);
        if (v <= n)
            en[u].push_back(i);
    }
}

void calcAns() {
    build();
    for (int i = 1; i <= n; i++) {
        for (auto idx: st[i])
            updateH(idx, h[idx]);
        int v = i - a[i], u = i - b[i];
        if (1 <= v) {
            u = max(1, u);
            updateAns(u, v + 1, -h[i]);
        }
        for (auto [l, idx]: query[i])
            res[idx] = max(res[ idx], get(l, i + 1));
        for (auto idx: en[i])
            updateH(idx, -INF);
    }
}

void solve() {
    for (int i = 1; i <= q; i++)
        res[i] = -1;
    calcAns();
    for (int i = 1; i <= n; i++)
        h[i] = -h[i];
    calcAns();
}

void writeOutput() {
    for (int i = 1; i <= q; i++)
        cout << res[i] << '\n';
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    readInput();
    calcStEn();
    solve();
    writeOutput();
    return 0;
}

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