Submission #925064

#	Time	Username	Problem	Language	Result	Execution time	Memory
925064		boris_mihov	Triple Jump (JOI19_jumps)	C++17	5 / 100	3336 ms	319276 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 NEEDED_ELEMENTS = 40;
const int MAXN = 500000 + 10;
const int INF  = 2e9;

int n, q;
int a[MAXN];
struct SegmentTree
{
    struct Node
    {
        int vals[NEEDED_ELEMENTS];
        Node()
        {
            std::fill(vals, vals + NEEDED_ELEMENTS, 0);
        }

        friend Node operator + (const Node &left, const Node &right)
        {
            Node res;
            int lPtr = 0;
            int rPtr = 0;
            int ptr = 0;

            while (ptr < NEEDED_ELEMENTS)
            {
                if (a[left.vals[lPtr]] > a[right.vals[rPtr]])
                {
                    res.vals[ptr++] = left.vals[lPtr++];
                } else
                {
                    res.vals[ptr++] = right.vals[rPtr++];
                }
            }

            return res;
        }
    };

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

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

    Node res;
    void query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            res = res + tree[node];
            return;
        }

        int mid = (l + r) / 2;
        if (queryL <= mid) query(l, mid, 2*node, queryL, queryR);
        if (mid + 1 <= queryR) query(mid + 1, r, 2*node + 1, queryL, queryR);
    }

    void build()
    {
        build(1, n, 1);
    }

    void query(int l, int r)
    {
        res = Node();
        query(1, n, 1, l, r);
    }
};

int suffMAX[NEEDED_ELEMENTS];   
SegmentTree tree;
void solve()
{
    tree.build();
    for (int i = 1 ; i <= q ; ++i)
    {
        int l, r;
        int answer = 0;
        std::cin >> l >> r;

        tree.query(l, r);
        SegmentTree::Node res = tree.res;
        std::sort(res.vals, res.vals + NEEDED_ELEMENTS);

        suffMAX[NEEDED_ELEMENTS - 1] = a[res.vals[NEEDED_ELEMENTS - 1]];
        for (int i = NEEDED_ELEMENTS - 2 ; i >= 0 ; --i)
        {
            suffMAX[i] = std::max(suffMAX[i + 1], a[res.vals[i]]);
        }

        for (int aPos = 0 ; aPos < NEEDED_ELEMENTS ; aPos++)
        {
            if (res.vals[aPos] == 0)
            {
                continue;
            }

            int cPos = aPos + 2;
            for (int bPos = aPos + 1 ; bPos < NEEDED_ELEMENTS ; bPos++)
            {
                while (cPos < NEEDED_ELEMENTS && res.vals[cPos] < 2 * res.vals[bPos] - res.vals[aPos])
                {
                    cPos++;
                }

                if (cPos == NEEDED_ELEMENTS)
                {
                    break;
                }

                answer = std::max(answer, a[res.vals[aPos]] + a[res.vals[bPos]] + suffMAX[cPos]);
            }
        }

        std::cout << answer << '\n';
    }
}

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

    std::cin >> q;
}

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

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

    return 0;
}

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