oj.uz

Submission #982923

# Submission time Handle Problem Language Result Execution time Memory
982923 2024-05-15T04:12:59 Z shjeong Rainforest Jumps (APIO21_jumps) C++17
48 / 100
 1022 ms 115600 KB 
#include "jumps.h"
#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <list>
using namespace std;
typedef long long ll;
ll n;
struct segtree{
    vector<ll> tree;
    segtree(): tree(808080){}
    void init(ll node, ll s, ll e, vector<ll> &v){
        if(s==e)tree[node] = v[s];
        else{
            ll mid = s+e>>1;
            init(node<<1,s,mid,v); init(node<<1|1,mid+1,e,v);
            tree[node] = max(tree[node<<1],tree[node<<1|1]);
        }
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if(l>r)return -1;
        if(e<l or r<s)return 0;
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1;
        return max(query(node<<1,s,mid,l,r), query(node<<1|1,mid+1,e,l,r));
    }
    ll Q(ll l, ll r){ return query(1,1,n,l,r); }
} seg;
vector<ll> v;
ll L[202020][22];
ll R[202020][22];
ll M[202020][22];
void init(int N, std::vector<int> H) {
    n=N;
    v.push_back(0);
    for(int i = 1 ; i <= n ; i++)v.push_back(H[i-1]);
    seg.init(1,1,n,v);
    stack<ll> st;
    for(int i = 1 ; i <= n ; i++){
        while(st.size() and v[st.top()] < v[i]){
            R[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }
    while(st.size())st.pop();
    for(int i = n ; i >= 1 ; i--){
        while(st.size() and v[st.top()] < v[i]){
            L[st.top()][0] = i;
            st.pop();
        }
        st.push(i);
    }
    for(int i = 1 ; i <= n ; i++){
        M[i][0] = (v[L[i][0]] > v[R[i][0]] ? L[i][0] : R[i][0]);
    }
    for(int j = 1 ; j <= 20 ; j++){
        for(int i = 1 ; i <= n ; i++){
            L[i][j] = L[L[i][j-1]][j-1];
            R[i][j] = R[R[i][j-1]][j-1];
            M[i][j] = M[M[i][j-1]][j-1];
        }
    }
}
ll AB, BC, CD;
ll c;
int minimum_jumps(int A, int B, int C, int D) {
    A++; B++; C++; D++;
    AB = seg.Q(A,B), BC = seg.Q(B+1,C-1), CD = seg.Q(C,D);
    if(BC>CD)return -1;
    ll ret = 0;
    ll cur = B;
    for(int i = 20 ; i >= 0 ; i--){
        if(L[cur][i]<=0)continue;
        if(L[cur][i]>=A and v[L[cur][i]] < CD)cur = L[cur][i];
    }
    for(int i = 20 ; i >= 0 ; i--){
        if(M[cur][i]<=0)continue;
        if(v[M[cur][i]]<CD and R[cur][i]>0 and R[cur][i]<C)cur = M[cur][i], ret += (1<<i);
    }
    for(int i = 20 ; i >= 0 ; i--){
        if(R[cur][i]<=0)continue;
        if(R[cur][i]<C)cur = R[cur][i], ret += (1<<i);
    }
    ret++; cur = R[cur][0];
    if(cur<C or cur>D)ret = -1;
    return ret;
}
/*
10 100
8 7 2 1 3 4 5 6 9 10
3 3 9 9
 ans : 4
 */

Compilation message

jumps.cpp: In member function 'void segtree::init(ll, ll, ll, std::vector<long long int>&)':
jumps.cpp:26:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |             ll mid = s+e>>1;
      |                      ~^~
jumps.cpp: In member function 'll segtree::query(ll, ll, ll, ll, ll)':
jumps.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         ll mid = s+e>>1;
      |                  ~^~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 209 ms 97448 KB Output is correct
4 Correct 1022 ms 115572 KB Output is correct
5 Correct 821 ms 65656 KB Output is correct
6 Correct 1006 ms 115568 KB Output is correct
7 Correct 772 ms 84984 KB Output is correct
8 Correct 970 ms 115568 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 3 ms 11092 KB Output is correct
6 Correct 3 ms 10840 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 3 ms 10840 KB Output is correct
10 Incorrect 3 ms 10840 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 3 ms 11092 KB Output is correct
6 Correct 3 ms 10840 KB Output is correct
7 Correct 3 ms 10840 KB Output is correct
8 Correct 3 ms 10840 KB Output is correct
9 Correct 3 ms 10840 KB Output is correct
10 Incorrect 3 ms 10840 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10840 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 2 ms 8792 KB Output is correct
5 Correct 102 ms 99652 KB Output is correct
6 Correct 125 ms 114220 KB Output is correct
7 Correct 58 ms 67964 KB Output is correct
8 Correct 116 ms 113888 KB Output is correct
9 Correct 13 ms 30060 KB Output is correct
10 Correct 120 ms 114044 KB Output is correct
11 Correct 131 ms 115436 KB Output is correct
12 Correct 127 ms 114936 KB Output is correct
13 Incorrect 133 ms 114940 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 208 ms 61780 KB Output is correct
5 Correct 780 ms 114044 KB Output is correct
6 Correct 417 ms 30160 KB Output is correct
7 Correct 798 ms 114044 KB Output is correct
8 Correct 433 ms 49144 KB Output is correct
9 Correct 724 ms 113892 KB Output is correct
10 Correct 967 ms 115412 KB Output is correct
11 Correct 909 ms 115600 KB Output is correct
12 Correct 871 ms 115340 KB Output is correct
13 Correct 746 ms 114052 KB Output is correct
14 Correct 862 ms 114744 KB Output is correct
15 Correct 782 ms 115236 KB Output is correct
16 Correct 731 ms 115012 KB Output is correct
17 Correct 2 ms 10840 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 3 ms 10840 KB Output is correct
20 Correct 4 ms 10840 KB Output is correct
21 Correct 3 ms 10840 KB Output is correct
22 Correct 3 ms 10840 KB Output is correct
23 Correct 4 ms 10840 KB Output is correct
24 Correct 2 ms 10840 KB Output is correct
25 Correct 2 ms 10840 KB Output is correct
26 Correct 2 ms 10932 KB Output is correct
27 Correct 15 ms 15192 KB Output is correct
28 Correct 13 ms 15192 KB Output is correct
29 Correct 13 ms 15192 KB Output is correct
30 Correct 15 ms 15192 KB Output is correct
31 Correct 14 ms 15192 KB Output is correct
32 Correct 2 ms 8792 KB Output is correct
33 Correct 72 ms 74540 KB Output is correct
34 Correct 125 ms 114044 KB Output is correct
35 Correct 134 ms 115316 KB Output is correct
36 Correct 123 ms 114040 KB Output is correct
37 Correct 137 ms 114728 KB Output is correct
38 Correct 127 ms 115228 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 2 ms 8792 KB Output is correct
4 Correct 208 ms 61780 KB Output is correct
5 Correct 780 ms 114044 KB Output is correct
6 Correct 417 ms 30160 KB Output is correct
7 Correct 798 ms 114044 KB Output is correct
8 Correct 433 ms 49144 KB Output is correct
9 Correct 724 ms 113892 KB Output is correct
10 Correct 967 ms 115412 KB Output is correct
11 Correct 909 ms 115600 KB Output is correct
12 Correct 871 ms 115340 KB Output is correct
13 Correct 746 ms 114052 KB Output is correct
14 Correct 862 ms 114744 KB Output is correct
15 Correct 782 ms 115236 KB Output is correct
16 Correct 731 ms 115012 KB Output is correct
17 Correct 2 ms 10840 KB Output is correct
18 Correct 2 ms 8792 KB Output is correct
19 Correct 3 ms 10840 KB Output is correct
20 Correct 4 ms 10840 KB Output is correct
21 Correct 3 ms 10840 KB Output is correct
22 Correct 3 ms 10840 KB Output is correct
23 Correct 4 ms 10840 KB Output is correct
24 Correct 2 ms 10840 KB Output is correct
25 Correct 2 ms 10840 KB Output is correct
26 Correct 2 ms 10932 KB Output is correct
27 Correct 15 ms 15192 KB Output is correct
28 Correct 13 ms 15192 KB Output is correct
29 Correct 13 ms 15192 KB Output is correct
30 Correct 15 ms 15192 KB Output is correct
31 Correct 14 ms 15192 KB Output is correct
32 Correct 2 ms 8792 KB Output is correct
33 Correct 72 ms 74540 KB Output is correct
34 Correct 125 ms 114044 KB Output is correct
35 Correct 134 ms 115316 KB Output is correct
36 Correct 123 ms 114040 KB Output is correct
37 Correct 137 ms 114728 KB Output is correct
38 Correct 127 ms 115228 KB Output is correct
39 Correct 2 ms 8792 KB Output is correct
40 Correct 2 ms 8824 KB Output is correct
41 Correct 2 ms 8792 KB Output is correct
42 Correct 202 ms 61844 KB Output is correct
43 Correct 746 ms 114044 KB Output is correct
44 Correct 411 ms 30168 KB Output is correct
45 Correct 777 ms 113904 KB Output is correct
46 Correct 426 ms 49100 KB Output is correct
47 Correct 744 ms 114000 KB Output is correct
48 Correct 1002 ms 115420 KB Output is correct
49 Correct 869 ms 115448 KB Output is correct
50 Correct 970 ms 115348 KB Output is correct
51 Correct 733 ms 113884 KB Output is correct
52 Correct 914 ms 114748 KB Output is correct
53 Correct 750 ms 115004 KB Output is correct
54 Correct 761 ms 115228 KB Output is correct
55 Correct 2 ms 8792 KB Output is correct
56 Correct 155 ms 113720 KB Output is correct
57 Correct 769 ms 114044 KB Output is correct
58 Correct 406 ms 30080 KB Output is correct
59 Correct 772 ms 114028 KB Output is correct
60 Correct 308 ms 49100 KB Output is correct
61 Correct 769 ms 113888 KB Output is correct
62 Correct 953 ms 115544 KB Output is correct
63 Correct 949 ms 115188 KB Output is correct
64 Correct 869 ms 114960 KB Output is correct
65 Correct 780 ms 114044 KB Output is correct
66 Correct 957 ms 114732 KB Output is correct
67 Correct 860 ms 115180 KB Output is correct
68 Correct 796 ms 115036 KB Output is correct
69 Correct 2 ms 8792 KB Output is correct
70 Correct 2 ms 10840 KB Output is correct
71 Correct 3 ms 10840 KB Output is correct
72 Correct 3 ms 10840 KB Output is correct
73 Correct 4 ms 10836 KB Output is correct
74 Correct 3 ms 10840 KB Output is correct
75 Correct 3 ms 10840 KB Output is correct
76 Correct 2 ms 10840 KB Output is correct
77 Correct 2 ms 8832 KB Output is correct
78 Correct 3 ms 10840 KB Output is correct
79 Correct 3 ms 10840 KB Output is correct
80 Correct 3 ms 10840 KB Output is correct
81 Correct 4 ms 10840 KB Output is correct
82 Correct 3 ms 10840 KB Output is correct
83 Correct 3 ms 10840 KB Output is correct
84 Correct 2 ms 10840 KB Output is correct
85 Correct 4 ms 10840 KB Output is correct
86 Correct 11 ms 15192 KB Output is correct
87 Correct 11 ms 15192 KB Output is correct
88 Correct 13 ms 15192 KB Output is correct
89 Correct 13 ms 15192 KB Output is correct
90 Correct 13 ms 13400 KB Output is correct
91 Correct 3 ms 10840 KB Output is correct
92 Correct 2 ms 10840 KB Output is correct
93 Correct 13 ms 15196 KB Output is correct
94 Correct 15 ms 15192 KB Output is correct
95 Correct 12 ms 15192 KB Output is correct
96 Correct 13 ms 15192 KB Output is correct
97 Correct 13 ms 15192 KB Output is correct
98 Correct 2 ms 8792 KB Output is correct
99 Correct 112 ms 113996 KB Output is correct
100 Correct 114 ms 114056 KB Output is correct
101 Correct 136 ms 115148 KB Output is correct
102 Correct 113 ms 114048 KB Output is correct
103 Correct 125 ms 114752 KB Output is correct
104 Correct 116 ms 115184 KB Output is correct
105 Correct 2 ms 8792 KB Output is correct
106 Correct 65 ms 74536 KB Output is correct
107 Correct 111 ms 113908 KB Output is correct
108 Correct 151 ms 115164 KB Output is correct
109 Correct 111 ms 113888 KB Output is correct
110 Correct 126 ms 114672 KB Output is correct
111 Correct 123 ms 115136 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8792 KB Output is correct
2 Correct 2 ms 8792 KB Output is correct
3 Correct 209 ms 97448 KB Output is correct
4 Correct 1022 ms 115572 KB Output is correct
5 Correct 821 ms 65656 KB Output is correct
6 Correct 1006 ms 115568 KB Output is correct
7 Correct 772 ms 84984 KB Output is correct
8 Correct 970 ms 115568 KB Output is correct
9 Correct 2 ms 10840 KB Output is correct
10 Correct 2 ms 8792 KB Output is correct
11 Correct 2 ms 8792 KB Output is correct
12 Correct 2 ms 8792 KB Output is correct
13 Correct 3 ms 11092 KB Output is correct
14 Correct 3 ms 10840 KB Output is correct
15 Correct 3 ms 10840 KB Output is correct
16 Correct 3 ms 10840 KB Output is correct
17 Correct 3 ms 10840 KB Output is correct
18 Incorrect 3 ms 10840 KB Output isn't correct
19 Halted 0 ms 0 KB -