Submission #557334

#	Time	Username	Problem	Language	Result	Execution time	Memory
557334		new_acc	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1114 ms	48968 KiB

jumps

#include<bits/stdc++.h>
#include "jumps.h"
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e5+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e13;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=18;
int t[N],l[N][L+1],r[N][L+1],w[N][L+1],n;
void init(int nn,vi v){
    n=nn;
    for(int i=1;i<=n;i++) t[i]=v[i-1];
    deque<pair<int,int> >deq;
    for(int i=n;i>=1;i--){
        while(deq.size() and deq.back().fi<t[i]) deq.pop_back();
        if(!deq.size()) r[i][0]=n+1;
        else r[i][0]=deq.back().se;
        deq.push_back({t[i],i});
    }
    deq.clear();
    for(int i=1;i<=n;i++){
        while(deq.size() and deq.back().fi<t[i]) deq.pop_back();
        if(!deq.size()) l[i][0]=0;
        else l[i][0]=deq.back().se;
        deq.push_back({t[i],i});
    }
    for(int i=0;i<=L;i++) r[n+1][i]=n+1;
    for(int i=1;i<=n;i++){
        for(int k=1;k<=L;k++) l[i][k]=l[l[i][k-1]][k-1];
    }
    for(int i=n;i>=1;i--){
        for(int k=1;k<=L;k++) r[i][k]=r[r[i][k-1]][k-1];
    }
    t[n+1]=INFi;
    for(int i=1;i<=n;i++){
        if((r[i][0]==n+1 and l[i][0]!=0) or t[l[i][0]]>t[r[i][0]]) w[i][0]=l[i][0];
        else w[i][0]=r[i][0];
    }
    for(int i=0;i<=L;i++) w[n+1][i]=n+1;
    for(int i=1;i<=L;i++){
        for(int k=1;k<=n;k++) w[k][i]=w[w[k][i-1]][i-1];
    }
}
int minimum_jumps(int a,int b,int c,int d){
    a++,b++,c++,d++;
    int cc=c;
    int tt=t[cc];
    for(int i=L;i>=0;i--) if(r[cc][i]<=d) cc=r[cc][i];
    if(t[b]>t[cc]) return -1;
    int bb=b;
    for(int i=L;i>=0;i--) if(l[bb][i]>=a and t[l[bb][i]]<t[cc]) bb=l[bb][i];
    int maxi=0;
    cc=b+1;
    for(int i=L;i>=0;i--) if(r[cc][i]<c) cc=r[cc][i];
    if(cc<c) maxi=t[cc];
    else return 1;
    int curr=0,res=-1;
    for(int i=L;i>=0;i--)
        if(t[w[bb][i]]<maxi and w[bb][i]<c) bb=w[bb][i],curr+=(1<<i);  
    cc=bb;
    int il=curr;
    for(int i=L;i>=0;i--)
        if(r[cc][i]<c) il+=(1<<i),cc=r[cc][i];
    if(r[cc][0]>d) return -1;
    res=il+1;
    int res2=INFi;
    curr++,bb=w[bb][0];
    if(bb>d) return res;
    if(bb>=c) return min(res,curr);
    for(int i=L;i>=0;i--){
        if(r[bb][i]<c) curr+=(1<<i),bb=r[bb][i];
        else res2=curr+(1<<i);
    }
    if(r[bb][0]>d) res2=INFi;
    return min(res,res2);
}
/*int main(){
    int n;
    cin>>n;
    vi xd;
    for(int i=1;i<=n;i++){
        int a;
        cin>>a;
        xd.push_back(a);
    }
    init(n,xd);
    int q;
    cin>>q;
    while(q--){
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        cout<<minimum_jumps(a,b,c,d)<<"\n";
    }
}*/

Compilation message (stderr)

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:59:9: warning: unused variable 'tt' [-Wunused-variable]
   59 |     int tt=t[cc];
      |         ^~

• 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