Submission #1222900

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222900		minhpk	Two Antennas (JOI19_antennas)	C++20	100 / 100	589 ms	30064 KiB

antennas

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

#define mid ((l + r) >> 1)

const int INF = 1e9;

int n, m;
int a[200200], b[200200], h[200200], ans[200200];
int t[800800], t2[800800], lz[800800];
vector<int> in[200200], out[200200];

void lazy_update(int node, int l, int r) {
    if (lz[node]) {
        t2[node] = max(t2[node], lz[node] - t[node]);
        if (l != r) {
            lz[node*2]     = max(lz[node*2],     lz[node]);
            lz[node*2+1]   = max(lz[node*2+1],   lz[node]);
        }
        lz[node] = 0;
    }
}

void update(int nl, int nr, int val, int node = 1, int l = 1, int r = n) {
    lazy_update(node, l, r);
    if (nr < l || r < nl) return;
    if (nl <= l && r <= nr) {
        lz[node] = max(lz[node], val);
        lazy_update(node, l, r);
        return;
    }
    update(nl, nr, val, node*2,     l, mid);
    update(nl, nr, val, node*2+1, mid+1, r);
    t[node]  = min(t[node*2],     t[node*2+1]);
    t2[node] = max(t2[node*2], t2[node*2+1]);
}

void update2(int pos, int val, int node = 1, int l = 1, int r = n) {
    lazy_update(node, l, r);
    if (pos < l || r < pos) return;
    if (l == r) {
        t[node] = val;
        lazy_update(node, l, r);
        return;
    }
    update2(pos, val, node*2,     l, mid);
    update2(pos, val, node*2+1, mid+1, r);
    t[node]  = min(t[node*2],     t[node*2+1]);
    t2[node] = max(t2[node*2], t2[node*2+1]);
}

int find(int nl, int nr, int node = 1, int l = 1, int r = n) {
    lazy_update(node, l, r);
    if (nr < l || r < nl) return -INF;
    if (nl <= l && r <= nr) return t2[node];
    return max(
        find(nl, nr, node*2,     l, mid),
        find(nl, nr, node*2+1, mid+1, r)
    );
}

void solve(vector<array<int,3>>& q) {
    fill(t,  t + 4*n + 1, INF + 10);
    fill(t2, t2 + 4*n + 1,    -INF);
    fill(lz, lz + 4*n + 1,      0);

    int L = 0;
    for (auto [r, l, id] : q) {
        while (L < r) {
            int u = ++L;
            for (int x : in[u])  update2(x,     h[x]);
            for (int x : out[u]) update2(x, INF + 10);
            int left  = max(1, u - b[u]);
            int right = max(0, u - a[u]);
            if (left <= right) update(left, right, h[u]);
        }
        ans[id] = max(ans[id], find(l, r));
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> h[i] >> a[i] >> b[i];
    }
    for (int i = 1; i <= n; i++) {
        if (i + a[i] <= n)    in[i + a[i]].push_back(i);
        if (i + b[i] <= n)   out[i + b[i] + 1].push_back(i);
    }

    cin >> m;
    vector<array<int,3>> q(m);
    for (int i = 0; i < m; i++) {
        cin >> q[i][1] >> q[i][0];
        q[i][2] = i;
        ans[i]  = -1;
    }
    sort(q.begin(), q.end());

    solve(q);

    for (int i = 1; i <= n; i++) {
        h[i] = INF - h[i] + 1;
    }
    for (int i = 1; i <= n+1; i++) {
        in[i].clear();
        out[i].clear();
    }
    for (int i = 1; i <= n; i++) {
        if (i + a[i] <= n)    in[i + a[i]].push_back(i);
        if (i + b[i] <= n)   out[i + b[i] + 1].push_back(i);
    }

    solve(q);

    for (int i = 0; i < m; i++) {
        cout << ans[i] << "\n";
    }
    return 0;
}

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