oj.uz

Submission #983667

# Submission time Handle Problem Language Result Execution time Memory
983667 2024-05-15T22:14:37 Z shjeong Rainforest Jumps (APIO21_jumps) C++17
48 / 100
 1272 ms 227828 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<pair<ll,ll>> tree;
    segtree(): tree(808080){}
    void init(ll node, ll s, ll e, vector<ll> &v){
        if(s==e)tree[node] = {v[s],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]);
        }
    }
    pair<ll,ll> query(ll node, ll s, ll e, ll l, ll r){
        if(l>r)return {-1,-1};
        if(e<l or r<s)return {0,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));
    }
    pair<ll,ll> Q(ll l, ll r){ return query(1,1,n,l,r); }
} seg;
vector<ll> v, Rv;
ll L[202020][22];
ll R[202020][22];
ll M[202020][22];
ll RL[202020][22];
ll RR[202020][22];
ll RM[202020][22];
void init(int N, std::vector<int> H) {
    n=N;
    v.push_back(0); Rv=v;
    for(int i = 1 ; i <= n ; i++)v.push_back(H[i-1]), Rv.push_back(H[n-i]);
    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 i = 1 ; i <= n ; i++){
        RL[i][0] = (L[n-i+1][0]==0?n-L[n-i+1][0]+1:0);
        RR[i][0] = (R[n-i+1][0]==0?n-R[n-i+1][0]+1:0);
        RM[i][0] = (M[n-i+1][0]==0?n-M[n-i+1][0]+1: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];
            RL[i][j] = RL[RL[i][j-1]][j-1];
            RR[i][j] = RR[RR[i][j-1]][j-1];
            RM[i][j] = RM[RM[i][j-1]][j-1];
        }
    }
}
ll AB, BC, CD;
ll c;
ll solve_terminal(ll A, ll B, ll C){
    ll D=C;
    ll AB = seg.Q(A,B).first, BC = seg.Q(B+1,C-1).first, CD = seg.Q(C,D).first;
    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;
}
ll solve_terminal_reverse(ll A, ll B, ll C){
    ll D=C;
    ll AB = seg.Q(A,B).first, BC = seg.Q(B+1,C-1).first, CD = seg.Q(C,D).first;
    ll ret = 0;
    ll cur = B;
    for(int i = 20 ; i >= 0 ; i--){
        if(RL[cur][i]<=0)continue;
        if(RL[cur][i]>=A and Rv[RL[cur][i]] < CD)cur = RL[cur][i];
    }
    for(int i = 20 ; i >= 0 ; i--){
        if(RM[cur][i]<=0)continue;
        if(Rv[RM[cur][i]]<CD and RM[cur][i]<C)cur = RM[cur][i], ret += (1<<i);
    }
    for(int i = 20 ; i >= 0 ; i--){
        if(RR[cur][i]<=0)continue;
        if(RR[cur][i]<C)cur = RR[cur][i], ret += (1<<i);
    }
    ret++; cur = RR[cur][0];
    if(cur<C or cur>D)ret = 1e9;
    return ret;
}
int minimum_jumps(int A, int B, int C, int D) {
    A++; B++; C++; D++;
    return solve_terminal(A,B,C);
    ll cur = B;
    AB = seg.Q(A,B).first, BC = seg.Q(B+1,C-1).first, CD = seg.Q(C,D).first;
    ll ret = 1e9;
    if(AB>BC){
        ll cur = B;
        for(int i = 20 ; i >= 0 ; i--){
            if(L[cur][i]<=0)continue;
            if(v[L[cur][i]]<BC)cur = L[cur][i];
        }
        if(v[cur]<BC)cur = L[cur][0];
        cur = R[cur][0];
        if(C<=cur and cur<=D)return 1;
    }
    if(BC>0){
        ll pos = seg.Q(B+1,C-1).second;
        ret = min(ret, solve_terminal(A,B,pos)+1);
    }
    if(seg.Q(1,A-1).first > BC){
        ll cur = A-1;
        for(int i = 20 ; i >= 0 ; i--){
            if(L[cur][i]<=0)continue;
            if(v[L[cur][i]]<BC)cur = L[cur][i];
        }
        if(v[cur]<BC)cur = L[cur][0];
        ret = min(ret, solve_terminal_reverse(n-B+1, n-A+1, n-cur+1)+1);
    }
    if(ret==1e9)ret = -1;
    return ret;
}

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 'std::pair<long long int, long long int> segtree::query(ll, ll, ll, ll, ll)':
jumps.cpp:35:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |         ll mid = s+e>>1;
      |                  ~^~
jumps.cpp: In function 'll solve_terminal(ll, ll, ll)':
jumps.cpp:91:8: warning: unused variable 'AB' [-Wunused-variable]
   91 |     ll AB = seg.Q(A,B).first, BC = seg.Q(B+1,C-1).first, CD = seg.Q(C,D).first;
      |        ^~
