Submission #951764

#	Time	Username	Problem	Language	Result	Execution time	Memory
951764		abczz	Rainforest Jumps (APIO21_jumps)	C++14	100 / 100	1062 ms	76656 KiB

jumps

#include "jumps.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long

using namespace std;

vector <array<ll, 2> > V;
array<ll, 2> L[200000], R[200000];
ll n, z, s, mx, k, X[200000], jmp[200000][18], bl[200000][18], st[800000];

void build(ll id, ll l, ll r) {
  if (l == r) {
    st[id] = X[l];
    return;
  }
  ll mid = (l+r)/2;
  build(id*2, l, mid);
  build(id*2+1, mid+1, r);
  st[id] = max(st[id*2], st[id*2+1]);
}

ll query(ll id, ll l, ll r, ll ql, ll qr) {
  if (qr < l || r < ql) return -1;
  else if (ql <= l && r <= qr) return st[id];
  ll mid = (l+r)/2;
  return max(query(id*2, l, mid, ql, qr), query(id*2+1, mid+1, r, ql, qr));
}

void find(ll id, ll l, ll r, ll ql, ll qr) {
  if (qr < l || r < ql) return;
  //cout << l << " " << r << '\n';
  if (l == r) {
    if (mx < st[id]) mx = st[id], s = l;
    return;
  }
  ll mid = (l+r)/2;
  if (ql <= l && r <= qr) {
    if (st[id*2] < st[id*2+1]) find(id*2+1, mid+1, r, ql, qr);
    else find(id*2, l, mid, ql, qr);
    return;
  }
  find(id*2, l, mid, ql, qr);
  find(id*2+1, mid+1, r, ql, qr);
}

void solve(ll id, ll l, ll r, ll ql, ll qr) {
  if (qr < l || r < ql || k != -1) return;
  ll mid = (l+r)/2;
  if (ql <= l && r <= qr) {
    if (st[id] >= z) {
      if (l == r) {
        k = l;
        return;
      }
      solve(id*2+1, mid+1, r, ql, qr);
      solve(id*2, l, mid, ql, qr);
    }
    return;
  }
  solve(id*2+1, mid+1, r, ql, qr);
  solve(id*2, l, mid, ql, qr);
}

void init(int N, std::vector<int> H) {
  n = N;
  for (int i=0; i<N; ++i) {
    X[i] = H[i];
  }
  build(1, 0, n-1);
  ll l, r, mid;
  for (int i=0; i<n; ++i) {
    L[i] = {-1, -1};
    l = 0, r = (ll)V.size()-1;
    while (l < r) {
      mid = (l+r+1)/2;
      if (V[mid][0] > X[i]) l = mid;
      else r = mid-1;
    }
    if (!V.empty() && V[l][0] > X[i]) {
      L[i] = {V[l][1], V[l][0]};
    }
    while (!V.empty()) {
      auto [u, x] = V.back();
      if (X[i] > u) V.pop_back();
      else break;
    }
    V.push_back({X[i], i});
  }
  V.clear();
  for (int i=n-1; i>=0; --i) {
    R[i] = {-1, -1};
    bl[i][0] = i;
    l = 0, r = (ll)V.size()-1;
    while (l < r) {
      mid = (l+r+1)/2;
      if (V[mid][0] > X[i]) l = mid;
      else r = mid-1;
    }
    if (!V.empty() && V[l][0] > X[i]) {
      bl[i][0] = V[l][1];
      R[i] = {V[l][1], V[l][0]};
    }
    while (!V.empty()) {
      auto [u, x] = V.back();
      if (X[i] > u) V.pop_back();
      else break;
    }
    V.push_back({X[i], i});
  }
  for (int i=0; i<n; ++i) {
    if (L[i][1] && R[i][1] == -1) jmp[i][0] = i;
    else if (L[i][1] > R[i][1]) jmp[i][0] = L[i][0];
    else jmp[i][0] = R[i][0];
  }
  for (int j=1; j<18; ++j) {
    for (int i=0; i<n; ++i) {
      bl[i][j] = bl[bl[i][j-1]][j-1];
      jmp[i][j] = jmp[jmp[i][j-1]][j-1];
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  z = query(1, 0, n-1, C, D);
  k = mx = -1;
  solve(1, 0, n-1, A, B);
  if (k == B) return -1;
  if (k == -1) k = A;
  else ++k;
  find(1, 0, n-1, k, B);
  ll f = 0;
  for (int j=17; j>=0; --j) {
    if (X[jmp[s][j]] < z) {
      if (bl[jmp[s][j]][0] < C) {
        s = jmp[s][j];
        f += (1LL<<j);
      }
    }
  }
  if (X[jmp[s][0]] < z && bl[s][0] < C) {
    s = jmp[s][0];
    ++f;
  }
  for (int j=17; j>=0; --j) {
    if (bl[s][j] < C) {
      s = bl[s][j];
      f += (1LL<<j);
    }
  }
  if (C <= bl[s][0] && bl[s][0] <= D) return f+1;
  else return -1;
}

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:85:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   85 |       auto [u, x] = V.back();
      |            ^
jumps.cpp:106:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  106 |       auto [u, x] = V.back();
      |            ^

• 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