Submission #1052552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052552		user736482	Rainforest Jumps (APIO21_jumps)	C++17	25 / 100	1111 ms	35632 KiB

jumps

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

int lft[200007],rgt[200007],jmpl[200007][18],jmpg[200007][18];
bool czy1=1;
bool odw[200007];
int n;
vector<int>v;
void init(int N,vector<int>V){
    n=N;
    v=V;
    while(v.size()<200007)
        v.push_back(200006);
    stack<int>s;
    lft[200006]=200006;
    rgt[200006]=200006;
    //s.push(n);
    for(int i=0;i<n;i++){
        lft[i]=200006;
        rgt[i]=200006;
    }
    //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];
    }
    jmpl[200006][0]=200006;
    jmpg[200006][0]=200006;
    for(int i=1;i<18;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[200006][i]=200006;
        jmpg[200006][i]=200006;
       // cout<<"\n";
    }
    //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;
    if(a==b && c==d){
        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;
    }
    odw[200006]=1;
    int ans[n];
    for(int i=0;i<n;i++){ odw[i]=0; ans[i]=200007;}
    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=200007;
    for(int i=c;i<=d;i++){
        mn=min(mn,ans[i]);
    }
    if(mn==200007)
        mn=-1;
    //cout<<ans[11];
    return mn;
}

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