oj.uz

Submission #479850

# Submission time Handle Problem Language Result Execution time Memory
479850 2021-10-13T14:25:52 Z alextodoran Triple Jump (JOI19_jumps) C++17
0 / 100
 847 ms 57748 KB 
/**
 ____ ____ ____ ____ ____
||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;
}

set <pair <int, int>> s;

void update (int l, int AB)
{
    int r = s.upper_bound(make_pair(AB, INT_MAX))->second - 1;
    if(l <= r)
    {
        update(l, r, AB);
        s.insert(make_pair(AB, l));
    }
}

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(make_pair(0, 1));
        s.insert(make_pair(INT_MAX, N + 1));

        for(int l = N; l >= 1; l--)
        {
            for(int b : bs[l])
                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] << " ";
    cout << "\n";

    return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Incorrect 13 ms 23816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Incorrect 13 ms 23816 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 847 ms 57748 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23756 KB Output is correct
2 Incorrect 13 ms 23816 KB Output isn't correct
3 Halted 0 ms 0 KB -