Submission #925833

#	Time	Username	Problem	Language	Result	Execution time	Memory
925833		boris_mihov	Triple Jump (JOI19_jumps)	C++17	100 / 100	801 ms	106764 KiB

jumps

#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <set>

typedef long long llong;
const int MAXN = 500000 + 10;
const int INF  = 2e9;

int n, q;
struct SegmentTree
{
    struct Node
    {
        int maxAB;
        int maxC;
        int lazy;
        int max;

        Node()
        {
            maxAB = maxC = lazy = max = 0;
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            res.maxC = std::max(left.maxC, right.maxC);
            res.max = std::max(left.max, right.max);
            return res;
        }
    };

    Node tree[4*MAXN];
    void push(int node, int l, int r)
    {
        if (tree[node].lazy == 0)
        {
            return;
        }

        tree[node].maxAB = std::max(tree[node].maxAB, tree[node].lazy);
        if (tree[node].maxAB != 0)
        {
            tree[node].max = std::max(tree[node].max, tree[node].maxAB + tree[node].maxC);
        }

        if (l < r)
        {
            tree[2*node].lazy = std::max(tree[2*node].lazy, tree[node].lazy);
            tree[2*node + 1].lazy = std::max(tree[2*node + 1].lazy, tree[node].lazy);
        }

        tree[node].lazy = 0;
    }

    void build(int l, int r, int node, int a[])
    {
        tree[node] = Node();
        if (l == r)
        {
            tree[node].maxC = a[l];
            return;
        }

        int mid = (l + r) / 2;
        build(l, mid, 2*node, a);
        build(mid + 1, r, 2*node + 1, a);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    void update(int l, int r, int node, int queryL, int queryR, int queryVal)
    {
        push(node, l, r);
        if (queryR < l || r < queryL)
        {
            return;
        }

        if (queryL <= l && r <= queryR)
        {
            tree[node].lazy = queryVal;
            push(node, l, r);
            return;
        }

        int mid = (l + r) / 2;
        update(l, mid, 2*node, queryL, queryR, queryVal);
        update(mid + 1, r, 2*node + 1, queryL, queryR, queryVal);
        tree[node] = tree[2*node] + tree[2*node + 1];
    }

    int query(int l, int r, int node, int queryL, int queryR)
    {
        push(node, l, r);
        if (queryL <= l && r <= queryR)
        {
            return tree[node].max;
        }

        int res = 0;
        int mid = (l + r) / 2;
        if (queryL <= mid) res = std::max(res, query(l, mid, 2*node, queryL, queryR));
        if (mid + 1 <= queryR) res = std::max(res, query(mid + 1, r, 2*node + 1, queryL, queryR));
        return res;
    }

    void build(int a[])
    {
        build(1, n, 1, a);
    }

    void update(int l, int r, int val)
    {
        update(1, n, 1, l, r, val);
    }

    int query(int l, int r)
    {
        return query(1, n, 1, l, r);
    }
};

int a[MAXN];

int answer[MAXN];
std::vector <int> pairs[MAXN];
std::vector <std::pair <int,int>> queries[MAXN];
std::stack <int> st;
SegmentTree tree;

void solve()
{
    for (int i = n ; i >= 1 ; --i)
    {
        while (st.size() && a[st.top()] <= a[i])
        {
            pairs[i].push_back(st.top());
            st.pop();
        }

        if (st.size())
        {
            pairs[i].push_back(st.top());
        }

        st.push(i);
    }

    tree.build(a);
    for (int i = n ; i >= 1 ; --i)
    {
        for (const int &next : pairs[i])
        {
            if (2 * next - i <= n)
            {
                tree.update(2 * next - i, n, a[i] + a[next]);
            }
        }

        for (const auto &[r, idx] : queries[i])
        {
            answer[idx] = tree.query(i, r);
        }
    }
}

void print()
{
    for (int i = 1 ; i <= q ; ++i)
    {
        std::cout << answer[i] << '\n';
    }
}

void input()
{
    std::cin >> n;
    for (int i = 1 ; i <= n ; ++i)
    {
        std::cin >> a[i];
    }

    std::cin >> q;
    for (int i = 1 ; i <= q ; ++i)
    {
        int l, r;
        std::cin >> l >> r;
        queries[l].push_back({r, i});
    }
}

void fastIOI()
{
    std::ios_base :: sync_with_stdio(0);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
}   

int main()
{
    fastIOI();
    input();
    solve();
    print();

    return 0;
}

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