oj.uz

Submission #447005

# Submission time Handle Problem Language Result Execution time Memory
447005 2021-07-24T08:12:29 Z blue Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 84832 KB 
#include "jumps.h"
#include <vector>
#include <iostream>
#include <stack>
using namespace std;

const int maxN = 200'000;
const int logN = 18;
const int INF = 1e9;

int N;
vector<int> H(2+maxN);

vector<int> leftHigh(2+maxN);
vector<int> rightHigh(2+maxN);

vector< vector<int> > highEdge(2+maxN, vector<int>(logN));
vector< vector<int> > lowEdge(2+maxN, vector<int>(logN));
vector< vector<int> > rightEdge(2+maxN, vector<int>(logN));



struct segtree
{
    int l;
    int r;

    int mn = -INF;
    int mx = INF;

    segtree* left = NULL;
    segtree* right = NULL;

    segtree()
    {
        ;
    }

    segtree(int L, int R)
    {
        l = L;
        r = R;
        if(l == r)
        {
            mn = mx = H[l];
        }
        else
        {
            int m = (l+r)/2;
            left = new segtree(l, m);
            right = new segtree(m+1, r);
            mn = min(left->mn, right->mn);
            mx = max(left->mx, right->mx);
        }
    }

    int rangemax(int L, int R)
    {
        if(R < l || r < L) return -INF;
        else if(L <= l && r <= R) return mx;
        else return max(left->rangemax(L, R), right->rangemax(L, R));
    }

    int rangemin(int L, int R)
    {
        if(R < l || r < L) return INF;
        else if(L <= l && r <= R) return mn;
        else return min(left->rangemin(L, R), right->rangemin(L, R));
    }
};

segtree ST;


void init(int n, vector<int> h)
{
    N = n;

    H[0] = H[N+1] = INF;
    for(int i = 1; i <= N; i++) H[i] = h[i-1];


    stack<int> S;


    leftHigh[0] = 0;
    S.push(0);
    for(int i = 1; i <= N; i++)
    {
        while(!S.empty() && H[S.top()] < H[i])
            S.pop();

        if(!S.empty()) leftHigh[i] = S.top();

        S.push(i);
    }
    while(!S.empty()) S.pop();
    leftHigh[N+1] = N+1;





    rightHigh[N+1] = N+1;
    S.push(N+1);
    for(int i = N; i >= 1; i--)
    {
        while(!S.empty() && H[S.top()] < H[i])
            S.pop();

        if(!S.empty()) rightHigh[i] = S.top();

        S.push(i);
    }
    leftHigh[0] = 0;

    // for(int i = 0; i <= N+1; i++) cerr << leftHigh[i] << ' ';
    // cerr << '\n';
    // for(int i = 0; i <= N+1; i++) cerr << rightHigh[i] << ' ';
    // cerr << '\n';


    highEdge[0][0] = 0;
    lowEdge[0][0] = 0;
    rightEdge[0][0] = 0;

    for(int i = 1; i <= N; i++)
    {
        highEdge[i][0] = (H[ leftHigh[i] ] > H[ rightHigh[i] ]) ? leftHigh[i] : rightHigh[i];
        lowEdge[i][0] = (H[ leftHigh[i] ] < H[ rightHigh[i] ]) ? leftHigh[i] : rightHigh[i];
        rightEdge[i][0] = rightHigh[i];
    }

    highEdge[N+1][0] = N+1;
    lowEdge[N+1][0] = N+1;
    rightEdge[N+1][0] = N+1;



    for(int e = 1; e < logN; e++)
    {
        for(int i = 0; i <= N+1; i++)
        {
            highEdge[i][e] = highEdge[ highEdge[i][e-1] ][e-1];
            lowEdge[i][e] = lowEdge[ lowEdge[i][e-1] ][e-1];
            rightEdge[i][e] = rightEdge[ rightEdge[i][e-1] ][e-1];
        }
    }



    ST = segtree(0, N+1);
}









