oj.uz

Submission #925069

# Submission time Handle Problem Language Result Execution time Memory
925069 2024-02-10T16:14:32 Z boris_mihov Triple Jump (JOI19_jumps) C++17
0 / 100
 149 ms 394580 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 = 50;
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;
int b[MAXN];
void solve()
{
    SegmentTree::Node res;
    std::iota(b + 1, b + 1 + n, 1);
    std::sort(b + 1, b + 1 + n, [&](int x, int y)
    {
        return a[x] > a[y];
    });

    for (int i = 0 ; i < NEEDED_ELEMENTS ; ++i)
    {
        res.vals[i] = b[i + 1];
    }

    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]]);
    }

    int answer = 0;
    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';
    
    // 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 393552 KB Output is correct
2 Incorrect 123 ms 393776 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 125 ms 393552 KB Output is correct
2 Incorrect 123 ms 393776 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 149 ms 394372 KB Output is correct
2 Correct 134 ms 394564 KB Output is correct
3 Correct 148 ms 394452 KB Output is correct
4 Correct 148 ms 394324 KB Output is correct
5 Correct 146 ms 394376 KB Output is correct
6 Incorrect 140 ms 394580 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 393552 KB Output is correct
2 Incorrect 123 ms 393776 KB Output isn't correct
3 Halted 0 ms 0 KB -