Submission #147508

#	Time	Username	Problem	Language	Result	Execution time	Memory
147508		kuroni	Triple Jump (JOI19_jumps)	C++17	100 / 100	1348 ms	89468 KiB

jumps

#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;

const int N = 500005, Q = 500005;

int n, q, l, r, a[N], ans[Q];
vector<int> pos;
vector<pair<int, int>> upd[N], que[N];

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

    int tot[4 * N], cur[4 * N] , lz[4 * N];

    void apply(int i, int v)
    {
        lz[i] = max(lz[i], v);
        tot[i] = max(tot[i], cur[i] + lz[i]);
    }

    void down(int i)
    {
        apply(lc, lz[i]);
        apply(rc, lz[i]);
        lz[i] = 0;
    }

    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)
        {
            apply(i, v);
            return;
        }
        down(i);
        update_range(l, m, lc, L, R, v);
        update_range(m + 1, r, rc, L, R, v);
        tot[i] = max(tot[lc], tot[rc]);
    }

    void update_node(int l, int r, int i, int u, int v)
    {
        if (l > u || r < u)
            return;
        if (l == r)
        {
            cur[i] = v; lz[i] = 0;
            apply(i, 0);
            return;
        }
        down(i);
        if (u <= m)
            update_node(l, m, lc, u, v);
        else
            update_node(m + 1, r, rc, u, v);
        cur[i] = max(cur[lc], cur[rc]);
        tot[i] = max(tot[lc], tot[rc]);
    }

    int query(int l, int r, int i, int L, int R)
    {
        if (l > R || r < L || L > R)
            return 0;
        else if (L <= l && r <= R)
            return tot[i];
        down(i);
        return max(query(l, m, lc, L, R), query(m + 1, r, rc, L, R));
    }

#undef m
#undef lc
#undef rc
} seg;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        while (!pos.empty())
        {
            int u = pos.back();
            if (2 * i - u <= n)
                upd[2 * i - u].push_back({u, a[i] + a[u]});
            if (a[u] <= a[i])
                pos.pop_back();
            else
                break;
        }
        pos.push_back(i);
    }
    cin >> q;
    for (int i = 1; i <= q; i++)
    {
        cin >> l >> r;
        que[r].push_back({l, i});
    }
    for (int i = 1; i <= n; i++)
    {
        for (pair<int, int> &v : upd[i])
            seg.update_node(1, n, 1, v.fi, v.se);
        seg.update_range(1, n, 1, 1, i, a[i]);
        for (pair<int, int> &v : que[i])
            ans[v.se] = seg.query(1, n, 1, v.fi, i);
    }
    for (int i = 1; i <= q; i++)
        cout << ans[i] << '\n';
}

• Subtask 1: 5 / 5
• Subtask 2: 14 / 14
• Subtask 3: 27 / 27
• Subtask 4: 54 / 54