int minimum_jumps(int A, int B, int C, int D)
{
    A++;
    B++;
    C++;
    D++;

    int oldB = B;

    int CDmax = ST.rangemax(C, D);

    if(ST.rangemax(B, oldB) > CDmax) return -1;
    while(A != B)
    {
        int m = (A+B)/2;
        if(ST.rangemax(m, oldB) <= CDmax) B = m;
        else A = m+1;
    }
    for(int bit = logN-1; bit >= 0; bit--)
    {
        int newA = A + (1 << bit);
        if(newA > oldB) continue;
        if(ST.rangemax(A, oldB) == ST.rangemax(newA, oldB)) A = newA;
    }

    // cerr << "A = B = " << A << '\n';

    int o = A;

    int res = 0;
    while(1)
    {
        if(C <= o && o <= D) return res;
        else if(o > D || H[o] > CDmax) return -1;
        else if(highEdge[o][0] < C && H[highEdge[o][0]] <= CDmax/* && lowEdge[o][0] < C*/)
        {
            o = highEdge[o][0];
            res++;
        }
        else
        {
            o = rightEdge[o][0];
            res++;
        }
    }

    // for(int bit = logN-1; bit >= 0; bit--)
    // {
    //     if(C <= o && o <= D) return res;
    //     else if(o > D || H[o] > CDmax) return -1;
    //     else if(highEdge[o][bit] < C && H[highEdge[o][bit]] <= CDmax && lowEdge[o][0] < C)
    //     {
    //         o = highEdge[o][bit];
    //         res += (1 << bit);
    //     }
    // }
    //
    // for(int bit = logN-1; bit >= 0; bit--)
    // {
    //     if(C <= o && o <= D) return res;
    //     else if(o > D || H[o] > CDmax) return -1;
    //     else if(rightEdge[o][bit] < C)
    //     {
    //         o = rightEdge[o][bit];
    //         res += (1 << bit);
    //     }
    // }
    //
    // if(o < C)
    // {
    //     o = rightEdge[o][0];
    //     res++;
    // }
    // if(D < o) return -1;

    return res;
}

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 63720 KB Output is correct
2 Correct 54 ms 63720 KB Output is correct
3 Execution timed out 4069 ms 80428 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 63680 KB Output is correct
2 Correct 52 ms 63680 KB Output is correct
3 Correct 53 ms 63696 KB Output is correct
4 Correct 52 ms 63584 KB Output is correct
5 Correct 54 ms 63636 KB Output is correct
6 Incorrect 55 ms 63720 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 63680 KB Output is correct
2 Correct 52 ms 63680 KB Output is correct
3 Correct 53 ms 63696 KB Output is correct
4 Correct 52 ms 63584 KB Output is correct
5 Correct 54 ms 63636 KB Output is correct
6 Incorrect 55 ms 63720 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 63704 KB Output is correct
2 Correct 52 ms 63680 KB Output is correct
3 Correct 52 ms 63696 KB Output is correct
4 Correct 60 ms 63700 KB Output is correct
5 Correct 166 ms 80032 KB Output is correct
6 Correct 193 ms 83948 KB Output is correct
7 Correct 121 ms 74108 KB Output is correct
8 Correct 200 ms 83940 KB Output is correct
9 Correct 70 ms 66740 KB Output is correct
10 Correct 191 ms 84044 KB Output is correct
11 Correct 208 ms 84828 KB Output is correct
12 Correct 193 ms 84392 KB Output is correct
13 Correct 183 ms 84512 KB Output is correct
14 Correct 212 ms 83932 KB Output is correct
15 Incorrect 246 ms 83980 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 63680 KB Output is correct
2 Correct 56 ms 63676 KB Output is correct
3 Correct 65 ms 63624 KB Output is correct
4 Correct 416 ms 72972 KB Output is correct
5 Correct 1393 ms 84032 KB Output is correct
6 Correct 634 ms 66972 KB Output is correct
7 Correct 1159 ms 84028 KB Output is correct
8 Correct 956 ms 70720 KB Output is correct
9 Correct 1470 ms 83928 KB Output is correct
10 Execution timed out 4027 ms 84832 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 53 ms 63680 KB Output is correct
2 Correct 56 ms 63676 KB Output is correct
3 Correct 65 ms 63624 KB Output is correct
4 Correct 416 ms 72972 KB Output is correct
5 Correct 1393 ms 84032 KB Output is correct
6 Correct 634 ms 66972 KB Output is correct
7 Correct 1159 ms 84028 KB Output is correct
8 Correct 956 ms 70720 KB Output is correct
9 Correct 1470 ms 83928 KB Output is correct
10 Execution timed out 4027 ms 84832 KB Time limit exceeded
11 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 63720 KB Output is correct
2 Correct 54 ms 63720 KB Output is correct
3 Execution timed out 4069 ms 80428 KB Time limit exceeded
4 Halted 0 ms 0 KB -