Submission #1049526

#	Time	Username	Problem	Language	Result	Execution time	Memory
1049526		Maite_Morale	Rainforest Jumps (APIO21_jumps)	C++17	4 / 100	974 ms	288576 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define vll vector<ll>
#define MAX 500005
#define pll pair<ll,ll>
#define oo 10000000000000
#define F first
#define S second

const ll bts=20;
pll p[30][MAX],s[bts+10][MAX],t[bts+10][MAX];
vll v[MAX];
ll d[MAX],N;
pll query(ll x,ll y){
  if(x>y)return {0,N};
  ll c=log2l(abs(x-y)+1);
return max(t[c][x],t[c][y-(1LL<<c)+1]);
}
void dfs(ll x,ll y){
  d[x]=d[y]+1;
  for(auto w : v[x])dfs(w,x);
}
void init(int n, std::vector<int> h) {
    h.push_back(oo);
    stack<ll>  s1;s1.push(n);
    for(int i=0;i<n;i++){
        t[0][i]={h[i],i};
        while(h[i]>h[s1.top()]){
            p[0][s1.top()].S=i;
            s1.pop();
        }
        p[0][i].F=s1.top();
       s1.push(i);
    }
    while(!s1.empty()){p[0][s1.top()].S=n;s1.pop();}
    s[0][n]={n,n};
    for(int i=0;i<n;i++){
      s[0][i].F=max(pll {h[p[0][i].F],p[0][i].F},pll {h[p[0][i].S],p[0][i].S}).S;
      s[0][i].S=min(pll {h[p[0][i].F],p[0][i].F},pll {h[p[0][i].S],p[0][i].S}).S;
      v[s[0][i].S].push_back(i);
      if(p[0][i].F==n)p[0][i].F=-1;
      //cout<<p[i].F<<" ";
    }///cout<<"\n";
    dfs(n,n);
    for(int i=1;i<=bts;i++){
      for(int j=0;j<=n;j++){
        t[i][j]=max(t[i-1][j],t[i-1][j+(1LL<<(i-1))]);
        s[i][j].F=s[i-1][s[i-1][j].F].F;
        s[i][j].S=s[i-1][s[i-1][j].S].S;
        p[i][j].S=p[i-1][p[i-1][j].S].S;
        //if(i==20)cout<<d[j]<<" ";
        //else     cout<<s[i][j].S<<" ";
      }//cout<<"\n";
    }
}
int minimum_jumps(int A, int B, int C, int D) {
    D=query(C,D).S;
    A=max((ll)A,p[0][D].F+1LL);
    if(A>B)return -1;
    A=query(A,B).S;
    ll P=A;
    for(int i=bts;i>=0;i--){
      if(p[i][P].S<C)P=p[i][P].S;      
    }P=p[0][P].S;
    //cout<<A<<" "<<B<<"\n";
    ll r=0;
    for(int i=bts;i>=0;i--){
      if(d[s[i][A].F]>=d[P]){
          r+=(1LL<<i);
          A=s[i][A].F;
      }
    }
    ll ans=oo;
    if(s[1][A].F<=D)ans=r+2;
    for(int i=bts;i>=0;i--){
      if(d[s[i][A].S]>=d[P]){
          r+=(1LL<<i);
          A=s[i][A].S;
      }
    }
    return min(ans,r);
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:7:12: warning: overflow in conversion from 'long int' to 'std::vector<int>::value_type' {aka 'int'} changes value from '10000000000000' to '1316134912' [-Woverflow]
    7 | #define oo 10000000000000
      |            ^~~~~~~~~~~~~~
jumps.cpp:25:17: note: in expansion of macro 'oo'
   25 |     h.push_back(oo);
      |                 ^~

• 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