oj.uz

Submission #447007

# Submission time Handle Problem Language Result Execution time Memory
447007 2021-07-24T08:19:55 Z blue Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 3379 ms 125492 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));

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[ highEdge[i][0] ][0];
        highEdge_lowmax[i][0] = lowEdge[ highEdge[i][0] ][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][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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 104380 KB Output is correct
2 Correct 84 ms 104380 KB Output is correct
3 Correct 575 ms 121248 KB Output is correct
4 Correct 3143 ms 125488 KB Output is correct
5 Correct 2647 ms 115008 KB Output is correct
6 Correct 2736 ms 125468 KB Output is correct
7 Correct 2105 ms 118852 KB Output is correct
8 Correct 3379 ms 125472 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 104360 KB Output is correct
2 Correct 114 ms 104300 KB Output is correct
3 Correct 87 ms 104328 KB Output is correct
4 Correct 89 ms 104428 KB Output is correct
5 Correct 99 ms 104332 KB Output is correct
6 Incorrect 104 ms 104492 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 104360 KB Output is correct
2 Correct 114 ms 104300 KB Output is correct
3 Correct 87 ms 104328 KB Output is correct
4 Correct 89 ms 104428 KB Output is correct
5 Correct 99 ms 104332 KB Output is correct
6 Incorrect 104 ms 104492 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 101 ms 104336 KB Output is correct
2 Correct 92 ms 104384 KB Output is correct
3 Correct 92 ms 104384 KB Output is correct
4 Correct 109 ms 104360 KB Output is correct
5 Correct 265 ms 120676 KB Output is correct
6 Correct 296 ms 124640 KB Output is correct
7 Correct 202 ms 114856 KB Output is correct
8 Correct 289 ms 124736 KB Output is correct
9 Correct 136 ms 107508 KB Output is correct
10 Correct 313 ms 124752 KB Output is correct
11 Correct 297 ms 125492 KB Output is correct
12 Correct 288 ms 125028 KB Output is correct
13 Incorrect 285 ms 125316 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 104300 KB Output is correct
2 Correct 90 ms 104296 KB Output is correct
3 Correct 92 ms 104324 KB Output is correct
4 Incorrect 428 ms 113596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 104300 KB Output is correct
2 Correct 90 ms 104296 KB Output is correct
3 Correct 92 ms 104324 KB Output is correct
4 Incorrect 428 ms 113596 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 104380 KB Output is correct
2 Correct 84 ms 104380 KB Output is correct
3 Correct 575 ms 121248 KB Output is correct
4 Correct 3143 ms 125488 KB Output is correct
5 Correct 2647 ms 115008 KB Output is correct
6 Correct 2736 ms 125468 KB Output is correct
7 Correct 2105 ms 118852 KB Output is correct
8 Correct 3379 ms 125472 KB Output is correct
9 Correct 115 ms 104360 KB Output is correct
10 Correct 114 ms 104300 KB Output is correct
11 Correct 87 ms 104328 KB Output is correct
12 Correct 89 ms 104428 KB Output is correct
13 Correct 99 ms 104332 KB Output is correct
14 Incorrect 104 ms 104492 KB Output isn't correct
15 Halted 0 ms 0 KB -