Submission #111910

#	Time	Username	Problem	Language	Result	Execution time	Memory
111910		kuroni	Two Antennas (JOI19_antennas)	C++17	100 / 100	1123 ms	50668 KiB

antennas

#include <iostream>
#include <cstdio>
#include <vector>
#define fi first
#define se second
using namespace std;

const int N = 200005, Q = 200005, INF = 1E9 + 7;

struct TNode
{
    int cur, per, mi, ma;

    TNode(int _cur = -INF, int _per = -INF, int _mi = INF)
    {
        cur = _cur;
        per = _per;
        mi = _mi;
        ma = -INF;
    }

    TNode operator+(const TNode &oth) const
    {
        return TNode(max(cur, oth.cur), max(per, oth.per), min(mi, oth.mi));
    }
};

struct TSegmentTree
{
#define m (l + r) / 2
#define lc i * 2
#define rc i * 2 + 1

    TNode tr[4 * N];

    void down(int i)
    {
        tr[lc].ma = max(tr[lc].ma, tr[i].ma);
        tr[lc].cur = max(tr[lc].cur, tr[lc].ma - tr[lc].mi);
        tr[rc].ma = max(tr[rc].ma, tr[i].ma);
        tr[rc].cur = max(tr[rc].cur, tr[rc].ma - tr[rc].mi);
        tr[i].ma = -INF;
    }

    void build(int l, int r, int i)
    {
        tr[i] = TNode();
        if (l == r)
            return;
        build(l, m, lc);
        build(m + 1, r, rc);
    }

    void update_range(int l, int r, int i, int L, int R, int v)
    {
        if (l > R || r < L || L > R)
            return;
        if (L <= l && r <= R)
        {
            tr[i].ma = max(tr[i].ma, v);
            tr[i].cur = max(tr[i].cur, v - tr[i].mi);
            return;
        }
        down(i);
        update_range(l, m, lc, L, R, v);
        update_range(m + 1, r, rc, L, R, v);
        tr[i] = tr[lc] + tr[rc];
    }

    void update_child(int l, int r, int i, int u, int v)
    {
        if (l == r)
        {
            tr[i].mi = v;
            if (v == INF)
                tr[i].per = tr[i].cur;
            else
                tr[i].ma = -INF;
            tr[i].cur = tr[i].ma - v;
            return;
        }
        down(i);
        if (u <= m)
            update_child(l, m, lc, u, v);
        else
            update_child(m + 1, r, rc, u, v);
        tr[i] = tr[lc] + tr[rc];
    }

    int query(int l, int r, int i, int L, int R)
    {
        if (l > R || r < L || L > R)
            return -INF;
        if (L <= l && r <= R)
            return max(tr[i].per, tr[i].cur);
        down(i);
        return max(query(l, m, lc, L, R), query(m + 1, r, rc, L, R));
    }

#undef m
#undef lc
#undef rc
} pos, neg;

int n, q, u, v, a[N], l[N], r[N], ans[Q];
vector<int> eve[N];
vector<pair<int, int>> que[N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    pos.build(1, n, 1); neg.build(1, n, 1);
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i] >> u >> v;
        l[i] = max(1, i - v); r[i] = i - u;
        eve[min(i + u, n + 1)].push_back(i); eve[min(i + v + 1, n + 1)].push_back(-i);
    }
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> u >> v;
        ans[i] = -INF;
        que[v].push_back({u, i});
    }
    for (int i = 1; i <= n; i++)
    {
        for (int &v : eve[i])
        {
            bool add = v > 0;
            v = (add ? v : -v);
            pos.update_child(1, n, 1, v, add ? a[v] : INF);
            neg.update_child(1, n, 1, v, add ? -a[v] : INF);
        }
        pos.update_range(1, n, 1, l[i], r[i], a[i]);
        neg.update_range(1, n, 1, l[i], r[i], -a[i]);
        for (pair<int, int> &v : que[i])
            ans[v.se] = max(ans[v.se], max(pos.query(1, n, 1, v.fi, i), neg.query(1, n, 1, v.fi, i)));
    }
    for (int i = 1; i <= q; i++)
        cout << (ans[i] < 0 ? -1 : ans[i]) << '\n';
}

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