Submission #925073

#	Time	Username	Problem	Language	Result	Execution time	Memory
925073		boris_mihov	Triple Jump (JOI19_jumps)	C++17	0 / 100	32 ms	3456 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;
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++)
        {
            for (int cPos = aPos + 2 ; cPos < NEEDED_ELEMENTS ; ++cPos)
            {
                if (res.vals[cPos] < 2 * res.vals[bPos] - res.vals[aPos]) continue;
                answer = std::max(answer, a[res.vals[aPos]] + a[res.vals[bPos]] + suffMAX[cPos]);
            }
            // while (cPos < NEEDED_ELEMENTS && res.vals[cPos] < 2 * res.vals[bPos] - res.vals[aPos])
            // {
            //     cPos++;
            // }

            // if (cPos == NEEDED_ELEMENTS)
            // {
            //     break;
            // }

        }
    }

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

Compilation message (stderr)

jumps.cpp: In function 'void solve()':
jumps.cpp:123:13: warning: unused variable 'cPos' [-Wunused-variable]
  123 |         int cPos = aPos + 2;
      |             ^~~~

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