Submission #447011

#	Time	Username	Problem	Language	Result	Execution time	Memory
447011		blue	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	3476 ms	125616 KiB

jumps

#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));

vector< vector<int> > highEdge_highmax(2+maxN, vector<int>(logN));
vector< vector<int> > highEdge_lowmax(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;

    highEdge_highmax[0][0] = 0;
    highEdge_lowmax[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];
    }
    for(int i = 1; i <= N; i++)
    {
        highEdge_highmax[i][0] = highEdge[i][0];
        highEdge_lowmax[i][0] = lowEdge[i][0];
    }

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

    highEdge_highmax[N+1][0] = N+1;
    highEdge_lowmax[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];

            highEdge_highmax[i][e] = max(highEdge_highmax[i][e-1], highEdge_highmax[ highEdge[i][e-1] ][e-1]);
            highEdge_lowmax[i][e] = max(highEdge_lowmax[i][e-1], highEdge_lowmax[ highEdge[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_highmax[o][bit] < C && H[highEdge[o][bit]] <= CDmax && highEdge_lowmax[o][bit] < 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: 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