Submission #1052177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052177		Szymon_Pilipczuk	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	4038 ms	3736 KiB

jumps

#include "jumps.h"

#include <algorithm>
#include <vector>
using namespace std;
int a[200000];
int dest[200000];
int dest2[200000];
int t1 = 1;
void init(int N, std::vector<int> H) {
for(int i = 0;i<N;i++)
{
    if (i+1 != H[i])
    {
        t1 = 0;
    }
    a[i] = H[i];
    dest[i] = 300000;
    dest2[i] = 300000;
    for (int j = i;j>=0;j--)
    {
        if (H[j] > H[i])
        {
            dest[i] = j;
            break;
        }
    }
    for(int j = i; j<N;j++)
    {
        if (H[j]>H[i])
        {
            dest2[i] = j;
            break;
        }
    }

}
}

int minimum_jumps(int A, int B, int C, int D) {
    if (t1 == 1)
    {
        return C-B;
    }
    else
    {
        int answer = 300000;
        for(int i = A;i<=B;i++)
        {
            for(int j = C;j<=D;j++)
            {


                int cu_i = i;
                int steps = 0;
                while(a[cu_i]<a[j])
                {
                    if(a[dest2[cu_i]]>a[j])
                    {
                        break;
                    }
                    if (a[dest[cu_i]]>a[j])
                    {
                        cu_i = dest2[cu_i];
                    }
                    else
                    {
                        if (a[dest2[cu_i]]>a[dest[cu_i]])
                        {
                            cu_i = dest2[cu_i];
                        }
                        else
                        {
                            cu_i = dest[cu_i];
                        }
                    }
                    steps++;
                    if (cu_i == j)
                    {
                        answer = min(answer,steps);
                    }
                }
            }
        }
        if (answer > 200000)
        {
            return -1;
        }
        return answer;
    }
}

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