Submission #552783

#	Time	Username	Problem	Language	Result	Execution time	Memory
552783		farhan132	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1178 ms	55976 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
 
 
 
using namespace std;
 
typedef int ll;
typedef unsigned long long ull;
typedef double dd;
typedef vector<ll> vll;
typedef pair<ll , ll> ii;
typedef vector< ii > vii;
typedef pair < pair < ll , ll > , pair < ll , ll > > cm; 
typedef tuple < ll,  ll, ll > tp;
 
#define ff first
#define ss second
#define pb push_back
#define in insert
#define f0(b) for(int i=0;i<(b);i++)
#define f00(b) for(int j=0;j<(b);j++)
#define f1(b) for(int i=1;i<=(b);i++)
#define f11(b) for(int j=1;j<=(b);j++)
#define f2(a,b) for(int i=(a);i<=(b);i++)
#define f22(a,b) for(int j=(a);j<=(b);j++)
#define sf(a) scanf("%lld",&a)
#define sff(a,b) scanf("%lld %lld", &a , &b)
#define pf(a) printf("%lld\n",a)
#define pff(a,b) printf("%lld %lld\n", a , b)
#define bug printf("**!\n")
#define mem(a , b) memset(a, b ,sizeof(a))
#define front_zero(n) __builtin_clzll(n)
#define back_zero(n) __builtin_ctzll(n)
#define total_one(n) __builtin_popcount(n)
#define clean fflush(stdout)
 
//const ll mod =  (ll) 998244353;
const ll mod =  (ll) 1e9 + 7;
const ll maxn = (ll)1e8 + 5;
const int nnn = 1048590;
const int inf = numeric_limits<int>::max()-1;
//const ll INF = numeric_limits<ll>::max()-1;
//const ll INF = (ll)1e18;
 
ll dx[]={0,1,0,-1};
ll dy[]={1,0,-1,0};
ll dxx[]={0,1,0,-1,1,1,-1,-1};
ll dyy[]={1,0,-1,0,1,-1,1,-1};

const ll N = 2e5 + 5;
ll a[N], n, p[N];
ll lft[N] , rght[N];
ll par[N][20], L[N][20], R[N][20];

struct seg_tree{

  struct typo{
    ll mx;
    void setup(ll _sum){
      mx = _sum;
    }
  };

  vector < typo > b;
  ll n;

  void init(ll l, ll r, ll node){
    b[node].setup(a[l]);
    return;
  }

  typo merge(typo a, typo b){
    typo c;
    c.mx = max(a.mx, b.mx);
    return c;
  }

  void build(ll l, ll r, ll node){
    if(l == r){
      init(l,r,node);
      return;
    }
    ll mid = (l + r)/2;
    ll n1 = 2*node;
    ll n2 = n1 + 1;
    build(l, mid , n1);
    build(mid+1, r, n2);
    b[node] = merge(b[n1] , b[n2]);
    return;
  }

  void build(ll _n){
    n = _n;
    b.resize(4*n);
    build(1,n,1); // optional
  }
  typo get(ll l, ll r, ll node, ll x, ll y){
    if(y < l || x > r) return {0};
    if(x <= l && y >= r){
      return b[node];
    }
    ll mid = (l + r)/2;
    ll n1 = 2*node;
    ll n2 = n1 + 1;
    return merge(get(l , mid , n1 , x , y) , get(mid + 1, r , n2 , x , y));
  }

  ll get(ll l, ll r){
    return get(1,n,1,l,r).mx;
  }

  /* Final Check!!!
     1. Typo, Okay?
     2. Init Okay? (Build!!)
     3. Merge, Okay?
     4. Lazy Needed ? YES | NO (if NO, REMOVE anything related to lazy prop)
     5. Dummy?
     6. Check Update, Get, etc function's Merge, Lazy Prop , Init :D
     7, Even after a WA, check for possible Out Of Bound/MLE/RE cases
  */

}T;



void init(int _n, std::vector<int> H) {
  n = _n;
  for(ll i = 1; i <= n; i++){
    a[i] = H[i - 1];
    p[a[i]] = i;
  }
  a[0] = a[n + 1] = n + 1;
  stack < ll > st;
  st.push(0);
  for(ll i = 1; i <= n; i++){
    while(st.size() && a[st.top()] < a[i]) st.pop();
    lft[i] = st.top();
    st.push(i);
  }
  while(st.size()) st.pop(); 
  st.push(n + 1);
  for(ll i = n; i >= 1; i--){
    while(st.size() && a[st.top()] < a[i]) st.pop();
    rght[i] = st.top();
    st.push(i);
  }
  for(ll i = 0; i < 20; i++){
    par[0][i] = L[0][i] = R[0][i] = 0;
    par[n+1][i] = L[n+1][i] = R[n+1][i] = n+1;
  }
  for(ll i = 1; i <= n; i++){
    if(a[lft[i]] > a[rght[i]]) par[i][0] = lft[i];
    else par[i][0] = rght[i];
    L[i][0] = lft[i];
    R[i][0] = rght[i];
  }
  for(ll j = 1; j < 20; j++){
    for(ll i = 1; i <= n; i++){
      par[i][j] = par[par[i][j - 1]][j - 1];
      L[i][j] = L[L[i][j-1]][j-1];
      R[i][j] = R[R[i][j-1]][j-1];
    }
  }
  T.build(n);


  return;
}

ll apply(ll x, ll C, ll D){
  ll res = 0;
  for(ll i = 19; i >= 0; i--){
    if(R[x][i] < C) x = R[x][i], res += (1 << i);
  }
  if(rght[x] <= D) res++;
  else res = 1e9;
  return res;
}

int minimum_jumps(int A, int B, int C, int D) {
  A++; B++; C++; D++;

  ll e = T.get(C,D);
  if(a[B] > e) return -1;
  ll x = B;
  for(ll i = 19; i >= 0; i--){
    if(A <= L[x][i] && a[L[x][i]] < e) x = L[x][i];
  }

  ll prob = T.get(x, C-1);
  if(prob > e) return -1;
  ll ans = 0;
  for(ll i = 19; i >= 0; i--){
    if(a[par[x][i]] <= prob){
      ans += (1 << i);
      x = par[x][i];
    }
  }
  ll k = apply(x, C, D);
  if(lft[x]) k = min(k, 1 + apply(lft[x], C,D));
  if(k > n) return -1;
  return ans + k;
}

• 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