Submission #1223522

#	Time	Username	Problem	Language	Result	Execution time	Memory
1223522		KALARRY	Rainforest Jumps (APIO21_jumps)	C++20	65 / 100	4042 ms	251648 KiB

jumps

//chockolateman

#include<bits/stdc++.h>

using namespace std;


int n,l[200005],r[200005],a[200005],up_max[200005][20],up_min[200005][20],max_st[800005];
set<int> st[800005]; //merge sort tree

void build(int v = 1,int start = 1,int end = n)
{
    if(start==end)
    {
        st[v].insert(a[start]);
        max_st[v] = a[start];
        return;
    }
    int mid = (start + end)/2;
    build(2*v,start,mid);
    build(2*v+1,mid+1,end);
    for(auto x : st[2*v])
        st[v].insert(x);
    for(auto x : st[2*v+1])
        st[v].insert(x);
    max_st[v] = max(max_st[2*v],max_st[2*v+1]);
}

int query(int left,int right,int val,int v = 1,int start = 1,int end = n)
{
    if(start==left && end==right)
    {
        if(*st[v].begin() > val)
            return 0;
        if(*st[v].rbegin() <= val)
            return *st[v].rbegin();
        auto it = st[v].upper_bound(val);
        it--;
        return *it;
    }
    int mid = (start + end)/2;
    if(right <= mid)
        return query(left,right,val,2*v,start,mid);
    else if(left > mid)
        return query(left,right,val,2*v+1,mid+1,end);
    else
        return max(query(left,mid,val,2*v,start,mid),query(mid+1,right,val,2*v+1,mid+1,end));

}

int query_max(int left,int right,int v = 1,int start = 1,int end = n)
{
    if(start==left && end==right)
        return max_st[v];
    int mid = (start + end)/2;
    if(right <= mid)
        return query_max(left,right,2*v,start,mid);
    else if(left > mid)
        return query_max(left,right,2*v+1,mid+1,end);
    else
        return max(query_max(left,mid,2*v,start,mid),query_max(mid+1,right,2*v+1,mid+1,end));
}

void init(int N, std::vector<int> H) {
    for(int i = 1 ; i <= N ; i++)
        a[i] = H[i-1];
    n = N;
    stack<int> order;
    order.push(N+1);
    for(int i = 1 ; i <= N ; i++)
    {
        while(H[i-1] > order.top())
            order.pop();
        l[a[i]] = order.top();
        order.push(a[i]);
    }
    while(!order.empty())
        order.pop();
    order.push(N+1);
    for(int i = N ; i >= 1 ; i--)
    {
        while(H[i-1] > order.top())
            order.pop();
        r[a[i]] = order.top();
        order.push(a[i]);
    }
    for(int L = 18 ; L >= 0 ; L--)
        up_max[N+1][L] = N+1;
    for(int i = 1 ; i <= N ; i++)
        up_max[i][0] = max(l[i],r[i]);
    for(int L = 1 ; L <= 18 ; L++)
        for(int i = 1 ; i <= N ; i++)
            up_max[i][L] = up_max[up_max[i][L-1]][L-1];
    for(int L = 18 ; L >= 0 ; L--)
        up_min[N+1][L] = N+1;
    for(int i = 1 ; i <= N ; i++)
        up_min[i][0] = min(l[i],r[i]);
    for(int L = 1 ; L <= 18 ; L++)
        for(int i = 1 ; i <= N ; i++)
            up_min[i][L] = up_min[up_min[i][L-1]][L-1];
    build();
}


int ans(long long v,long long targ)
{
    long long sums = (1ll<<18);
    long long ret = 0;
    for(int L = 18 ; L >= 0 ; L--)
    {
        while (up_max[v][L] <= targ)
        {
            v = up_max[v][L];
            ret += sums;
        }
        sums /= 2;
    }
        
    sums = (1ll<<18);
    for(int L = 18 ; L >= 0 ; L--)
    {
        while (up_min[v][L] <= targ)
        {
            v = up_min[v][L];
            ret += sums;
        }
        sums /= 2;
    }
    if(v != targ)
        ret = n+1;
    return ret;
}

int minimum_jumps(int A, int B, int C, int D) {
    A++;
    B++;
    C++;
    D++;
    int ret = 1e9;
    for(int j = C ; j <= D ; j++)
    {
        int front_chose = 0;
        int left = B;
        if(a[left] > a[j])
            continue;
        for(int b = n ; b >= 1 ; b/=2)
            while(left - b >= A && query_max(left-b,B) <= a[j])
                left -= b;
        front_chose = query_max(left,B);
        for(int i = B ; i >= A ; i--)
            if(a[i] <= a[j])
                front_chose = max(front_chose,a[i]);
            else 
                break;
        if(front_chose==0)
            continue;
        ret = min(ret,ans(front_chose,a[j]));
    }
    if(ret > n)
        ret = -1;
    return ret;
}

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