oj.uz

Submission #447002

# Submission time Handle Problem Language Result Execution time Memory
447002 2021-07-24T08:08:48 Z blue Rainforest Jumps (APIO21_jumps) C++17
48 / 100
 3466 ms 84856 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
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 63704 KB Output is correct
2 Correct 55 ms 63676 KB Output is correct
3 Correct 463 ms 80528 KB Output is correct
4 Correct 3157 ms 84776 KB Output is correct
5 Correct 2515 ms 74244 KB Output is correct
6 Correct 3466 ms 84832 KB Output is correct
7 Correct 2533 ms 78132 KB Output is correct
8 Correct 2772 ms 84800 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 63668 KB Output is correct
2 Correct 53 ms 63632 KB Output is correct
3 Correct 60 ms 63680 KB Output is correct
4 Correct 55 ms 63700 KB Output is correct
5 Correct 55 ms 63632 KB Output is correct
6 Correct 57 ms 63680 KB Output is correct
7 Correct 56 ms 63720 KB Output is correct
8 Correct 57 ms 63680 KB Output is correct
9 Correct 67 ms 63680 KB Output is correct
10 Incorrect 56 ms 63684 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 63668 KB Output is correct
2 Correct 53 ms 63632 KB Output is correct
3 Correct 60 ms 63680 KB Output is correct
4 Correct 55 ms 63700 KB Output is correct
5 Correct 55 ms 63632 KB Output is correct
6 Correct 57 ms 63680 KB Output is correct
7 Correct 56 ms 63720 KB Output is correct
8 Correct 57 ms 63680 KB Output is correct
9 Correct 67 ms 63680 KB Output is correct
10 Incorrect 56 ms 63684 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 63788 KB Output is correct
2 Correct 56 ms 63608 KB Output is correct
3 Correct 55 ms 63668 KB Output is correct
4 Correct 54 ms 63644 KB Output is correct
5 Correct 167 ms 79980 KB Output is correct
6 Correct 201 ms 84056 KB Output is correct
7 Correct 126 ms 73992 KB Output is correct
8 Correct 214 ms 84032 KB Output is correct
9 Correct 71 ms 66784 KB Output is correct
10 Correct 190 ms 83944 KB Output is correct
11 Correct 187 ms 84856 KB Output is correct
12 Correct 181 ms 84340 KB Output is correct
13 Correct 208 ms 84644 KB Output is correct
14 Correct 193 ms 84024 KB Output is correct
15 Incorrect 231 ms 84004 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 63596 KB Output is correct
2 Correct 53 ms 63584 KB Output is correct
3 Correct 53 ms 63724 KB Output is correct
4 Correct 385 ms 72980 KB Output is correct
5 Correct 1264 ms 83996 KB Output is correct
6 Correct 855 ms 67008 KB Output is correct
7 Correct 1294 ms 83948 KB Output is correct
8 Correct 813 ms 70688 KB Output is correct
9 Correct 1468 ms 83936 KB Output is correct
10 Correct 1647 ms 84776 KB Output is correct
11 Correct 1548 ms 84108 KB Output is correct
12 Correct 1490 ms 84660 KB Output is correct
13 Correct 1205 ms 83928 KB Output is correct
14 Correct 1627 ms 84060 KB Output is correct
15 Correct 1352 ms 84024 KB Output is correct
16 Correct 1312 ms 84032 KB Output is correct
17 Correct 53 ms 63668 KB Output is correct
18 Correct 53 ms 63688 KB Output is correct
19 Correct 58 ms 63684 KB Output is correct
20 Correct 58 ms 63632 KB Output is correct
21 Correct 58 ms 63680 KB Output is correct
22 Correct 59 ms 63712 KB Output is correct
23 Correct 58 ms 63644 KB Output is correct
24 Correct 57 ms 63680 KB Output is correct
25 Correct 57 ms 63680 KB Output is correct
26 Correct 58 ms 63780 KB Output is correct
27 Correct 80 ms 63884 KB Output is correct
28 Correct 69 ms 63912 KB Output is correct
29 Correct 82 ms 63900 KB Output is correct
30 Correct 69 ms 63940 KB Output is correct
31 Correct 68 ms 63904 KB Output is correct
32 Correct 54 ms 63680 KB Output is correct
33 Correct 140 ms 75416 KB Output is correct
34 Correct 193 ms 84012 KB Output is correct
35 Correct 202 ms 84668 KB Output is correct
36 Correct 198 ms 84036 KB Output is correct
37 Correct 254 ms 84064 KB Output is correct
38 Correct 179 ms 83964 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 63596 KB Output is correct
2 Correct 53 ms 63584 KB Output is correct
3 Correct 53 ms 63724 KB Output is correct
4 Correct 385 ms 72980 KB Output is correct
5 Correct 1264 ms 83996 KB Output is correct
6 Correct 855 ms 67008 KB Output is correct
7 Correct 1294 ms 83948 KB Output is correct
8 Correct 813 ms 70688 KB Output is correct
9 Correct 1468 ms 83936 KB Output is correct
10 Correct 1647 ms 84776 KB Output is correct
11 Correct 1548 ms 84108 KB Output is correct
12 Correct 1490 ms 84660 KB Output is correct
13 Correct 1205 ms 83928 KB Output is correct
14 Correct 1627 ms 84060 KB Output is correct
15 Correct 1352 ms 84024 KB Output is correct
16 Correct 1312 ms 84032 KB Output is correct
17 Correct 53 ms 63668 KB Output is correct
18 Correct 53 ms 63688 KB Output is correct
19 Correct 58 ms 63684 KB Output is correct
20 Correct 58 ms 63632 KB Output is correct
21 Correct 58 ms 63680 KB Output is correct
22 Correct 59 ms 63712 KB Output is correct
23 Correct 58 ms 63644 KB Output is correct
24 Correct 57 ms 63680 KB Output is correct
25 Correct 57 ms 63680 KB Output is correct
26 Correct 58 ms 63780 KB Output is correct
27 Correct 80 ms 63884 KB Output is correct
28 Correct 69 ms 63912 KB Output is correct
29 Correct 82 ms 63900 KB Output is correct
30 Correct 69 ms 63940 KB Output is correct
31 Correct 68 ms 63904 KB Output is correct
32 Correct 54 ms 63680 KB Output is correct
33 Correct 140 ms 75416 KB Output is correct
34 Correct 193 ms 84012 KB Output is correct
35 Correct 202 ms 84668 KB Output is correct
36 Correct 198 ms 84036 KB Output is correct
37 Correct 254 ms 84064 KB Output is correct
38 Correct 179 ms 83964 KB Output is correct
39 Correct 53 ms 63660 KB Output is correct
40 Correct 56 ms 63680 KB Output is correct
41 Correct 55 ms 63620 KB Output is correct
42 Correct 425 ms 72900 KB Output is correct
43 Correct 1454 ms 83936 KB Output is correct
44 Correct 571 ms 66984 KB Output is correct
45 Correct 1404 ms 84140 KB Output is correct
46 Correct 746 ms 70616 KB Output is correct
47 Correct 1340 ms 83948 KB Output is correct
48 Correct 1603 ms 84780 KB Output is correct
49 Correct 1733 ms 84192 KB Output is correct
50 Correct 1942 ms 84696 KB Output is correct
51 Correct 1650 ms 84020 KB Output is correct
52 Correct 1910 ms 83980 KB Output is correct
53 Correct 1350 ms 83980 KB Output is correct
54 Correct 1413 ms 84048 KB Output is correct
55 Correct 60 ms 63696 KB Output is correct
56 Correct 294 ms 83996 KB Output is correct
57 Correct 2024 ms 83952 KB Output is correct
58 Correct 858 ms 67232 KB Output is correct
59 Correct 1904 ms 84072 KB Output is correct
60 Correct 892 ms 70848 KB Output is correct
61 Correct 1934 ms 84020 KB Output is correct
62 Correct 3204 ms 84832 KB Output is correct
63 Correct 3271 ms 84412 KB Output is correct
64 Correct 2942 ms 84368 KB Output is correct
65 Correct 1895 ms 84032 KB Output is correct
66 Correct 3137 ms 83980 KB Output is correct
67 Correct 2308 ms 84004 KB Output is correct
68 Correct 1537 ms 84008 KB Output is correct
69 Correct 56 ms 63664 KB Output is correct
70 Correct 55 ms 63612 KB Output is correct
71 Correct 58 ms 63720 KB Output is correct
72 Correct 61 ms 63680 KB Output is correct
73 Correct 61 ms 63596 KB Output is correct
74 Correct 61 ms 63704 KB Output is correct
75 Correct 61 ms 63808 KB Output is correct
76 Correct 57 ms 63612 KB Output is correct
77 Correct 55 ms 63600 KB Output is correct
78 Correct 55 ms 63688 KB Output is correct
79 Correct 58 ms 63684 KB Output is correct
80 Correct 60 ms 63700 KB Output is correct
81 Correct 76 ms 63684 KB Output is correct
82 Correct 59 ms 63680 KB Output is correct
83 Correct 61 ms 63680 KB Output is correct
84 Correct 57 ms 63680 KB Output is correct
85 Correct 60 ms 63808 KB Output is correct
86 Correct 79 ms 63880 KB Output is correct
87 Correct 83 ms 63896 KB Output is correct
88 Correct 84 ms 63908 KB Output is correct
89 Correct 92 ms 63972 KB Output is correct
90 Correct 95 ms 63856 KB Output is correct
91 Correct 56 ms 63616 KB Output is correct
92 Correct 63 ms 63756 KB Output is correct
93 Correct 82 ms 63876 KB Output is correct
94 Correct 88 ms 63800 KB Output is correct
95 Correct 81 ms 63796 KB Output is correct
96 Correct 85 ms 63904 KB Output is correct
97 Correct 73 ms 63832 KB Output is correct
98 Correct 55 ms 63576 KB Output is correct
99 Correct 189 ms 83904 KB Output is correct
100 Correct 206 ms 83988 KB Output is correct
101 Correct 195 ms 84584 KB Output is correct
102 Correct 186 ms 83940 KB Output is correct
103 Correct 235 ms 84056 KB Output is correct
104 Correct 178 ms 84060 KB Output is correct
105 Correct 57 ms 63680 KB Output is correct
106 Correct 148 ms 75356 KB Output is correct
107 Correct 199 ms 83988 KB Output is correct
108 Correct 190 ms 84720 KB Output is correct
109 Correct 195 ms 83940 KB Output is correct
110 Correct 244 ms 83992 KB Output is correct
111 Correct 186 ms 84056 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 63704 KB Output is correct
2 Correct 55 ms 63676 KB Output is correct
3 Correct 463 ms 80528 KB Output is correct
4 Correct 3157 ms 84776 KB Output is correct
5 Correct 2515 ms 74244 KB Output is correct
6 Correct 3466 ms 84832 KB Output is correct
7 Correct 2533 ms 78132 KB Output is correct
8 Correct 2772 ms 84800 KB Output is correct
9 Correct 54 ms 63668 KB Output is correct
10 Correct 53 ms 63632 KB Output is correct
11 Correct 60 ms 63680 KB Output is correct
12 Correct 55 ms 63700 KB Output is correct
13 Correct 55 ms 63632 KB Output is correct
14 Correct 57 ms 63680 KB Output is correct
15 Correct 56 ms 63720 KB Output is correct
16 Correct 57 ms 63680 KB Output is correct
17 Correct 67 ms 63680 KB Output is correct
18 Incorrect 56 ms 63684 KB Output isn't correct
19 Halted 0 ms 0 KB -