jumps.cpp: In function 'll solve_terminal_reverse(ll, ll, ll)':
jumps.cpp:113:8: warning: unused variable 'AB' [-Wunused-variable]
  113 |     ll AB = seg.Q(A,B).first, BC = seg.Q(B+1,C-1).first, CD = seg.Q(C,D).first;
      |        ^~
jumps.cpp:113:31: warning: unused variable 'BC' [-Wunused-variable]
  113 |     ll AB = seg.Q(A,B).first, BC = seg.Q(B+1,C-1).first, CD = seg.Q(C,D).first;
      |                               ^~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:135:8: warning: unused variable 'cur' [-Wunused-variable]
  135 |     ll cur = B;
      |        ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21080 KB Output is correct
3 Correct 254 ms 193004 KB Output is correct
4 Correct 1038 ms 227736 KB Output is correct
5 Correct 833 ms 134368 KB Output is correct
6 Correct 1078 ms 227712 KB Output is correct
7 Correct 782 ms 172208 KB Output is correct
8 Correct 1045 ms 227720 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 23128 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21076 KB Output is correct
2 Correct 4 ms 21120 KB Output is correct
3 Correct 4 ms 21080 KB Output is correct
4 Correct 237 ms 124356 KB Output is correct
5 Correct 866 ms 226400 KB Output is correct
6 Correct 520 ms 61388 KB Output is correct
7 Correct 882 ms 226400 KB Output is correct
8 Correct 498 ms 99004 KB Output is correct
9 Correct 865 ms 226552 KB Output is correct
10 Correct 1043 ms 227788 KB Output is correct
11 Correct 986 ms 227468 KB Output is correct
12 Correct 1022 ms 227472 KB Output is correct
13 Correct 834 ms 226224 KB Output is correct
14 Correct 995 ms 227496 KB Output is correct
15 Correct 897 ms 227484 KB Output is correct
16 Correct 881 ms 227468 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 21080 KB Output is correct
19 Correct 5 ms 23128 KB Output is correct
20 Correct 5 ms 23384 KB Output is correct
21 Correct 5 ms 23384 KB Output is correct
22 Correct 5 ms 23384 KB Output is correct
23 Correct 5 ms 23384 KB Output is correct
24 Correct 5 ms 23384 KB Output is correct
25 Correct 4 ms 23384 KB Output is correct
26 Correct 4 ms 23384 KB Output is correct
27 Correct 14 ms 27704 KB Output is correct
28 Correct 19 ms 27704 KB Output is correct
29 Correct 17 ms 27712 KB Output is correct
30 Correct 14 ms 27736 KB Output is correct
31 Correct 14 ms 27692 KB Output is correct
32 Correct 5 ms 21080 KB Output is correct
33 Correct 112 ms 149328 KB Output is correct
34 Correct 195 ms 226396 KB Output is correct
35 Correct 203 ms 227584 KB Output is correct
36 Correct 205 ms 226188 KB Output is correct
37 Correct 254 ms 226956 KB Output is correct
38 Correct 228 ms 227488 KB Output is correct

