Submission #760364

#	Time	Username	Problem	Language	Result	Execution time	Memory
760364		danikoynov	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1090 ms	44164 KiB

jumps

#include "jumps.h"

#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10, maxlog = 21;
int n, h[maxn], left_child[maxn], right_child[maxn];
int dp[maxlog][maxn], fp[maxlog][maxn];
bool sorted;

struct node
{
    int mx, pos;

    node(int _mx = 0, int _pos = 0)
    {
        mx = _mx;
        pos = _pos;
    }
};

node merge_node(node lf, node rf)
{
    node nd;
    if (lf.mx > rf.mx)
        nd = lf;
    else
        nd = rf;
    return nd;
}

node tree[4 * maxn];
void build_tree(int root, int left, int right)
{
    if (left == right)
    {
        tree[root].mx = h[left];
        tree[root].pos = left;
        return;
    }

    int mid = (left + right) / 2;
    build_tree(root * 2, left, mid);
    build_tree(root * 2 + 1, mid + 1, right);

    tree[root] = merge_node(tree[root * 2], tree[root * 2 + 1]);
}

node query(int root, int left, int right, int qleft, int qright)
{
    if (left > qright || right < qleft)
        return node();

    if (left >= qleft && right <= qright)
        return tree[root];

    int mid = (left + right) / 2;
    return merge_node(query(root * 2, left, mid, qleft, qright),
                      query(root * 2 + 1, mid + 1, right, qleft, qright));
}

int walk(int root, int left, int right, int qleft, int qright, int val)
{
    if (left > qright || right < qleft || tree[root].mx < val)
        return qleft - 1;
        if (left == right)
            return left;
    int mid = (left + right) / 2;
    if (left >= qleft && right <= qright)
    {
        if (tree[root * 2 + 1].mx > val)
            return walk(root * 2 + 1, mid + 1, right, qleft, qright, val);
        return walk(root * 2, left, mid, qleft, qright, val);
    }

    return max(walk(root * 2, left, mid, qleft, qright, val),
               walk(root * 2 + 1, mid + 1, right, qleft, qright, val));
}
void init(int N, vector<int> H)
{
    n = N;
    for (int i = 0; i < N; i ++)
    {
        left_child[i + 1] = right_child[i + 1] = 0;
        h[i + 1] = H[i];
    }
    sorted = true;
    for (int i = 1; i <= N; i ++)
        if (h[i] < h[i - 1])
            sorted = false;

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

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

    for (int i = n; i > 0; i --)
    {
        while(!st.empty() && h[i] > h[st.top()])
            st.pop();
        if (!st.empty())
            right_child[i] = st.top();
        st.push(i);
    }

    h[0] = 1e9;
    for (int i = 1; i <= n; i ++)
    {
        if (h[left_child[i]] > h[right_child[i]])
            dp[0][i] = left_child[i];
        else
            dp[0][i] = right_child[i];

        fp[0][i] = right_child[i];
    }

    for (int j = 1; j < maxlog; j ++)
        for (int i = 1; i <= n; i ++)
        {
            dp[j][i] = dp[j - 1][dp[j - 1][i]];
            fp[j][i] = fp[j - 1][fp[j - 1][i]];
        }

        build_tree(1, 1, n);
}


int used[maxn];

