Submission #604216

#	Time	Username	Problem	Language	Result	Execution time	Memory
604216		elkernos	Two Antennas (JOI19_antennas)	C++17	100 / 100	746 ms	45164 KiB

antennas

#include <bits/stdc++.h>

using namespace std;

struct ant {
    int h, a, b;
    void read() { cin >> h >> a >> b; }
};

const int oo = 1e9 + 213;

struct T {
    int d = -1, c = 0, lazy = oo;
    void merge(T l, T r)
    {
        assert(lazy == oo);
        d = max({d, l.d, r.d}); // why:c
        c = max(l.c, r.c);
    }
};

const int nax = 2e5 + 213;

struct tree {
#define lc 2 * v
#define rc 2 * v + 1
#define m (l + r) / 2
    vector<T> t = vector<T>(4 * nax);
    void push(int v, int l, int r)
    {
        if(t[v].lazy == oo) {
            return;
        }
        if(l != r) {
            for(int to : {lc, rc}) {
                t[to].lazy = min(t[to].lazy, t[v].lazy);
            }
        }
        t[v].d = max(t[v].d, t[v].c - t[v].lazy);
        t[v].lazy = oo;
    }
    void setC(int v, int l, int r, int p, int x)
    {
        push(v, l, r);
        if(l == r) {
            t[v].c = x;
            return;
        }
        if(p <= m) {
            setC(lc, l, m, p, x);
        }
        else {
            setC(rc, m + 1, r, p, x);
        }
        t[v].merge(t[lc], t[rc]);
    }
    void putLazy(int v, int l, int r, int ql, int qr, int x)
    {
        push(v, l, r);
        if(ql <= l && r <= qr) {
            t[v].lazy = x;
            push(v, l, r);
            return;
        }
        if(ql <= m) {
            putLazy(lc, l, m, ql, qr, x);
        }
        if(m < qr) {
            putLazy(rc, m + 1, r, ql, qr, x);
        }
        t[v].merge(t[lc], t[rc]);
    }
    int query(int v, int l, int r, int ql, int qr)
    {
        push(v, l, r);
        if(ql <= l && r <= qr) {
            return t[v].d;
        }
        int ret = -1;
        if(ql <= m) {
            ret = max(ret, query(lc, l, m, ql, qr));
        }
        if(m < qr) {
            ret = max(ret, query(rc, m + 1, r, ql, qr));
        }
        t[v].merge(t[lc], t[rc]);
        return ret;
    }
};

int32_t main()
{
    cin.tie(0)->sync_with_stdio(0);
    int n;
    cin >> n;
    vector<ant> in(n + 1);
    for(int i = 1; i <= n; i++) {
        in[i].read();
    }
    int q;
    cin >> q;
    vector<int> ql(q + 1), qr(q + 1), ans(q + 1, -1);
    for(int i = 1; i <= q; i++) {
        cin >> ql[i] >> qr[i];
    }
    auto solve = [&]() {
        vector<vector<int>> qs(n + 1), st(n + 1), en(n + 1);
        tree seg;
        for(int i = 1; i <= q; i++) {
            qs[qr[i]].emplace_back(i);
        }
        for(int i = 1; i <= n; i++) {
            if(i + in[i].a <= n) {
                st[i + in[i].a].emplace_back(i);
            }
            if(i + in[i].b <= n) {
                en[i + in[i].b].emplace_back(i);
            }
            for(int j : st[i]) {
                seg.setC(1, 1, n, j, in[j].h);
            }
            if(i - in[i].a >= 1) {
                seg.putLazy(1, 1, n, max(1, i - in[i].b), i - in[i].a, in[i].h);
            }
            for(int j : qs[i]) {
                ans[j] = max(ans[j], seg.query(1, 1, n, ql[j], qr[j]));
            }
            for(int j : en[i]) {
                seg.setC(1, 1, n, j, 0);
            }
        }
    };
    solve();
    reverse(1 + in.begin(), in.end());
    for(int i = 1; i <= q; i++) {
        ql[i] = n - ql[i] + 1;
        qr[i] = n - qr[i] + 1;
        swap(ql[i], qr[i]);
    }
    solve();
    for(int i = 1; i <= q; i++) {
        cout << ans[i] << '\n';
    }
}

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