oj.uz

Submission #927969

# Submission time Handle Problem Language Result Execution time Memory
927969 2024-02-15T15:20:33 Z borisAngelov Triple Jump (JOI19_jumps) C++17
100 / 100
 860 ms 110896 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 57692 KB Output is correct
2 Correct 11 ms 57692 KB Output is correct
3 Correct 11 ms 57856 KB Output is correct
4 Correct 11 ms 57692 KB Output is correct
5 Correct 11 ms 57804 KB Output is correct
6 Correct 11 ms 57908 KB Output is correct
7 Correct 11 ms 57788 KB Output is correct
8 Correct 11 ms 57692 KB Output is correct
9 Correct 11 ms 57692 KB Output is correct
10 Correct 11 ms 57692 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 57692 KB Output is correct
2 Correct 11 ms 57692 KB Output is correct
3 Correct 11 ms 57856 KB Output is correct
4 Correct 11 ms 57692 KB Output is correct
5 Correct 11 ms 57804 KB Output is correct
6 Correct 11 ms 57908 KB Output is correct
7 Correct 11 ms 57788 KB Output is correct
8 Correct 11 ms 57692 KB Output is correct
9 Correct 11 ms 57692 KB Output is correct
10 Correct 11 ms 57692 KB Output is correct
11 Correct 231 ms 74756 KB Output is correct
12 Correct 238 ms 74836 KB Output is correct
13 Correct 223 ms 74836 KB Output is correct
14 Correct 235 ms 74736 KB Output is correct
15 Correct 244 ms 74832 KB Output is correct
16 Correct 223 ms 74228 KB Output is correct
17 Correct 230 ms 73992 KB Output is correct
18 Correct 221 ms 74072 KB Output is correct
19 Correct 237 ms 74772 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 66428 KB Output is correct
2 Correct 83 ms 68688 KB Output is correct
3 Correct 87 ms 68692 KB Output is correct
4 Correct 143 ms 68172 KB Output is correct
5 Correct 141 ms 68040 KB Output is correct
6 Correct 137 ms 67516 KB Output is correct
7 Correct 141 ms 67188 KB Output is correct
8 Correct 136 ms 67408 KB Output is correct
9 Correct 168 ms 67664 KB Output is correct

Subtask #4
54.0 / 54.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 57692 KB Output is correct
2 Correct 11 ms 57692 KB Output is correct
3 Correct 11 ms 57856 KB Output is correct
4 Correct 11 ms 57692 KB Output is correct
5 Correct 11 ms 57804 KB Output is correct
6 Correct 11 ms 57908 KB Output is correct
7 Correct 11 ms 57788 KB Output is correct
8 Correct 11 ms 57692 KB Output is correct
9 Correct 11 ms 57692 KB Output is correct
10 Correct 11 ms 57692 KB Output is correct
11 Correct 231 ms 74756 KB Output is correct
12 Correct 238 ms 74836 KB Output is correct
13 Correct 223 ms 74836 KB Output is correct
14 Correct 235 ms 74736 KB Output is correct
15 Correct 244 ms 74832 KB Output is correct
16 Correct 223 ms 74228 KB Output is correct
17 Correct 230 ms 73992 KB Output is correct
18 Correct 221 ms 74072 KB Output is correct
19 Correct 237 ms 74772 KB Output is correct
20 Correct 141 ms 66428 KB Output is correct
21 Correct 83 ms 68688 KB Output is correct
22 Correct 87 ms 68692 KB Output is correct
23 Correct 143 ms 68172 KB Output is correct
24 Correct 141 ms 68040 KB Output is correct
25 Correct 137 ms 67516 KB Output is correct
26 Correct 141 ms 67188 KB Output is correct
27 Correct 136 ms 67408 KB Output is correct
28 Correct 168 ms 67664 KB Output is correct
29 Correct 844 ms 105184 KB Output is correct
30 Correct 703 ms 104484 KB Output is correct
31 Correct 660 ms 104480 KB Output is correct
32 Correct 850 ms 105072 KB Output is correct
33 Correct 817 ms 105168 KB Output is correct
34 Correct 825 ms 102880 KB Output is correct
35 Correct 860 ms 102348 KB Output is correct
36 Correct 820 ms 102564 KB Output is correct
37 Correct 815 ms 103948 KB Output is correct
38 Correct 633 ms 110812 KB Output is correct
39 Correct 659 ms 110896 KB Output is correct
40 Correct 622 ms 107344 KB Output is correct
41 Correct 681 ms 107088 KB Output is correct
42 Correct 688 ms 106880 KB Output is correct
43 Correct 636 ms 108524 KB Output is correct
44 Correct 670 ms 110088 KB Output is correct
45 Correct 648 ms 110180 KB Output is correct
46 Correct 645 ms 107092 KB Output is correct
47 Correct 651 ms 106564 KB Output is correct
48 Correct 650 ms 106468 KB Output is correct
49 Correct 706 ms 108648 KB Output is correct
50 Correct 708 ms 108288 KB Output is correct
51 Correct 706 ms 108528 KB Output is correct
52 Correct 698 ms 105812 KB Output is correct
53 Correct 716 ms 105552 KB Output is correct
54 Correct 710 ms 105380 KB Output is correct
55 Correct 707 ms 107256 KB Output is correct