Submission #412456

#	Time	Username	Problem	Language	Result	Execution time	Memory
412456		azberjibiou	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1716 ms	54976 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define bp __builtin_popcount
#define fir first
#define sec second
#define pii pair<int, int>
#define pll pair<ll, ll>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
int dx[4]={0, 1, 0, -1}, dy[4]={1, 0, -1 , 0};
const int mxN=200100;
const int mxM=104;
const int mxK=50000;
const int MOD=1000000007;
const ll INF=100000000000001;
int N;
int H[mxN];
stack <pii> stk;
int L[mxN], R[mxN];
void make_link()
{
    for(int i=0;i<N;i++)
    {
        while(!stk.empty())
        {
            pii now=stk.top();
            if(now.sec<H[i])    stk.pop();
            else    break;
        }
        if(!stk.empty())    L[i]=stk.top().fir;
        else    L[i]=i;
        stk.push({i, H[i]});
    }
    while(!stk.empty()) stk.pop();
    for(int i=N-1;i>=0;i--)
    {
        while(!stk.empty())
        {
            pii now=stk.top();
            if(now.sec<H[i])    stk.pop();
            else    break;
        }
        if(!stk.empty())    R[i]=stk.top().fir;
        else    R[i]=i;
        stk.push({i, H[i]});
    }
}
int spL[mxN][20], spR[mxN][20];
int spI[mxN][20];
void make_sparse()
{
    for(int i=0;i<N;i++)
    {
        spL[i][0]=L[i], spR[i][0]=R[i];
    }
    for(int i=1;i<20;i++)
    {
        for(int j=0;j<N;j++)
        {
            spL[j][i]=spL[spL[j][i-1]][i-1];
            spR[j][i]=spR[spR[j][i-1]][i-1];
        }
    }
    for(int i=0;i<N;i++)    spI[i][0]=(H[L[i]]<H[R[i]] ? R[i] : L[i]);
    for(int i=1;i<20;i++)
    {
        for(int j=0;j<N;j++)
        {
            spI[j][i]=spI[spI[j][i-1]][i-1];
        }
    }
}
int seg[4*mxN];
void init_seg(int idx, int s, int e)
{
    if(s==e)
    {
        seg[idx]=H[s];  return;
    }
    int mid=(s+e)/2;
    init_seg(2*idx, s, mid);
    init_seg(2*idx+1, mid+1, e);
    seg[idx]=max(seg[2*idx], seg[2*idx+1]);
}
int solv(int idx, int s1, int e1, int s2, int e2)
{
    if(s2>e1 || s1>e2)  return 0;
    if(s2<=s1 && e1<=e2)    return seg[idx];
    int mid=(s1+e1)/2;
    return max(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
}
void init(int n, std::vector<int> h) {
    N=n;
    for(int i=0;i<N;i++)    H[i]=h[i];
    make_link();
    make_sparse();
    init_seg(1, 0, N-1);
}

int minimum_jumps(int A, int B, int C, int D)
{
    int cnt=0;
    if(solv(1, 0, N-1, B, C-1)>solv(1, 0, N-1, C, D))  return -1;
    if(B==C-1)  return 1;
    int minH, maxH;
    maxH=solv(1, 0, N-1, C, D);
    minH=solv(1, 0, N-1, B+1, C-1);
    int ABnow=B;
    for(int i=19;i>=0;i--)
    {
        if(H[spL[ABnow][i]]<maxH && spL[ABnow][i]>=A)   ABnow=spL[ABnow][i];
    }
    if(H[ABnow]>minH)   return 1;
    for(int i=19;i>=0;i--)
    {
        if(H[spI[ABnow][i]]<minH)
        {
            ABnow=spI[ABnow][i];
            cnt+=(1<<i);
        }
    }
    if(R[ABnow]>=C) return cnt+1;
    if(H[L[ABnow]]>minH && H[L[ABnow]]<maxH)  return cnt+2;
    for(int i=19;i>=0;i--)
    {
        if(spR[ABnow][i]<C)
        {
            ABnow=spR[ABnow][i];
            cnt+=(1<<i);
        }
    }
    return cnt+1;
}

• 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