Subtask #6
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21076 KB Output is correct
2 Correct 4 ms 21120 KB Output is correct
3 Correct 4 ms 21080 KB Output is correct
4 Correct 237 ms 124356 KB Output is correct
5 Correct 866 ms 226400 KB Output is correct
6 Correct 520 ms 61388 KB Output is correct
7 Correct 882 ms 226400 KB Output is correct
8 Correct 498 ms 99004 KB Output is correct
9 Correct 865 ms 226552 KB Output is correct
10 Correct 1043 ms 227788 KB Output is correct
11 Correct 986 ms 227468 KB Output is correct
12 Correct 1022 ms 227472 KB Output is correct
13 Correct 834 ms 226224 KB Output is correct
14 Correct 995 ms 227496 KB Output is correct
15 Correct 897 ms 227484 KB Output is correct
16 Correct 881 ms 227468 KB Output is correct
17 Correct 4 ms 23128 KB Output is correct
18 Correct 4 ms 21080 KB Output is correct
19 Correct 5 ms 23128 KB Output is correct
20 Correct 5 ms 23384 KB Output is correct
21 Correct 5 ms 23384 KB Output is correct
22 Correct 5 ms 23384 KB Output is correct
23 Correct 5 ms 23384 KB Output is correct
24 Correct 5 ms 23384 KB Output is correct
25 Correct 4 ms 23384 KB Output is correct
26 Correct 4 ms 23384 KB Output is correct
27 Correct 14 ms 27704 KB Output is correct
28 Correct 19 ms 27704 KB Output is correct
29 Correct 17 ms 27712 KB Output is correct
30 Correct 14 ms 27736 KB Output is correct
31 Correct 14 ms 27692 KB Output is correct
32 Correct 5 ms 21080 KB Output is correct
33 Correct 112 ms 149328 KB Output is correct
34 Correct 195 ms 226396 KB Output is correct
35 Correct 203 ms 227584 KB Output is correct
36 Correct 205 ms 226188 KB Output is correct
37 Correct 254 ms 226956 KB Output is correct
38 Correct 228 ms 227488 KB Output is correct
39 Correct 4 ms 21080 KB Output is correct
40 Correct 4 ms 21080 KB Output is correct
41 Correct 4 ms 21080 KB Output is correct
42 Correct 214 ms 124356 KB Output is correct
43 Correct 869 ms 226404 KB Output is correct
44 Correct 464 ms 61388 KB Output is correct
45 Correct 840 ms 226200 KB Output is correct
46 Correct 465 ms 98980 KB Output is correct
47 Correct 890 ms 226188 KB Output is correct
48 Correct 1038 ms 227828 KB Output is correct
49 Correct 1014 ms 227484 KB Output is correct
50 Correct 961 ms 227496 KB Output is correct
51 Correct 832 ms 226400 KB Output is correct
52 Correct 1008 ms 227212 KB Output is correct
53 Correct 846 ms 227492 KB Output is correct
54 Correct 813 ms 227468 KB Output is correct
55 Correct 4 ms 21080 KB Output is correct
56 Correct 251 ms 226004 KB Output is correct
57 Correct 901 ms 226176 KB Output is correct
58 Correct 370 ms 61504 KB Output is correct
59 Correct 863 ms 226224 KB Output is correct
60 Correct 357 ms 99268 KB Output is correct
61 Correct 835 ms 226528 KB Output is correct
62 Correct 1026 ms 227824 KB Output is correct
63 Correct 965 ms 227316 KB Output is correct
64 Correct 982 ms 227136 KB Output is correct
65 Correct 967 ms 226192 KB Output is correct
66 Correct 1272 ms 227012 KB Output is correct
67 Correct 1033 ms 227732 KB Output is correct
68 Correct 1084 ms 227484 KB Output is correct
69 Correct 3 ms 21080 KB Output is correct
70 Correct 4 ms 23128 KB Output is correct
71 Correct 6 ms 23384 KB Output is correct
72 Correct 6 ms 23384 KB Output is correct
73 Correct 6 ms 23600 KB Output is correct
74 Correct 5 ms 23384 KB Output is correct
75 Correct 5 ms 23384 KB Output is correct
76 Correct 4 ms 23128 KB Output is correct
77 Correct 4 ms 21080 KB Output is correct
78 Correct 4 ms 23128 KB Output is correct
79 Correct 5 ms 23384 KB Output is correct
80 Correct 6 ms 23384 KB Output is correct
81 Correct 6 ms 23384 KB Output is correct
82 Correct 5 ms 23384 KB Output is correct
83 Correct 5 ms 23384 KB Output is correct
84 Correct 5 ms 23384 KB Output is correct
85 Correct 8 ms 13296 KB Output is correct
86 Correct 16 ms 15448 KB Output is correct
87 Correct 22 ms 15444 KB Output is correct
88 Correct 16 ms 15448 KB Output is correct
89 Correct 16 ms 15260 KB Output is correct
90 Correct 19 ms 15268 KB Output is correct
91 Correct 3 ms 13144 KB Output is correct
92 Correct 5 ms 13912 KB Output is correct
93 Correct 19 ms 15448 KB Output is correct
94 Correct 18 ms 15540 KB Output is correct
95 Correct 20 ms 15284 KB Output is correct
96 Correct 22 ms 15272 KB Output is correct
97 Correct 19 ms 15280 KB Output is correct
98 Correct 4 ms 21080 KB Output is correct
99 Correct 217 ms 226192 KB Output is correct
100 Correct 228 ms 226396 KB Output is correct
101 Correct 244 ms 227452 KB Output is correct
102 Correct 211 ms 226400 KB Output is correct
103 Correct 245 ms 227212 KB Output is correct
104 Correct 216 ms 227488 KB Output is correct
105 Correct 4 ms 21080 KB Output is correct
106 Correct 106 ms 149564 KB Output is correct
107 Correct 204 ms 226408 KB Output is correct
108 Correct 203 ms 227588 KB Output is correct
109 Correct 193 ms 226204 KB Output is correct
110 Correct 215 ms 226784 KB Output is correct
111 Correct 199 ms 227468 KB Output is correct

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 21080 KB Output is correct
2 Correct 3 ms 21080 KB Output is correct
3 Correct 254 ms 193004 KB Output is correct
4 Correct 1038 ms 227736 KB Output is correct
5 Correct 833 ms 134368 KB Output is correct
6 Correct 1078 ms 227712 KB Output is correct
7 Correct 782 ms 172208 KB Output is correct
8 Correct 1045 ms 227720 KB Output is correct
9 Incorrect 3 ms 23128 KB Output isn't correct
10 Halted 0 ms 0 KB -