Submission #1101324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1101324		Warinchai	Rainforest Jumps (APIO21_jumps)	C++14	69 / 100	1020 ms	34120 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
#include <vector>
using namespace std;

int n;
int l[200005];
int r[200005];
int in[200005];
int out[200005];
int tme=0;
int h[200005];
int jl[200005];
int jr[200005];
int sp[200005];
int pa[20][200005];
int dis[20][200005];
int inf=1e9;

void dfs(int u,int pl=0,int pr=0,int p=0){
    in[u]=++tme;
    int x=h[pl]<h[pr]?pl:pr;
    //cerr<<"BINJUMP:"<<u<<" "<<x<<"\n";
    pa[0][u]=x;
    for(int i=1;i<20;i++)pa[i][u]=pa[i-1][pa[i-1][u]];
    //cerr<<u<<":"<<l[u]<<" "<<r[u]<<"\n";
    h[u]=h[p]+1;
    if(l[u])dfs(l[u],pl,u,u);
    if(r[u])dfs(r[u],u,pr,u);
    out[u]=tme;
}
struct segtree{
    struct node{
        int val,id;
        node(int _val=inf,int _id=inf){
            val=_val,id=_id;
        }
        friend node operator+(node a,node b){
            node c;
            c.val=min(a.val,b.val);
            c.id=a.val<b.val?a.id:b.id;
            return c;
        }
    };
    node info[800005];
    void upd(int st,int en,int i,int pos,int val){
        if(st>pos||en<pos)return;
        if(st==en)return void(info[i]=node(val,pos));
        int m=(st+en)/2;
        upd(st,m,i*2,pos,val);
        upd(m+1,en,i*2+1,pos,val);
        info[i]=info[i*2]+info[i*2+1];
    }
    node fans(int st,int en,int i,int l,int r){
        if(st>r||en<l)return node();
        if(st>=l&&en<=r)return info[i];
        int m=(st+en)/2;
        return fans(st,m,i*2,l,r)+fans(m+1,en,i*2+1,l,r);
    }
}tr;
void init(int N, std::vector<int> H) {
    n=N;
    stack<int>s;
    int rt=0;
    for(int i=1;i<=N;i++){
        while(!s.empty()&&H[i-1]>H[s.top()-1])l[i]=s.top(),s.pop();
        if(s.empty())rt=i;
        else r[s.top()]=i;
        s.push(i);
    }
    dfs(rt);
    for(int i=1;i<=N;i++){
        tr.upd(1,n,1,i,h[i]);
    }
    //cerr<<"\n\n";
}

int mn(int A,int B,int C){
    int ans=0;
    int val=h[C];
    int l=A,r=B;
    int st=A,en=B;
    //cerr<<"ABC:"<<A<<" "<<B<<" "<<C<<"\n";
    if(C>=A&&C<=B)return 0;
    if(C<A){
        if(!(in[A]>=in[C]&&in[A]<=out[C]))return inf;
        while(st<=en){
            int m=(st+en)/2;
            if(in[m]>=in[C]&&in[m]<=out[C])r=m,st=m+1;
            else en=m-1;
        }
    }else{
        if(!(in[B]>=in[C]&&in[B]<=out[C]))return inf;
        while(st<=en){
            int m=(st+en)/2;
            if(in[m]>=in[C]&&in[m]<=out[C])l=m,en=m-1;
            else st=m+1;
        }
    }
    //cerr<<l<<' '<<r<<"\n";
    int nw=tr.fans(1,n,1,l,r).id;
    //cerr<<"new:"<<nw<<"\n";
    if(in[nw]>=in[C]&&in[nw]<=out[C]){
        for(int i=19;i>=0;i--){
            //cerr<<i<<"possible:"<<A<<" "<<pa[A][i]<<"\n";
            if(h[pa[i][nw]]>=h[C])nw=pa[i][nw],ans+=(1<<i);
        }
        ans+=h[nw]-h[C];
        return ans;
    }
    return inf;
}
int minimum_jumps(int A, int B, int C, int D) {
    A++,B++,C++,D++;
    if(n>2000&&A!=B&&C!=D)return mn(A,B,C);
    int x=inf;
    for(int i=C;i<=D;i++)x=min(x,mn(A,B,i));
    return x==inf?-1:x;
}

Compilation message (stderr)

jumps.cpp: In function 'int mn(int, int, int)':
jumps.cpp:80:9: warning: unused variable 'val' [-Wunused-variable]
   80 |     int val=h[C];
      |         ^~~

• Subtask 1: 4 / 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