Submission #479855

#	Time	Username	Problem	Language	Result	Execution time	Memory
479855		alextodoran	Triple Jump (JOI19_jumps)	C++17	100 / 100	1306 ms	107900 KiB

jumps

/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N_MAX = 500000;
const int Q_MAX = 500000;

int N;

int A[N_MAX + 2];

int Q;

int L[Q_MAX + 2], R[Q_MAX + 2];

vector <int> queries[N_MAX + 2];

vector <int> bs[N_MAX + 2];

struct SGTNode
{
    int AB;
    int maxC;
    int maxABC;
};

SGTNode operator + (const SGTNode &u, const SGTNode &v)
{
    return SGTNode{0, max(u.maxC, v.maxC), max(u.maxABC, v.maxABC)};
}
void operator += (SGTNode &u, const int &AB)
{
    u.AB = AB;
    u.maxABC = u.maxC + AB;
}

SGTNode SGT[N_MAX * 4 + 2];

void build (int node, int l, int r)
{
    if(l == r)
    {
        SGT[node].AB = 0;
        SGT[node].maxC = A[l];
        SGT[node].maxABC = INT_MIN;
        return;
    }

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;

    build(lSon, l, mid);
    build(rSon, mid + 1, r);

    SGT[node] = SGT[lSon] + SGT[rSon];
}
void build ()
{
    build(1, 1, N);
}

void split (int node)
{
    if(SGT[node].AB == 0)
        return;

    int lSon = node * 2, rSon = node * 2 + 1;
    SGT[lSon] += SGT[node].AB;
    SGT[rSon] += SGT[node].AB;

    SGT[node].AB = 0;
}

void update (int node, int l, int r, int ul, int ur, int AB)
{
    if(ul <= l && r <= ur)
    {
        SGT[node] += AB;
        return;
    }

    split(node);

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;

    if(ul <= mid)
        update(lSon, l, mid, ul, ur, AB);
    if(mid + 1 <= ur)
        update(rSon, mid + 1, r, ul, ur, AB);

    SGT[node] = SGT[lSon] + SGT[rSon];
}
void update (int ul, int ur, int AB)
{
    update(1, 1, N, ul, ur, AB);
}

SGTNode query (int node, int l, int r, int ql, int qr)
{
    if(ql <= l && r <= qr)
        return SGT[node];

    split(node);

    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;

    if(ql <= mid && mid + 1 <= qr)
        return query(lSon, l, mid, ql, qr) + query(rSon, mid + 1, r, ql, qr);
    else if(ql <= mid)
        return query(lSon, l, mid, ql, qr);
    else
        return query(rSon, mid + 1, r, ql, qr);
}
int query (int ql, int qr)
{
    return query(1, 1, N, ql, qr).maxABC;
}
int brute (int l, int r)
{
    int mx = 0;
    for(int a = l; a <= r; a++)
        for(int b = a + 1; b <= r; b++)
            for(int c = b * 2 - a; c <= r; c++)
                mx = max(mx, A[a] + A[b] + A[c]);
    return mx;
}

set <pair <int, int>> s;

void update (int l, int AB)
{
    set <pair <int, int>> :: iterator it = s.upper_bound({l, INT_MAX});

    if(prev(it)->second >= AB)
        return;
    while(it->second <= AB)
    {
        it++;
        s.erase(prev(it));
    }

    update(l, it->first - 1, AB);
    s.insert(make_pair(l, AB));
}

int answer[Q_MAX + 2];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N;
    for(int i = 1; i <= N; i++)
        cin >> A[i];

    {
        vector <int> st;
        for(int i = 1; i <= N; i++)
        {
            while(st.empty() == false && A[st.back()] <= A[i])
            {
                bs[st.back()].push_back(i);
                st.pop_back();
            }

            if(st.empty() == false)
                bs[st.back()].push_back(i);
            st.push_back(i);
        }
    }

    cin >> Q;
    for(int i = 1; i <= Q; i++)
        cin >> L[i] >> R[i];

    {
        for(int i = 1; i <= Q; i++)
            queries[L[i]].push_back(i);

        build();
        s.insert({1, 0});
        s.insert({N + 1, INT_MAX});

        for(int l = N; l >= 1; l--)
        {
            for(int b : bs[l])
                if(b * 2 - l <= N)
                    update(b * 2 - l, A[l] + A[b]);
            for(int i : queries[l])
                answer[i] = query(l, R[i]);
        }
    }

    for(int i = 1; i <= Q; i++)
        cout << answer[i] << "\n";

    return 0;
}

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