Submission #1052662

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052662		user736482	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	565 ms	57900 KiB

jumps

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

int lft[400007],rgt[400007],jmpl[400007][19],jmpg[400007][19],spars[200007][18],pos[200007];
bool czy1=1;
bool odw[400007];
int n;
vector<int>v;
int lg(int x){
    int res=0;
    x/=2;
    res++;
    while(x>0){
        res++;
        x/=2;
    }
    return res;
}
int mx(int a,int b){
    int k=b-a+1;
    if(k<=0) return -1;
    //cout<<spars[a][lg(k+1)-1];
    return max(spars[a][lg(k+1)-1],spars[b+1-(1<<(lg(k+1)-1))][lg(k+1)-1]);
}
int furthest_greater(int a1,int b1,int x){
    //cout<<"q";
    while(a1!=b1){
     //       cout<<a1<<" "<<b1<<"  c ";
        int mid=(a1+b1)/2;
        if(mx(mid+1,b1)>x) a1=mid+1;
        else b1=mid;
    }
    if(v[a1]>x)return a1;
    else return a1-1;
}
void init(int N,vector<int>V){
    n=N;
    v=V;
    while(v.size()<400007)
        v.push_back(400006);
    stack<int>s;
    lft[400006]=400006;
    rgt[400006]=400006;
    //s.push(n);
    for(int i=0;i<n;i++){
        pos[v[i]]=i;
        lft[i]=400006;
        rgt[i]=400006;
    }
    //return;
    for(int i=0;i<n;i++){
        if(s.empty() || v[s.top()]>v[i])
            s.push(i);
        else{
            rgt[s.top()]=i;
            s.pop();
            i--;
        }
    }
    while(s.size()>0) s.pop();
    for(int i=n-1;i>=0;i--){
        if(s.empty() || v[s.top()]>v[i])
            s.push(i);
        else{
            czy1=0;
            lft[s.top()]=i;
            s.pop();
            i++;
        }
    }
    for(int i=0;i<n;i++){
        int pm=lft[i];
        if(v[lft[i]]>v[rgt[i]]){
            lft[i]=rgt[i];
            rgt[i]=pm;
        }
        jmpg[i][0]=rgt[i];
        jmpl[i][0]=lft[i];
        spars[i][0]=v[i];
    }
    jmpl[400006][0]=400006;
    jmpg[400006][0]=400006;
    for(int i=1;i<19;i++){
        for(int j=0;j<n;j++){
            jmpl[j][i]=jmpl[jmpl[j][i-1]][i-1];
            jmpg[j][i]=jmpg[jmpg[j][i-1]][i-1];
       //     cout<<jmpg[j][i]<<" ";
        }
        jmpl[400006][i]=400006;
        jmpg[400006][i]=400006;
       // cout<<"\n";
    }
    for(int i=1;i<18;i++){
        for(int j=0;j<n+1-(1<<i);j++){
            spars[j][i]=max(spars[j][i-1],spars[j+(1<<(i-1))][i-1]);
        }
    }
    //for(int i=0;i<n;i++)
    //cout<<lft[i]<<" "<<rgt[i]<<"\n";
}
int minimum_jumps(int a,int b,int c,int d){
    if(czy1)
        return c-b;
    int odp=0;
    if(c==d){
        int sava=a;
        a=pos[mx(furthest_greater(a,b,v[c])+1,b)];
    //cout<<a;//<<" "<<furthest_greater(sava,b,c)<<" ";
        if(a==-1) return -1;
        int akindex=-1;
        //int odp=0;
        while(v[jmpg[a][akindex+1]]<=v[c])
            akindex++;
        if(akindex>=0){
        odp+=1<<akindex;
        //cout<<akindex<<" a ";
        //return 0;
        //cout<<a<<" ";
        a=jmpg[a][akindex];
        //cout<<a<<" ";
        akindex--;}
        while(akindex>=0){
            if(v[jmpg[a][akindex]]>v[c]){
                akindex--;
                continue;
            }
            odp+=1<<akindex;
            a=jmpg[a][akindex];
            akindex--;
            cout<<a<<" ";
        }
        akindex=-1;
        while(v[jmpl[a][akindex+1]]<=v[c])
            akindex++;
        if(akindex>=0){
        odp+=1<<akindex;
        //cout<<akindex<<" a ";
        //return 0;
        a=jmpl[a][akindex];
        akindex--;}
        while(akindex>=0){
            if(v[jmpl[a][akindex]]>v[c]){
                akindex--;
                continue;
            }
            odp+=1<<akindex;
            a=jmpl[a][akindex];
            akindex--;
            //cout<<a<<" ";
        }
        if(a!=c)
            odp=-1;
        return odp;
        a=sava;
    }
    odw[400006]=1;
    int ans[n];
    for(int i=0;i<n;i++){ odw[i]=0; ans[i]=400007;}
    for(int i=a;i<=b;i++) odw[i]=1;
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;
    for(int i=a;i<=b;i++){
        pq.push({0,i});
    }
    while(!pq.empty()){
        pair<int,int>pom=pq.top();
        pq.pop();
        ans[pom.second]=pom.first;
        if(!odw[lft[pom.second]]){
            odw[lft[pom.second]]=1;
            pq.push({pom.first+1,lft[pom.second]});
        }
        if(!odw[rgt[pom.second]]){
            odw[rgt[pom.second]]=1;
            pq.push({pom.first+1,rgt[pom.second]});
        }
        //return 0;
    }
    int mn=400007;
    for(int i=c;i<=d;i++){
        mn=min(mn,ans[i]);
    }
    if(mn==400007)
        mn=-1;
    //cout<<ans[11];
    //cout<<mn;
    return mn;
}

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