oj.uz

Submission #925060

# Submission time Handle Problem Language Result Execution time Memory
925060 2024-02-10T15:59:28 Z boris_mihov Triple Jump (JOI19_jumps) C++17
5 / 100
 3931 ms 323148 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 query(int l, int r, int node, int queryL, int queryR)
    {
        if (queryL <= l && r <= queryR)
        {
            return tree[node];
        }

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

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

    Node query(int l, int r)
    {
        return 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;
        SegmentTree::Node res = tree.query(l, r);
        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 141 ms 313460 KB Output is correct
2 Correct 91 ms 313460 KB Output is correct
3 Correct 90 ms 313688 KB Output is correct
4 Correct 92 ms 313532 KB Output is correct
5 Correct 98 ms 313428 KB Output is correct
6 Correct 90 ms 313532 KB Output is correct
7 Correct 91 ms 313424 KB Output is correct
8 Correct 89 ms 313424 KB Output is correct
9 Correct 91 ms 313424 KB Output is correct
10 Correct 91 ms 313424 KB Output is correct

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 313460 KB Output is correct
2 Correct 91 ms 313460 KB Output is correct
3 Correct 90 ms 313688 KB Output is correct
4 Correct 92 ms 313532 KB Output is correct
5 Correct 98 ms 313428 KB Output is correct
6 Correct 90 ms 313532 KB Output is correct
7 Correct 91 ms 313424 KB Output is correct
8 Correct 89 ms 313424 KB Output is correct
9 Correct 91 ms 313424 KB Output is correct
10 Correct 91 ms 313424 KB Output is correct
11 Correct 3878 ms 323108 KB Output is correct
12 Correct 1583 ms 323148 KB Output is correct
13 Correct 1627 ms 323092 KB Output is correct
14 Correct 3774 ms 323116 KB Output is correct
15 Correct 3841 ms 323120 KB Output is correct
16 Incorrect 3931 ms 322288 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 130 ms 315984 KB Output is correct
2 Correct 129 ms 315924 KB Output is correct
3 Correct 121 ms 316076 KB Output is correct
4 Correct 128 ms 315936 KB Output is correct
5 Correct 141 ms 315932 KB Output is correct
6 Incorrect 126 ms 315228 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 313460 KB Output is correct
2 Correct 91 ms 313460 KB Output is correct
3 Correct 90 ms 313688 KB Output is correct
4 Correct 92 ms 313532 KB Output is correct
5 Correct 98 ms 313428 KB Output is correct
6 Correct 90 ms 313532 KB Output is correct
7 Correct 91 ms 313424 KB Output is correct
8 Correct 89 ms 313424 KB Output is correct
9 Correct 91 ms 313424 KB Output is correct
10 Correct 91 ms 313424 KB Output is correct
11 Correct 3878 ms 323108 KB Output is correct
12 Correct 1583 ms 323148 KB Output is correct
13 Correct 1627 ms 323092 KB Output is correct
14 Correct 3774 ms 323116 KB Output is correct
15 Correct 3841 ms 323120 KB Output is correct
16 Incorrect 3931 ms 322288 KB Output isn't correct
17 Halted 0 ms 0 KB -