Submission #1277613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1277613		hainam2k9	Rainforest Jumps (APIO21_jumps)	C++20	100 / 100	423 ms	46436 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define tt cin.tie(0), cout.tie(0), ios_base::sync_with_stdio(0)
#define fo freopen((NAME+".INP").c_str(), "r", stdin), freopen((NAME+".OUT").c_str(), "w", stdout)
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define db long double
#define sz(a) ((int)(a).size())
#define pb emplace_back
#define pf emplace_front
#define pob pop_back
#define pof pop_front
#define lb lower_bound
#define ub upper_bound
#define fi first
#define se second
#define ins emplace
#define mp make_pair
using namespace std;
const int MOD = 1e9+7, MAXN = 2e5+5;
const string NAME = "";
int n,a[MAXN],stmax[20][MAXN];
int L[MAXN],R[MAXN],jump[20][MAXN],jump2[20][MAXN];
void build(){
    for(int i = 1; i<=n; ++i)
        stmax[0][i]=i;
    for(int i = 1; i<=__lg(n); ++i)
        for(int j = 1; j+(1<<i)-1<=n; ++j)
            stmax[i][j]=(a[stmax[i-1][j]]>=a[stmax[i-1][j+(1<<(i-1))]] ? stmax[i-1][j] : stmax[i-1][j+(1<<(i-1))]);
    stack<int> st;
    for(int i = 1; i<=n; ++i){
        while(!st.empty()&&a[i]>=a[st.top()]) st.pop();
        L[i]=(st.empty() ? i : st.top());
        st.ins(i);
    }
    while(!st.empty()) st.pop();
    for(int i = n; i>0; --i){
        while(!st.empty()&&a[i]>=a[st.top()]) st.pop();
        R[i]=(st.empty() ? i : st.top());
        st.ins(i);
    }
    for(int i = 1; i<=n; ++i){
        if(a[L[i]]>a[R[i]]) jump[0][i]=L[i], jump2[0][i]=R[i];
        else jump[0][i]=R[i], jump2[0][i]=L[i];
    }
    for(int i = 1; i<=__lg(n); ++i)
        for(int j = 1; j<=n; ++j)
            jump[i][j]=jump[i-1][jump[i-1][j]], jump2[i][j]=jump2[i-1][jump2[i-1][j]];
}
int getmax(int l, int r){
    int k=__lg(r-l+1);
    return (a[stmax[k][l]]>=a[stmax[k][r-(1<<k)+1]] ? stmax[k][l] : stmax[k][r-(1<<k)+1]);
}
int bs(int l, int r, int x){
    int rs=-1, R=r;
    while(l<=r){
        int mid=(l+r)>>1;
        if(a[getmax(mid,r)]<=x) rs=getmax(mid,R), r=mid-1;
        else l=mid+1;
    }
    return rs;
}
void init(int N, vector<int> v){
    n=N;
    for(int i = 1; i<=n; ++i)
        a[i]=v[i-1];
    build();
}
int minimum_jumps(int l, int r, int u, int v){
    int rs=1e9;
    ++l, ++r, ++u, ++v;
    if(r+1==u){
        if(a[r]<a[getmax(u,v)]) return 1;
        return -1;
    }
    int MAX=getmax(r+1,u-1),x=bs(l,r,a[MAX]),cnt=0;
    if(x!=-1&&a[MAX]<a[getmax(u,v)]){
        for(int i = __lg(n); i>=0; --i)
            if(a[jump[i][x]]<=a[MAX]) x=jump[i][x], cnt+=1<<i;
        for(int i = __lg(n); i>=0; --i)
            if(a[jump2[i][x]]<a[MAX]) x=jump2[i][x], cnt+=1<<i;
        if(a[x]>=a[MAX]) rs=min(rs,cnt+1);
        else if(a[jump2[0][x]]>=a[MAX]) ++cnt, rs=min(rs,cnt+1);
    }
    if(L[MAX]!=MAX&&a[L[MAX]]<a[getmax(u,v)]){
        MAX=L[MAX], x=getmax(l,r), cnt=0;
        if(l<=MAX&&MAX<=r) rs=1;
        else{
            for(int i = __lg(n); i>=0; --i)
                if(a[jump[i][x]]<=a[MAX]) x=jump[i][x], cnt+=1<<i;
            for(int i = __lg(n); i>=0; --i)
                if(a[jump2[i][x]]<a[MAX]) x=jump2[i][x], cnt+=1<<i;
            if(a[x]>=a[MAX]) rs=min(rs,cnt+1);
            else if(a[jump2[0][x]]>=a[MAX]) ++cnt, rs=min(rs,cnt+1);
        }
    }
    return (rs<1e9 ? rs : -1);
}
//int main()
//{
//    tt;
//    if(fopen((NAME + ".INP").c_str(), "r")) fo;
//}

• 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