oj.uz

Submission #650163

# Submission time Handle Problem Language Result Execution time Memory
650163 2022-10-12T16:18:50 Z PoonYaPat Rainforest Jumps (APIO21_jumps) C++14
48 / 100
 1410 ms 51768 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

int n,h[200001],s[1<<19];
int l[400001][20],r[400001][20],high[400001][20];

void build(int ll, int rr, int idx) {
    if (ll>rr) return;
    if (ll==rr) s[idx]=h[ll];
    else {
        int mid=(ll+rr)/2;
        build(ll,mid,2*idx);
        build(mid+1,rr,2*idx+1);
        s[idx]=max(s[2*idx],s[2*idx+1]);
    }
}

int query(int ll, int rr, int idx, int x, int y) {
    if (ll>y ||rr<x) return 0;
    if (x<=ll && rr<=y) return s[idx];
    int mid=(ll+rr)/2;
    return max(query(ll,mid,2*idx,x,y),query(mid+1,rr,2*idx+1,x,y));
}

void init(int N, vector<int> H) {
    n=N;
    for (int i=0; i<n; ++i) h[i+1]=H[i];
    build(1,n,1);

    for (int i=1; i<=n; ++i) {
        int idx=i-1;
        while (h[idx]<h[i] && idx!=0) idx=l[idx][0];
        l[i][0]=idx;
    }

    for (int i=n; i>=1; --i) {
        int idx=i+1;
        while (h[idx]<h[i] && idx!=n+1) idx=r[idx][0];
        r[i][0]=idx;
    }

    for (int i=1; i<=n; ++i) {
        if (h[r[i][0]]>h[l[i][0]]) high[i][0]=r[i][0];
        else high[i][0]=l[i][0];
    }

    for (int i=1; i<18; ++i) {
        for (int j=1; j<=n; ++j) {
            l[j][i]=l[l[j][i-1]][i-1];
            r[j][i]=r[r[j][i-1]][i-1];
            high[j][i]=high[high[j][i-1]][i-1];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    int a=++A, b=++B, c=++C, d=++D;
    int mmax=query(1,n,1,c,d),now=b;

    if (query(1,n,1,b,c-1)>mmax) return -1;

    //free range, start with considering b
    for (int i=18; i>=0; --i) {
        if (l[now][i]>=a && h[l[now][i]]<mmax) now=l[now][i]; //go to left[now][i] (in free range)
    }
    if (r[now][0]>=c) return 1;

    int ans=0;
    for (int i=18; i>=0; --i) {
        if (h[high[now][i]]<h[c] && high[now][i]!=0 && high[now][i]!=n+1) { //go to the highest point (with cost)
            ans+=(1<<i);
            now=high[now][i];
        }
    }

    for (int i=18; i>=0; --i) { //go from the highest point (lower than h[c]) to c
        if (h[r[now][i]]<h[c] && r[now][i]!=0 && r[now][i]!=n+1) {
            ans+=(1<<i);
            now=r[now][i];
        }
    }
    return ans+1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 196 ms 41492 KB Output is correct
4 Correct 1306 ms 51612 KB Output is correct
5 Correct 1090 ms 26172 KB Output is correct
6 Correct 1309 ms 51688 KB Output is correct
7 Correct 1026 ms 36084 KB Output is correct
8 Correct 1271 ms 51688 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Incorrect 2 ms 336 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 98 ms 42132 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 315 ms 23888 KB Output is correct
5 Correct 891 ms 51628 KB Output is correct
6 Correct 592 ms 8896 KB Output is correct
7 Correct 1050 ms 51576 KB Output is correct
8 Correct 533 ms 18256 KB Output is correct
9 Correct 806 ms 51656 KB Output is correct
10 Correct 1049 ms 51688 KB Output is correct
11 Correct 1167 ms 51620 KB Output is correct
12 Correct 1129 ms 51624 KB Output is correct
13 Correct 1088 ms 51620 KB Output is correct
14 Correct 1048 ms 51604 KB Output is correct
15 Correct 971 ms 51616 KB Output is correct
16 Correct 996 ms 51624 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 2 ms 336 KB Output is correct
20 Correct 3 ms 336 KB Output is correct
21 Correct 3 ms 336 KB Output is correct
22 Correct 3 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 4 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 11 ms 720 KB Output is correct
28 Correct 25 ms 720 KB Output is correct
29 Correct 23 ms 720 KB Output is correct
30 Correct 22 ms 720 KB Output is correct
31 Correct 29 ms 720 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 84 ms 29804 KB Output is correct
34 Correct 109 ms 51620 KB Output is correct
35 Correct 122 ms 51748 KB Output is correct
36 Correct 108 ms 51688 KB Output is correct
37 Correct 116 ms 51616 KB Output is correct
38 Correct 113 ms 51656 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 208 KB Output is correct
4 Correct 315 ms 23888 KB Output is correct
5 Correct 891 ms 51628 KB Output is correct
6 Correct 592 ms 8896 KB Output is correct
7 Correct 1050 ms 51576 KB Output is correct
8 Correct 533 ms 18256 KB Output is correct
9 Correct 806 ms 51656 KB Output is correct
10 Correct 1049 ms 51688 KB Output is correct
11 Correct 1167 ms 51620 KB Output is correct
12 Correct 1129 ms 51624 KB Output is correct
13 Correct 1088 ms 51620 KB Output is correct
14 Correct 1048 ms 51604 KB Output is correct
15 Correct 971 ms 51616 KB Output is correct
16 Correct 996 ms 51624 KB Output is correct
17 Correct 1 ms 336 KB Output is correct
18 Correct 0 ms 336 KB Output is correct
19 Correct 2 ms 336 KB Output is correct
20 Correct 3 ms 336 KB Output is correct
21 Correct 3 ms 336 KB Output is correct
22 Correct 3 ms 336 KB Output is correct
23 Correct 2 ms 336 KB Output is correct
24 Correct 4 ms 336 KB Output is correct
25 Correct 1 ms 336 KB Output is correct
26 Correct 1 ms 464 KB Output is correct
27 Correct 11 ms 720 KB Output is correct
28 Correct 25 ms 720 KB Output is correct
29 Correct 23 ms 720 KB Output is correct
30 Correct 22 ms 720 KB Output is correct
31 Correct 29 ms 720 KB Output is correct
32 Correct 1 ms 208 KB Output is correct
33 Correct 84 ms 29804 KB Output is correct
34 Correct 109 ms 51620 KB Output is correct
35 Correct 122 ms 51748 KB Output is correct
36 Correct 108 ms 51688 KB Output is correct
37 Correct 116 ms 51616 KB Output is correct
38 Correct 113 ms 51656 KB Output is correct
39 Correct 0 ms 208 KB Output is correct
40 Correct 0 ms 336 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 325 ms 23844 KB Output is correct
43 Correct 1410 ms 51684 KB Output is correct
44 Correct 628 ms 8912 KB Output is correct
45 Correct 1012 ms 51640 KB Output is correct
46 Correct 557 ms 18252 KB Output is correct
47 Correct 567 ms 51748 KB Output is correct
48 Correct 1159 ms 51684 KB Output is correct
49 Correct 1180 ms 51608 KB Output is correct
50 Correct 1162 ms 51620 KB Output is correct
51 Correct 873 ms 51768 KB Output is correct
52 Correct 1146 ms 51656 KB Output is correct
53 Correct 876 ms 51636 KB Output is correct
54 Correct 870 ms 51624 KB Output is correct
55 Correct 0 ms 336 KB Output is correct
56 Correct 165 ms 51480 KB Output is correct
57 Correct 818 ms 51616 KB Output is correct
58 Correct 539 ms 9424 KB Output is correct
59 Correct 993 ms 51692 KB Output is correct
60 Correct 452 ms 18868 KB Output is correct
61 Correct 1115 ms 51692 KB Output is correct
62 Correct 1202 ms 51620 KB Output is correct
63 Correct 1123 ms 51676 KB Output is correct
64 Correct 1117 ms 51656 KB Output is correct
65 Correct 959 ms 51688 KB Output is correct
66 Correct 1235 ms 51652 KB Output is correct
67 Correct 1058 ms 51644 KB Output is correct
68 Correct 1037 ms 51656 KB Output is correct
69 Correct 0 ms 208 KB Output is correct
70 Correct 1 ms 336 KB Output is correct
71 Correct 2 ms 336 KB Output is correct
72 Correct 2 ms 336 KB Output is correct
73 Correct 2 ms 336 KB Output is correct
74 Correct 2 ms 336 KB Output is correct
75 Correct 3 ms 336 KB Output is correct
76 Correct 0 ms 208 KB Output is correct
77 Correct 0 ms 336 KB Output is correct
78 Correct 2 ms 336 KB Output is correct
79 Correct 2 ms 336 KB Output is correct
80 Correct 2 ms 336 KB Output is correct
81 Correct 1 ms 336 KB Output is correct
82 Correct 2 ms 336 KB Output is correct
83 Correct 2 ms 336 KB Output is correct
84 Correct 1 ms 336 KB Output is correct
85 Correct 4 ms 336 KB Output is correct
86 Correct 18 ms 840 KB Output is correct
87 Correct 19 ms 720 KB Output is correct
88 Correct 23 ms 720 KB Output is correct
89 Correct 20 ms 720 KB Output is correct
90 Correct 21 ms 720 KB Output is correct
91 Correct 0 ms 336 KB Output is correct
92 Correct 1 ms 464 KB Output is correct
93 Correct 17 ms 720 KB Output is correct
94 Correct 19 ms 720 KB Output is correct
95 Correct 23 ms 720 KB Output is correct
96 Correct 20 ms 720 KB Output is correct
97 Correct 18 ms 720 KB Output is correct
98 Correct 0 ms 208 KB Output is correct
99 Correct 100 ms 51488 KB Output is correct
100 Correct 98 ms 51688 KB Output is correct
101 Correct 101 ms 51604 KB Output is correct
102 Correct 106 ms 51764 KB Output is correct
103 Correct 111 ms 51660 KB Output is correct
104 Correct 95 ms 51656 KB Output is correct
105 Correct 0 ms 336 KB Output is correct
106 Correct 58 ms 29892 KB Output is correct
107 Correct 101 ms 51652 KB Output is correct
108 Correct 97 ms 51656 KB Output is correct
109 Correct 100 ms 51688 KB Output is correct
110 Correct 115 ms 51644 KB Output is correct
111 Correct 96 ms 51644 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 208 KB Output is correct
3 Correct 196 ms 41492 KB Output is correct
4 Correct 1306 ms 51612 KB Output is correct
5 Correct 1090 ms 26172 KB Output is correct
6 Correct 1309 ms 51688 KB Output is correct
7 Correct 1026 ms 36084 KB Output is correct
8 Correct 1271 ms 51688 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 208 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Incorrect 2 ms 336 KB Output isn't correct
14 Halted 0 ms 0 KB -