Submission #922013

#	Time	Username	Problem	Language	Result	Execution time	Memory
922013		adhityamv	Rainforest Jumps (APIO21_jumps)	C++17	77 / 100	4051 ms	99260 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int,int>
#define fi first
#define se second
const int N=200000;
const int ln=20;
int INF=1000000000;
int leftjump[N];
int rightjump[N];
int h[N];
int n;
pii seg[2*N][ln];
int onlyr[2*N][ln];
void updateonlyr(int i,int val,int tp){
    i+=n;
    onlyr[i][tp]=val;
    while(i>1){
        onlyr[i>>1][tp]=max(onlyr[i][tp],onlyr[i^1][tp]);
        i>>=1;
    }
}
int queryonlyr(int l,int r,int tp){
    r++;
    l+=n;
    r+=n;
    int ans=-INF;
    while(l<r){
        if(l&1){
            ans=max(ans,onlyr[l][tp]);
            l++;
        }
        if(r&1){
            ans=max(ans,onlyr[r-1][tp]);
            r--;
        }
        l>>=1;
        r>>=1;
    }
    return ans;
}
void update(int i,pii val,int tp){
    i+=n;
    seg[i][tp]=val;
    while(i>1){
        seg[i>>1][tp].first=min(seg[i][tp].first,seg[i^1][tp].first);
        seg[i>>1][tp].second=max(seg[i][tp].second,seg[i^1][tp].second);
        i>>=1;
    }
}
pii query(int l,int r,int tp){
    r++;
    l+=n;
    r+=n;
    pii ans=mp(INF,-INF);
    while(l<r){
        if(l&1){
            ans.first=min(ans.first,seg[l][tp].first);
            ans.second=max(ans.second,seg[l][tp].second);
            l++;
        }
        if(r&1){
            ans.first=min(ans.first,seg[r-1][tp].first);
            ans.second=max(ans.second,seg[r-1][tp].second);
            r--;
        }
        l>>=1;
        r>>=1;
    }
    return ans;
}
void init(int nn,vector<int> hh){
    n=nn;
    for(int i=0;i<n;i++)  (h[i]=hh[i]);
    stack<int> fl;
    fl.push(-1);
    for(int i=0;i<n;i++){
        while(fl.top()!=-1 && h[fl.top()]<h[i]) fl.pop();
        leftjump[i]=fl.top();
        fl.push(i);
    }
    stack<int> fr;
    fr.push(-1);
    for(int i=n-1;i>=0;i--){
        while(fr.top()!=-1 && h[fr.top()]<h[i]) fr.pop();
        rightjump[i]=fr.top();
        fr.push(i);
    }
    for(int i=0;i<n;i++){
        if(rightjump[i]==-1) rightjump[i]=n;
    }
    for(int j=0;j<ln;j++) for(int i=0;i<2*n;i++) seg[i][j]=mp(INF,-INF);
    for(int i=0;i<n;i++){
        update(i,mp(leftjump[i],rightjump[i]),0);
    }
    //for(int i=0;i<2*n;i++) cout << seg[i][0].first << " " << seg[i][0].second << "\n";
    for(int j=0;j<ln-1;j++){
        for(int i=0;i<n;i++){
            update(i,query(seg[i+n][j].first,seg[i+n][j].second,j),j+1);
        }
    }
    for(int i=0;i<n;i++){
        updateonlyr(i,rightjump[i],0);
    }
    for(int j=0;j<ln-1;j++){
        for(int i=0;i<n;i++){
            if(onlyr[i+n][j]==n) updateonlyr(i,n,j+1);
            else updateonlyr(i,onlyr[onlyr[i+n][j]+n][j],j+1);
        }
    }
}
bool out(int m,pii p){
    if(p.first<=m && m<=p.second) return false;
    return true;
}
int cequalsd(int a,int b,int c){
    int lb=leftjump[c];
    if(lb==c) lb=-1;
    if(b<=lb) return -1;
    a=max(a,lb+1);
    int cnt=0;
    for(int j=ln-1;j>=0;j--){
        auto p=query(a,b,j);
        if(out(lb,p) && out(c,p)){
            a=p.first;
            b=p.second;
            cnt+=(1<<j);
        }
    }
    auto p=query(a,b,0);
    if(!out(c,p)){
        return cnt+1;
    }
    int bl=a;
    int br=b;
    while(bl!=br){
        int bm=(bl+br)/2;
        if(out(lb,query(a,bm,0))){
            bl=bm+1;
        } else br=bm;
    }
    a=bl;
    for(int j=ln-1;j>=0;j--){
        int nb=queryonlyr(a,b,j);
        if(nb<c){
            b=nb;
            cnt+=(1<<j);
        }
    }
    return cnt+1;
}
int minimum_jumps(int a,int b,int c,int d){
    int ans=N;
    for(int j=c;j<=d;j++){
        int cans=cequalsd(a,b,j);
        if(cans!=-1) ans=min(cans,ans);
    }
    if(ans==N) ans=-1;
    return ans;
}

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