Submission #927969

#	Time	Username	Problem	Language	Result	Execution time	Memory
927969		borisAngelov	Triple Jump (JOI19_jumps)	C++17	100 / 100	860 ms	110896 KiB

jumps

#include <bits/stdc++.h>

using namespace std;

const int maxn = 500005;

int n, q;
int a[maxn];

vector<int> jumpsByPos[maxn];
int prv[maxn];
int nxt[maxn];

void findJumps()
{
    stack<int> st;

    for (int i = 1; i <= n; ++i)
    {
        while (!st.empty() && a[i] > a[st.top()])
        {
            st.pop();
        }

        if (!st.empty())
        {
            jumpsByPos[st.top()].push_back(i);
            prv[i] = st.top();
        }
        else
        {
            prv[i] = -1;
        }

        st.push(i);
    }

    while (!st.empty())
    {
        st.pop();
    }

    for (int i = n; i >= 1; --i)
    {
        while (!st.empty() && a[i] > a[st.top()])
        {
            st.pop();
        }

        if (!st.empty())
        {
            jumpsByPos[i].push_back(st.top());
            nxt[i] = st.top();
        }
        else
        {
            nxt[i] = -1;
        }

        st.push(i);
    }

    /*for (int i = 1; i <= n; ++i)
    {
        cout << i << " -> ";

        for (int j = 0; j < jumpsByPos[i].size(); ++j)
        {
            cout << jumpsByPos[i][j] << ' ';
        }

        cout << endl;
    }*/
}

struct SegmentTree
{
    struct Node
    {
        int maxInit;
        int maxByJump;
        int ans;

        Node()
        {
            maxInit = 0;
            maxByJump = 0;
            ans = 0;
        }
    };

    Node tree[4 * maxn];

    int lazy[4 * maxn];

    void build(int node, int l, int r)
    {
        lazy[node] = 0;

        if (l == r)
        {
            tree[node].maxInit = a[l];
            return;
        }

        int mid = (l + r) / 2;

        build(2 * node, l, mid);
        build(2 * node + 1, mid + 1, r);

        tree[node].maxInit = max(tree[2 * node].maxInit, tree[2 * node + 1].maxInit);
        tree[node].ans = max(tree[2 * node].ans, tree[2 * node + 1].ans);
    }

    void pushLazy(int node, int l, int r)
    {
        tree[node].maxByJump = max(tree[node].maxByJump, lazy[node]);

        if (tree[node].maxByJump != 0)
        {
            tree[node].ans = max(tree[node].ans, tree[node].maxByJump + tree[node].maxInit);
        }

        if (l != r)
        {
            lazy[2 * node] = max(lazy[2 * node], lazy[node]);
            lazy[2 * node + 1] = max(lazy[2 * node + 1], lazy[node]);
        }

        lazy[node] = 0;
    }

    void update(int node, int l, int r, int ql, int qr, int val)
    {
        pushLazy(node, l, r);

        if (l > qr || r < ql)
        {
            return;
        }

        if (ql <= l && r <= qr)
        {
            lazy[node] = max(lazy[node], val);
            pushLazy(node, l, r);
            return;
        }

        int mid = (l + r) / 2;

        update(2 * node, l, mid, ql, qr, val);
        update(2 * node + 1, mid + 1, r, ql, qr, val);

        tree[node].ans = max(tree[2 * node].ans, tree[2 * node + 1].ans);
    }

    int query(int node, int l, int r, int ql, int qr)
    {
        pushLazy(node, l, r);

        if (l > qr || r < ql)
        {
            return 0;
        }

        if (ql <= l && r <= qr)
        {
            return tree[node].ans;
        }

        int mid = (l + r) / 2;

        return max(query(2 * node, l, mid, ql, qr), query(2 * node + 1, mid + 1, r, ql, qr));
    }

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

    void update(int l, int r, int val)
    {
        update(1, 1, n, l, r, val);
    }

    int query(int l, int r)
    {
        return query(1, 1, n, l, r);
    }
};

SegmentTree tree;

vector<pair<int, int>> queries[maxn];
int answers[maxn];

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n;

    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }

    findJumps();

    cin >> q;

    for (int i = 1; i <= q; ++i)
    {
        int l, r;
        cin >> l >> r;
        queries[l].push_back(make_pair(r, i));
    }

    tree.build();

    for (int i = n - 2; i >= 1; --i)
    {
        for (int j = 0; j < jumpsByPos[i].size(); ++j)
        {
            int pos = jumpsByPos[i][j] - i + jumpsByPos[i][j];

            if (pos <= n)
            {
                tree.update(pos, n, a[i] + a[jumpsByPos[i][j]]);
            }
        }

        for (int j = 0; j < queries[i].size(); ++j)
        {
            answers[queries[i][j].second] = tree.query(i, queries[i][j].first);
        }
    }

    for (int i = 1; i <= q; ++i)
    {
        cout << answers[i] << "\n";
    }

    return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int main()':
jumps.cpp:230:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  230 |         for (int j = 0; j < jumpsByPos[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~
jumps.cpp:240:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  240 |         for (int j = 0; j < queries[i].size(); ++j)
      |                         ~~^~~~~~~~~~~~~~~~~~~

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