Submission #943069

#	Time	Username	Problem	Language	Result	Execution time	Memory
943069		LOLOLO	Two Antennas (JOI19_antennas)	C++17	100 / 100	623 ms	43484 KiB

antennas

#include <bits/stdc++.h>
typedef long long ll;

#define           f    first
#define           s    second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int32_t)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)

using namespace std;
const int N = 2e5 + 10;
int h[N], a[N], b[N], ans[N];
vector <pair <int, int>> ask[N], event[N];
const int lim = 1e9 + 100;

struct node{
    int mx = -1, val = lim, lz = -1;
} seg[N * 4];

void add(node &C, node A, node B) {
    C.mx = max({A.mx, B.mx, C.mx});
    C.val = min(A.val, B.val);
}

void push(int id) {
    int t = seg[id].lz;
    seg[id * 2].lz = max(seg[id * 2].lz, t);
    seg[id * 2 + 1].lz = max(seg[id * 2 + 1].lz, t);
    seg[id * 2].mx = max(seg[id * 2].mx, t - seg[id * 2].val);
    seg[id * 2 + 1].mx = max(seg[id * 2 + 1].mx, t - seg[id * 2 + 1].val);
    seg[id].lz = -1;
}

void point(int id, int l, int r, int p, int i) {
    if (l > p || r < p)
        return;

    if (l == r) {
        if (i) {
            seg[id].val = h[p];
        } else {
            seg[id].val = lim;
        }
        return;
    }

    push(id);
    int m = (l + r) / 2;
    point(id * 2, l, m, p, i);
    point(id * 2 + 1, m + 1, r, p, i);
    add(seg[id], seg[id * 2], seg[id * 2 + 1]);
}

void upd(int id, int l, int r, int u, int v, int val) {
    if (l > v || r < u || u > v)
        return;

    if (l >= u && r <= v) {
        seg[id].mx = max(seg[id].mx, val - seg[id].val);
        seg[id].lz = max(seg[id].lz, val);
        return;
    }

    int m = (l + r) / 2;
    push(id);
    upd(id * 2, l, m, u, v, val);
    upd(id * 2 + 1, m + 1, r, u, v, val);
    add(seg[id], seg[id * 2], seg[id * 2 + 1]);
}

int get(int id, int l, int r, int u, int v) {
    if (l > v || r < u || u > v)
        return -1;


    if (l >= u && r <= v)
        return seg[id].mx;

    push(id);
    int m = (l + r) / 2;
    return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
}

int n, q, l[N], r[N];
void solve() {
    for (int i = 1; i <= n; i++) {
        if (i + a[i] <= n)
            event[i + a[i]].pb({i, 1});
        if (b[i] + i <= n)
            event[i + b[i] + 1].pb({i, 0});
    }

    for (int i = 1; i <= q; i++) {
        ask[r[i]].pb({l[i], i});
    }

    for (int i = 1; i <= n; i++) {
        for (auto x : event[i]) {
            point(1, 1, n, x.f, x.s);
        }

        int x = max(i - b[i], 1), y = max(0, i - a[i]);
        upd(1, 1, n, x, y, h[i]);
        for (auto x : ask[i]) {
            ans[x.s] = max(ans[x.s], get(1, 1, n, x.f, i));
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    mem(ans, -1);
    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];
    }

    solve();
    for (int i = 1; i <= n; i++) {
        event[i].clear();
        ask[i].clear();
    }

    for (int i = 1; i <= n * 4; i++) {
        seg[i].lz = -1;
        seg[i].mx = -1;
        seg[i].val = lim;
    }

    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]);
    }

    solve();

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

    return 0;
}

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