Submission #1264251

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264251		tvgk	Two Antennas (JOI19_antennas)	C++20	100 / 100	310 ms	40748 KiB

antennas

#include<bits/stdc++.h>
using namespace std;
#define task "a"
#define se second
#define fi first
#define ll long long
#define ii pair<int, int>
const long mxN = 2e5 + 7, inf = 1e9 + 7;

struct Segment
{
    int mn, mx, node;
};

Segment tree[mxN * 4];
int h[mxN], n, l[mxN], r[mxN], ans[mxN];
ii lazy[mxN * 4];
vector<int> seg[mxN * 2];
vector<ii> querry[mxN];

void Build(int j = 1, int l = 1, int r = n)
{
    tree[j].mn = inf;
    tree[j].mx = -inf;
    tree[j].node = -1;
    if (l == r)
        return;

    int mid = (l + r) / 2;
    Build(j * 2, l, mid);
    Build(j * 2 + 1, mid + 1, r);
}

void Down(int j)
{
    for (int id = 0; id <= 1; id++)
    {
        tree[j * 2 + id].node = max({tree[j * 2 + id].node, tree[j * 2 + id].mx - lazy[j].fi, lazy[j].se - tree[j * 2 + id].mn});
        lazy[j * 2 + id].fi = min(lazy[j].fi, lazy[j * 2 + id].fi);
        lazy[j * 2 + id].se = max(lazy[j * 2 + id].se, lazy[j].se);
    }

    lazy[j] = {inf, -inf};
}

void Up(int j)
{
    tree[j].mx = max(tree[j * 2].mx, tree[j * 2 + 1].mx);
    tree[j].mn = min(tree[j * 2].mn, tree[j * 2 + 1].mn);
    tree[j].node = max(tree[j * 2].node, tree[j * 2 + 1].node);
}

void Upd(int vt, ii nw, int j = 1, int l = 1, int r = n)
{
    if (l > vt || vt > r)
        return;

    if (l == r)
    {
        tree[j].mn = nw.fi;
        tree[j].mx = nw.se;
        return;
    }
    Down(j);

    int mid = (l + r) / 2;
    Upd(vt, nw, j * 2, l, mid);
    Upd(vt, nw, j * 2 + 1, mid + 1, r);
    Up(j);
}

void Rev(int u, int v, int val, int j = 1, int l = 1, int r = n)
{
    if (u > r || l > v)
        return;

    if (u <= l && r <= v)
    {
        tree[j].node = max({tree[j].node, tree[j].mx - val, val - tree[j].mn});
        lazy[j].fi = min(lazy[j].fi, val);
        lazy[j].se = max(lazy[j].se, val);
        return;
    }
    Down(j);

    int mid = (l + r) / 2;
    Rev(u, v, val, j * 2, l, mid);
    Rev(u, v, val, j * 2 + 1, mid + 1, r);
    Up(j);
}

int Get(int u, int v, int j = 1, int l = 1, int r = n)
{
    if (u > r || l > v)
        return -1;

    if (u <= l && r <= v)
        return tree[j].node;
    Down(j);

    int mid = (l + r) / 2;
    int res = max(Get(u, v, j * 2, l, mid), Get(u, v, j * 2 + 1, mid + 1, r));
    Up(j);
    return res;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen(task".INP", "r", stdin);
    //freopen(task".OUT", "w", stdout);

    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> h[i] >> l[i] >> r[i];
        seg[i + l[i]].push_back(i);
        seg[i + r[i] + 1].push_back(-i);
    }
    Build();

    int q;
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        int u, v;
        cin >> u >> v;
        querry[v].push_back({u, i});
    }

    for (int i = 1; i <= n; i++)
    {
        for (int j : seg[i])
        {
            if (j > 0)
                Upd(j, {h[j], h[j]});
            else
                Upd(abs(j), {inf, -inf});
        }

        Rev(i - r[i], i - l[i], h[i]);

        for (ii j : querry[i])
            ans[j.se] = Get(j.fi, i);
    }

    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