Submission #887781

#	Time	Username	Problem	Language	Result	Execution time	Memory
887781		Alish	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	940 ms	61248 KiB

jumps

#include<bits/stdc++.h>

//#include "jumps.h"


using namespace std;

typedef long long int	ll;
typedef pair<int, int>	pii;
typedef pair<ll, ll>	pll;


#define F		        first
#define S		        second
#define pb		        push_back
#define endl            '\n'
#define Mp		        make_pair
#define all(x)          x.begin(), x.end()
#define debug(x)        cerr << #x << " = " << x << endl;
#define fast_io         ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io         freopen("connect.in" , "r" , stdin) ; freopen("connect.out" , "w" , stdout);
//#define int             ll

ll mod = 1e9+7 ;

const int N = 2e5+23, LOG=23;

int n, h[N];
int seg[4*N];
int L[N][LOG], R[N][LOG], M[N][LOG];

void build(int l=0, int r=n, int ind=0){
    if(r-l==1){
        seg[ind]=h[l];
        return;
    }
    int mid=(r+l)>>1;
    build(l, mid, 2*ind+1); build(mid, r, 2*ind+2);
    seg[ind]=max(seg[2*ind+1], seg[2*ind+2]);
}

int get(int lx, int rx, int l=0, int r=n, int ind=0){
    if(rx<=lx) return 0;
    if(lx>=r || rx<=l) return 0;
    if(lx<=l && rx>=r)return seg[ind];
    int mid=(r+l)>>1;
    return max(get(lx, rx, l, mid, 2*ind+1), get(lx, rx, mid, r, 2*ind+2));
}

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

    build();
    for (int i=0; i<n; i++) for (int j=0; j<LOG; j++)L[i][j]=R[i][j]=M[i][j]=-1;
    vector<int> st;
    for (int i=0; i<n; i++){
        while(!st.empty() && h[st.back()]<h[i]) st.pop_back();
        if(!st.empty()) L[i][0]=st.back();
        st.pb(i);
    }
    st.clear();

    for (int i=n-1; i>=0; i--){
        while(!st.empty() && h[st.back()]<h[i]) st.pop_back();
        if(!st.empty()) R[i][0]=st.back();
        st.pb(i);
    }

    for (int i=0; i<n; i++){
        if(L[i][0]==-1) M[i][0]=R[i][0];
        else if(R[i][0]==-1) M[i][0]=L[i][0];
        else if(h[L[i][0]]>h[R[i][0]]) M[i][0]=L[i][0];
        else M[i][0]=R[i][0];
    }


    for (int j=1; j<LOG; j++) for (int i=0; i<n; i++){
        if(L[i][j-1]!=-1)L[i][j]=L[L[i][j-1]][j-1];
        if(R[i][j-1]!=-1)R[i][j]=R[R[i][j-1]][j-1];
        if(M[i][j-1]!=-1)M[i][j]=M[M[i][j-1]][j-1];
    }
}

int minimum_jumps(int A, int B, int C, int D) {
    int ans=0;
    int r1=get(B+1, C), r2=get(C, D+1);
    if(r1>r2) return -1;
    if(h[B]>r2) return -1;
    int v=B;
    for (int i=LOG-1; i>=0; i--){
        if(L[v][i]!=-1 && h[L[v][i]]<r2 && L[v][i]>=A) v=L[v][i];
    }
    if(h[v]>r1) return 1;

    for (int i=LOG-1; i>=0; i--){
        if(M[v][i]!=-1 && h[M[v][i]]<=r1){
            ans+=(1<<i);
            v=M[v][i];
        }
    }

    if(R[v][0] && h[R[v][0]]>r1) return ans+1;
    if(M[v][0]!=-1 && h[M[v][0]]<r2) return ans+2;

    for (int i=LOG-1; i>=0; i--){
        if(R[v][i]!=-1 && R[v][i]<C){
            v=R[v][i];
            ans+=(1<<i);
        }
    }
    return ans+1;
}

/*
int main()
{

    int n; cin>>n;
    vector<int> vec;
    for (int i=0; i<n; i++){
        int c; cin>>c;
        vec.pb(c);
    }
    init(n, vec);
    int q; cin>>q;
    while(q--){
        int a, b, c, d; cin>>a>>b>>c>>d;
        cout<<minimum_jumps(a, b, c, d)<<endl;
    }
}


*/

• Subtask 1: 4 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 12 / 12
• Subtask 5: 23 / 23
• Subtask 6: 21 / 21
• Subtask 7: 19 / 19