oj.uz

Submission #447009

# Submission time Handle Problem Language Result Execution time Memory
447009 2021-07-24T08:21:07 Z blue Rainforest Jumps (APIO21_jumps) C++17
48 / 100
 3534 ms 125548 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[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][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 104388 KB Output is correct
2 Correct 86 ms 104412 KB Output is correct
3 Correct 577 ms 121328 KB Output is correct
4 Correct 2910 ms 125504 KB Output is correct
5 Correct 2205 ms 114976 KB Output is correct
6 Correct 2778 ms 125528 KB Output is correct
7 Correct 2526 ms 118848 KB Output is correct
8 Correct 3534 ms 125548 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 104372 KB Output is correct
2 Correct 105 ms 104348 KB Output is correct
3 Correct 109 ms 104280 KB Output is correct
4 Correct 112 ms 104412 KB Output is correct
5 Correct 97 ms 104356 KB Output is correct
6 Correct 92 ms 104360 KB Output is correct
7 Correct 105 ms 104432 KB Output is correct
8 Correct 108 ms 104376 KB Output is correct
9 Correct 95 ms 104384 KB Output is correct
10 Incorrect 97 ms 104420 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 104372 KB Output is correct
2 Correct 105 ms 104348 KB Output is correct
3 Correct 109 ms 104280 KB Output is correct
4 Correct 112 ms 104412 KB Output is correct
5 Correct 97 ms 104356 KB Output is correct
6 Correct 92 ms 104360 KB Output is correct
7 Correct 105 ms 104432 KB Output is correct
8 Correct 108 ms 104376 KB Output is correct
9 Correct 95 ms 104384 KB Output is correct
10 Incorrect 97 ms 104420 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 104400 KB Output is correct
2 Correct 88 ms 104360 KB Output is correct
3 Correct 117 ms 104340 KB Output is correct
4 Correct 88 ms 104404 KB Output is correct
5 Correct 278 ms 120772 KB Output is correct
6 Correct 316 ms 124736 KB Output is correct
7 Correct 190 ms 114816 KB Output is correct
8 Correct 290 ms 124672 KB Output is correct
9 Correct 119 ms 107452 KB Output is correct
10 Correct 286 ms 124664 KB Output is correct
11 Correct 283 ms 125504 KB Output is correct
12 Correct 282 ms 125012 KB Output is correct
13 Correct 284 ms 125248 KB Output is correct
14 Correct 296 ms 124668 KB Output is correct
15 Incorrect 427 ms 124688 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 90 ms 104424 KB Output is correct
2 Correct 102 ms 104456 KB Output is correct
3 Correct 88 ms 104328 KB Output is correct
4 Correct 523 ms 113684 KB Output is correct
5 Correct 1456 ms 124668 KB Output is correct
6 Correct 1006 ms 107768 KB Output is correct
7 Correct 1611 ms 124712 KB Output is correct
8 Correct 902 ms 111384 KB Output is correct
9 Correct 1439 ms 124728 KB Output is correct
10 Correct 1456 ms 125484 KB Output is correct
11 Correct 1793 ms 124908 KB Output is correct
12 Correct 1639 ms 125348 KB Output is correct
13 Correct 1417 ms 124828 KB Output is correct
14 Correct 1685 ms 124848 KB Output is correct
15 Correct 1093 ms 124724 KB Output is correct
16 Correct 1240 ms 124736 KB Output is correct
17 Correct 87 ms 104384 KB Output is correct
18 Correct 85 ms 104372 KB Output is correct
19 Correct 88 ms 104404 KB Output is correct
20 Correct 90 ms 104344 KB Output is correct
21 Correct 93 ms 104432 KB Output is correct
22 Correct 96 ms 104412 KB Output is correct
23 Correct 92 ms 104436 KB Output is correct
24 Correct 92 ms 104384 KB Output is correct
25 Correct 90 ms 104396 KB Output is correct
26 Correct 90 ms 104500 KB Output is correct
27 Correct 124 ms 104608 KB Output is correct
28 Correct 119 ms 104512 KB Output is correct
29 Correct 107 ms 104496 KB Output is correct
30 Correct 115 ms 104512 KB Output is correct
31 Correct 112 ms 104680 KB Output is correct
32 Correct 91 ms 104296 KB Output is correct
33 Correct 207 ms 116160 KB Output is correct
34 Correct 289 ms 124736 KB Output is correct
35 Correct 280 ms 125360 KB Output is correct
36 Correct 283 ms 124660 KB Output is correct
37 Correct 450 ms 124780 KB Output is correct
38 Correct 272 ms 124732 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 104424 KB Output is correct
2 Correct 102 ms 104456 KB Output is correct
3 Correct 88 ms 104328 KB Output is correct
4 Correct 523 ms 113684 KB Output is correct
5 Correct 1456 ms 124668 KB Output is correct
6 Correct 1006 ms 107768 KB Output is correct
7 Correct 1611 ms 124712 KB Output is correct
8 Correct 902 ms 111384 KB Output is correct
9 Correct 1439 ms 124728 KB Output is correct
10 Correct 1456 ms 125484 KB Output is correct
11 Correct 1793 ms 124908 KB Output is correct
12 Correct 1639 ms 125348 KB Output is correct
13 Correct 1417 ms 124828 KB Output is correct
14 Correct 1685 ms 124848 KB Output is correct
15 Correct 1093 ms 124724 KB Output is correct
16 Correct 1240 ms 124736 KB Output is correct
17 Correct 87 ms 104384 KB Output is correct
18 Correct 85 ms 104372 KB Output is correct
19 Correct 88 ms 104404 KB Output is correct
20 Correct 90 ms 104344 KB Output is correct
21 Correct 93 ms 104432 KB Output is correct
22 Correct 96 ms 104412 KB Output is correct
23 Correct 92 ms 104436 KB Output is correct
24 Correct 92 ms 104384 KB Output is correct
25 Correct 90 ms 104396 KB Output is correct
26 Correct 90 ms 104500 KB Output is correct
27 Correct 124 ms 104608 KB Output is correct
28 Correct 119 ms 104512 KB Output is correct
29 Correct 107 ms 104496 KB Output is correct
30 Correct 115 ms 104512 KB Output is correct
31 Correct 112 ms 104680 KB Output is correct
32 Correct 91 ms 104296 KB Output is correct
33 Correct 207 ms 116160 KB Output is correct
34 Correct 289 ms 124736 KB Output is correct
35 Correct 280 ms 125360 KB Output is correct
36 Correct 283 ms 124660 KB Output is correct
37 Correct 450 ms 124780 KB Output is correct
38 Correct 272 ms 124732 KB Output is correct
39 Correct 87 ms 104344 KB Output is correct
40 Correct 93 ms 104408 KB Output is correct
41 Correct 89 ms 104412 KB Output is correct
42 Correct 510 ms 113648 KB Output is correct
43 Correct 1582 ms 124772 KB Output is correct
44 Correct 994 ms 107740 KB Output is correct
45 Correct 1470 ms 124736 KB Output is correct
46 Correct 955 ms 111392 KB Output is correct
47 Correct 1500 ms 124680 KB Output is correct
48 Correct 1432 ms 125508 KB Output is correct
49 Correct 1679 ms 124916 KB Output is correct
50 Correct 1591 ms 125456 KB Output is correct
51 Correct 1526 ms 124668 KB Output is correct
52 Correct 1889 ms 124776 KB Output is correct
53 Correct 1370 ms 124736 KB Output is correct
54 Correct 1363 ms 124720 KB Output is correct
55 Correct 91 ms 104512 KB Output is correct
56 Correct 383 ms 124652 KB Output is correct
57 Correct 2164 ms 124728 KB Output is correct
58 Correct 818 ms 107964 KB Output is correct
59 Correct 1992 ms 124736 KB Output is correct
60 Correct 832 ms 111548 KB Output is correct
61 Correct 1769 ms 124728 KB Output is correct
62 Correct 3111 ms 125484 KB Output is correct
63 Correct 3296 ms 124996 KB Output is correct
64 Correct 2705 ms 125068 KB Output is correct
65 Correct 1727 ms 124664 KB Output is correct
66 Correct 3008 ms 124684 KB Output is correct
67 Correct 2050 ms 124736 KB Output is correct
68 Correct 1356 ms 124720 KB Output is correct
69 Correct 86 ms 104360 KB Output is correct
70 Correct 89 ms 104424 KB Output is correct
71 Correct 102 ms 104356 KB Output is correct
72 Correct 108 ms 104432 KB Output is correct
73 Correct 90 ms 104352 KB Output is correct
74 Correct 89 ms 104432 KB Output is correct
75 Correct 91 ms 104408 KB Output is correct
76 Correct 85 ms 104384 KB Output is correct
77 Correct 88 ms 104296 KB Output is correct
78 Correct 88 ms 104344 KB Output is correct
79 Correct 107 ms 104436 KB Output is correct
80 Correct 87 ms 104552 KB Output is correct
81 Correct 86 ms 104304 KB Output is correct
82 Correct 90 ms 104380 KB Output is correct
83 Correct 89 ms 104384 KB Output is correct
84 Correct 85 ms 104368 KB Output is correct
85 Correct 93 ms 104440 KB Output is correct
86 Correct 117 ms 104600 KB Output is correct
87 Correct 119 ms 104608 KB Output is correct
88 Correct 139 ms 104512 KB Output is correct
89 Correct 122 ms 104672 KB Output is correct
90 Correct 113 ms 104608 KB Output is correct
91 Correct 91 ms 104404 KB Output is correct
92 Correct 89 ms 104484 KB Output is correct
93 Correct 117 ms 104824 KB Output is correct
94 Correct 109 ms 104640 KB Output is correct
95 Correct 117 ms 104676 KB Output is correct
96 Correct 99 ms 104612 KB Output is correct
97 Correct 123 ms 104652 KB Output is correct
98 Correct 107 ms 104568 KB Output is correct
99 Correct 316 ms 124656 KB Output is correct
100 Correct 298 ms 124676 KB Output is correct
101 Correct 307 ms 125304 KB Output is correct
102 Correct 288 ms 124656 KB Output is correct
103 Correct 446 ms 124848 KB Output is correct
104 Correct 283 ms 124720 KB Output is correct
105 Correct 91 ms 104368 KB Output is correct
106 Correct 209 ms 116060 KB Output is correct
107 Correct 301 ms 124660 KB Output is correct
108 Correct 311 ms 125456 KB Output is correct
109 Correct 285 ms 124732 KB Output is correct
110 Correct 436 ms 124716 KB Output is correct
111 Correct 287 ms 124744 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 104388 KB Output is correct
2 Correct 86 ms 104412 KB Output is correct
3 Correct 577 ms 121328 KB Output is correct
4 Correct 2910 ms 125504 KB Output is correct
5 Correct 2205 ms 114976 KB Output is correct
6 Correct 2778 ms 125528 KB Output is correct
7 Correct 2526 ms 118848 KB Output is correct
8 Correct 3534 ms 125548 KB Output is correct
9 Correct 96 ms 104372 KB Output is correct
10 Correct 105 ms 104348 KB Output is correct
11 Correct 109 ms 104280 KB Output is correct
12 Correct 112 ms 104412 KB Output is correct
13 Correct 97 ms 104356 KB Output is correct
14 Correct 92 ms 104360 KB Output is correct
15 Correct 105 ms 104432 KB Output is correct
16 Correct 108 ms 104376 KB Output is correct
17 Correct 95 ms 104384 KB Output is correct
18 Incorrect 97 ms 104420 KB Output isn't correct
19 Halted 0 ms 0 KB -