Submission #956299

#	Time	Username	Problem	Language	Result	Execution time	Memory
956299		MrBrionix	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1008 ms	98488 KiB

jumps

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

const int MAXN = 200'005, LOGN = 20;
pair<int,int> succl[MAXN][LOGN],succr[MAXN][LOGN],succ[MAXN][LOGN];
vector<int> h;

void init(int N,vector<int> H){
    
    h=H;
    h.insert(h.begin(),0);
    
    stack<pair<int,int>> ds;
    ds.push({MAXN,0});
    succl[0][0]=ds.top();
    
    for(int i=0;i<N;i++){
        while(ds.top().first<H[i])ds.pop();
        succl[i+1][0]=ds.top();
        ds.push({H[i],i+1});
    }
    succl[N+1][0]={MAXN,0};
    
    while(!ds.empty())ds.pop();
    ds.push({MAXN,N+1});
    succr[N+1][0]=ds.top();
    
    for(int i=N-1;i>=0;i--){
        while(ds.top().first<H[i])ds.pop();
        succr[i+1][0]=ds.top();
        ds.push({H[i],i+1});
    }
    succr[0][0]={MAXN,N+1};
    
    for(int i=0;i<=N+1;i++){
        succ[i][0]=max(succl[i][0],succr[i][0]);
    }
    
    auto calc = [&](pair<int,int> v[][LOGN]){
        for(int i=1;i<LOGN;i++){
            for(int j=0;j<=N+1;j++){
                v[j][i]=v[v[j][i-1].second][i-1];
            }
        }
    };
    
    calc(succ);
    calc(succl);
    calc(succr);
}

int f(int x,int y){
    assert(x<y);
    
    int res=0;
    for(int i=LOGN-1;i>=0;i--){
        if(succ[x][i].first<=h[y]){
            //cout<<i<<" vale "<<succ[x][i].first<<" "<<succ[x][i].second<<"\n";
            x=succ[x][i].second;
            //cout<<"jumpo1 a "<<x<<"\n";
            res+=(1<<i);
        }
    }
    
    for(int i=LOGN-1;i>=0;i--){
        if(succl[x][i].first<=h[y]){
            x=succl[x][i].second;
            //cout<<"jumpo2 a "<<x<<"\n";
            res+=(1<<i);
        }
    }
    
    for(int i=LOGN-1;i>=0;i--){
        if(succr[x][i].first<=h[y]){
            x=succr[x][i].second;
            //cout<<"jumpo3 a "<<x<<"\n";
            res+=(1<<i);
        }
    }
    
    if(x!=y)res=-1;
    return res;
}

int calc(int A,int B,int x){
    for(int i=LOGN-1;i>=0;i--){
        if(succl[B][i].second>=A && succl[B][i].first<=h[x]){
            B=succl[B][i].second;
        }
    }
    return B;
}

int minimum_jumps(int A,int B,int C,int D){
    int ans = INT_MAX;
    A++;
    B++;
    C++;
    D++;
    
    int x = B;
    for(int i=LOGN-1;i>=0;i--){
        if(succr[x][i].second<C){
            x = succr[x][i].second;
        }
    }
    
    x = succr[x][0].second;
    assert(x>=C);
    if(x<=D){
        int st = calc(A,B,x);
        ans=min(ans,f(st,x));
    }
    
    int tmp = calc(0,B,x);
    tmp = succl[tmp][0].second;
    
    for(int i=LOGN-1;i>=0;i--){
        if(succr[x][i].first<=h[tmp]){
            x = succr[x][i].second;
        }
    }
    x = succr[x][0].second;
    
    if(x<=D){
        int st = calc(A,B,x);
        ans=min(ans,f(st,x));
    }
    
    /*
    for(int i=A;i<=B;i++){
        for(int j=C;j<=D;j++){
            int tmp = f(i,j);
            
            if(tmp!=-1)
            ans=min(ans,tmp);
        }
    }
    */
    if(ans==INT_MAX)ans=-1;
    return ans;
}
/*
int main() {
    int N, Q;
    assert(2 == scanf("%d %d", &N, &Q));
    std::vector<int> H(N);
    for (int i = 0; i < N; ++i) {
        assert(1 == scanf("%d", &H[i]));
    }
    init(N, H);
    
    for (int i = 0; i < Q; ++i) {
        int A, B, C, D;
        assert(4 == scanf("%d %d %d %d", &A, &B, &C, &D));
        printf("%d\n", minimum_jumps(A, B, C, D));
    }
    return 0;
}*/

• 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