oj.uz

Submission #925064

# Submission time Handle Problem Language Result Execution time Memory
925064 2024-02-10T16:05:30 Z boris_mihov Triple Jump (JOI19_jumps) C++17
5 / 100
 3336 ms 319276 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 313480 KB Output is correct
2 Correct 86 ms 313424 KB Output is correct
3 Correct 85 ms 313376 KB Output is correct
4 Correct 86 ms 313400 KB Output is correct
5 Correct 87 ms 313424 KB Output is correct
6 Correct 83 ms 313384 KB Output is correct
7 Correct 97 ms 313388 KB Output is correct
8 Correct 85 ms 313420 KB Output is correct
9 Correct 86 ms 313528 KB Output is correct
10 Correct 90 ms 313436 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 313480 KB Output is correct
2 Correct 86 ms 313424 KB Output is correct
3 Correct 85 ms 313376 KB Output is correct
4 Correct 86 ms 313400 KB Output is correct
5 Correct 87 ms 313424 KB Output is correct
6 Correct 83 ms 313384 KB Output is correct
7 Correct 97 ms 313388 KB Output is correct
8 Correct 85 ms 313420 KB Output is correct
9 Correct 86 ms 313528 KB Output is correct
10 Correct 90 ms 313436 KB Output is correct
11 Correct 3336 ms 318808 KB Output is correct
12 Correct 1193 ms 318800 KB Output is correct
13 Correct 1224 ms 318648 KB Output is correct
14 Correct 3253 ms 319276 KB Output is correct
15 Correct 3288 ms 318432 KB Output is correct
16 Incorrect 3295 ms 318112 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 314272 KB Output is correct
2 Correct 120 ms 314144 KB Output is correct
3 Correct 118 ms 314192 KB Output is correct
4 Correct 124 ms 314192 KB Output is correct
5 Correct 122 ms 314316 KB Output is correct
6 Incorrect 122 ms 314192 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 313480 KB Output is correct
2 Correct 86 ms 313424 KB Output is correct
3 Correct 85 ms 313376 KB Output is correct
4 Correct 86 ms 313400 KB Output is correct
5 Correct 87 ms 313424 KB Output is correct
6 Correct 83 ms 313384 KB Output is correct
7 Correct 97 ms 313388 KB Output is correct
8 Correct 85 ms 313420 KB Output is correct
9 Correct 86 ms 313528 KB Output is correct
10 Correct 90 ms 313436 KB Output is correct
11 Correct 3336 ms 318808 KB Output is correct
12 Correct 1193 ms 318800 KB Output is correct
13 Correct 1224 ms 318648 KB Output is correct
14 Correct 3253 ms 319276 KB Output is correct
15 Correct 3288 ms 318432 KB Output is correct
16 Incorrect 3295 ms 318112 KB Output isn't correct
17 Halted 0 ms 0 KB -