int minimum_jumps(int A, int B, int C, int D)
{
    if (sorted)
        return C - B;
    A ++;
    B ++;
    C ++;
    D ++;
    if (A == B && C == D)
    {
        int ver = A, ans = 0;

        for (int bit = maxlog - 1; bit >= 0; bit --)
        {
            if (h[dp[bit][ver]] < h[C])
            {
                ans = ans + (1 << bit);
                ver = dp[bit][ver];
            }
        }
        for (int bit = maxlog - 1; bit >= 0; bit --)
        {
            if (h[fp[bit][ver]] < h[C])
            {
                ans = ans + (1 << bit);
                ver = fp[bit][ver];
            }
        }
        if (right_child[ver] == C)
            return ans + 1;
        return -1;
    }

    if (C == D)
    {
        int gt = walk(1, 1, n, A, B, h[C]);
        int pos = -1;
        if (gt != B)
        {
            node cur = query(1, 1, n, gt + 1, B);
            pos = cur.pos;
        }
        /**for (int i = B; i >= A; i --)
        {
            if (h[i] > h[C])
                break;
            if (pos == -1 || h[i] > h[pos])
                pos = i;
        }*/
        if (pos == -1)
            return -1;
        ///cout << pos << " : " << h[pos] << " : "<< h[C] << endl;
        int ver = pos, ans = 0;

        for (int bit = maxlog - 1; bit >= 0; bit --)
        {
            if (h[dp[bit][ver]] < h[C])
            {
                ans = ans + (1 << bit);
                ver = dp[bit][ver];
            }
        }

        for (int bit = maxlog - 1; bit >= 0; bit --)
        {
            if (h[fp[bit][ver]] < h[C])
            {
                ans = ans + (1 << bit);
                ver = fp[bit][ver];
            }
        }
        ///cout << "here " << ver << " " << right_child[ver] << " " << h[right_child[ver]] << endl;
        if (right_child[ver] == C)
            return ans + 1;
        return -1;
    }

    int max_tree = query(1, 1, n, C, D).mx;
    int gt = walk(1, 1, n, A, B, max_tree);
        int pos = -1;
        if (gt != B)
        {
            node cur = query(1, 1, n, gt + 1, B);
            pos = cur.pos;
        }
        if (pos == -1)
            return -1;
            int  ans = 0;
    int ver = pos;

        for (int bit = maxlog - 1; bit >= 0; bit --)
        {
            if (h[dp[bit][ver]] <= max_tree && (right_child[dp[bit][ver]] < C && right_child[dp[bit][ver]] != 0))
            {
                ans = ans + (1 << bit);
                ver = dp[bit][ver];
            }
        }
        if (right_child[ver] >= C && right_child[ver] <= D)
            return ans + 1;
        if (h[dp[0][ver]] <= max_tree)
            ans ++, ver = dp[0][ver];
        for (int bit = maxlog - 1; bit >= 0; bit --)
        {
            if (h[fp[bit][ver]] <= max_tree && fp[bit][ver] < C)
            {
                ans = ans + (1 << bit);
                ver = fp[bit][ver];
            }
        }
                if (right_child[ver] >= C && right_child[ver] <= D)
            return ans + 1;
            return -1;

     ans = 1e9;
    for (int i = 1; i <= n; i ++)
        used[i] = 0;

    queue < int > q;
    q.push(pos);
    used[pos] = 1;
    /**for (int i = A; i <= B; i ++)
    {
        q.push(i);
        used[i] = 1;
    }*/
//cout << "------------" << endl;
    while(!q.empty())
    {
        int cur = q.front();
        q.pop();
        ///cout << cur << endl;
        if (left_child[cur] != 0 && used[left_child[cur]] == 0)
        {
            used[left_child[cur]] = used[cur] + 1;
            q.push(left_child[cur]);
        }
        if (right_child[cur] != 0 && used[right_child[cur]] == 0)
        {
            used[right_child[cur]] = used[cur] + 1;
            q.push(right_child[cur]);
        }
    }

    for (int to = C; to <= D; to ++)
    {
        ///cout << "here "<< to << " " << used[to] << endl;
        if (used[to] != 0)
        {
            ans = min(ans, used[to] - 1);
        }
    }

    if (ans == 1e9)
        return -1;
    return ans;
}

Compilation message (stderr)

jumps.cpp: In function 'int walk(int, int, int, int, int, int)':
jumps.cpp:64:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   64 |     if (left > qright || right < qleft || tree[root].mx < val)
      |     ^~
jumps.cpp:66:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   66 |         if (left == right)
      |         ^~
jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:125:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  125 |     for (int j = 1; j < maxlog; j ++)
      |     ^~~
jumps.cpp:132:9: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  132 |         build_tree(1, 1, n);
      |         ^~~~~~~~~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:223:9: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  223 |         if (pos == -1)
      |         ^~
jumps.cpp:225:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  225 |             int  ans = 0;
      |             ^~~

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19