Submission #1112793

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112793		PagodePaiva	Rainforest Jumps (APIO21_jumps)	C++17	23 / 100	2471 ms	91832 KiB

jumps

#include<bits/stdc++.h>
#include "jumps.h"
#define fr first
#define sc second

using namespace std;

const int N = 200010;
const int LOGN = 20;

struct Segtree{
  pair <int, int> tree[4*N];
  pair <int, int> join(pair <int, int> a, pair <int, int> b){
    return {min(a.fr, b.fr), max(a.sc, b.sc)};
  }
  void build(int node, int l, int r){
    if(l == r){
      tree[node] = {1e9, 0};
      return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    tree[node] = join(tree[2*node], tree[2*node+1]);
    return;
  }
  void update(int node, int l, int r, int pos, int val){
    if(l == r){
      tree[node] = {l, l};
      return;
    }
    int mid = (l+r)/2;
    if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
    else update(2*node+1, mid+1, r, pos, val);
    tree[node] = join(tree[2*node], tree[2*node+1]);
    return;
  }
  pair <int, int> query(int node, int l, int r, int tl, int tr){
    if(l > tr or tl > r) return {1e9, -1};
    if(l <= tl and tr <= r) return tree[node];
    int mid = (tl+tr)/2;
    return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
  }
} seg;

struct Segtree2{
  pair <int, int> tree[4*N];
  pair <int, int> join(pair <int, int> a, pair <int, int> b){
    if(a.fr > b.fr) return a;
    return b;
  }
  void build(int node, int l, int r){
    if(l == r){
      tree[node] = {0, l};
      return;
    }
    int mid = (l+r)/2;
    build(2*node, l, mid);
    build(2*node+1, mid+1, r);
    tree[node] = join(tree[2*node], tree[2*node+1]);
    return;
  }
  void update(int node, int l, int r, int pos, int val){
    if(l == r){
      tree[node] = {val, l};
      return;
    }
    int mid = (l+r)/2;
    if(l <= pos and pos <= mid) update(2*node, l, mid, pos, val);
    else update(2*node+1, mid+1, r, pos, val);
    tree[node] = join(tree[2*node], tree[2*node+1]);
    return;
  }
  pair <int, int> query(int node, int l, int r, int tl, int tr){
    if(l > tr or tl > r) return {-1, -1};
    if(l <= tl and tr <= r) return tree[node];
    int mid = (tl+tr)/2;
    return join(query(2*node, l, r, tl, mid), query(2*node+1, l, r, mid+1, tr));
  }
} seg2, alturas;

int l[N], r[N];
int lc[N], rc[N];
int pai[N][LOGN], pai2[N][LOGN];
int tin[N], tout[N];
vector <int> g[N];
int n;
int tmm;
int il[N], ir[N];
int alt[N];

void dfs(int v, int p){
  pai2[v][0] = p;
  tin[v] = tmm;
  tmm++;
  for(auto x : g[v]){
    if(x == p) continue;
    alt[x] = alt[v]+1;
    dfs(x, v);
  }
  tout[v] = tmm;
  tmm++;
}

void construct(int l = 1, int r = n){
  int t = seg2.query(1, l, r, 1, n).sc;
  il[t] = l;
  ir[t] = r;
  if(seg2.query(1, l, t-1, 1, n).first > 0){
    lc[t] = seg2.query(1, l, t-1, 1, n).sc;
    construct(l, t-1);
  }
  if(seg2.query(1, t+1, r, 1, n).fr > 0){
    rc[t] = seg2.query(1, t+1, r, 1, n).sc;
    construct(t+1, r);
  }
}

void init(int N, vector<int> h) {
  n = N;
  vector <pair <int, int>> v;
  for(int i = 0;i < n;i++){
    v.push_back({h[i], i+1});
  }
  sort(v.begin(), v.end());
  reverse(v.begin(), v.end());
  seg.build(1, 1, n);
  for(auto [val, pos] : v){
    l[pos] = r[pos] = -1;
    if(seg.query(1, 1, pos-1, 1, n).sc > 0) l[pos] = seg.query(1, 1, pos-1, 1, n).sc;
    if(seg.query(1, pos+1, n, 1, n).fr < 1e9) r[pos] = seg.query(1, pos+1, n, 1, n).fr;
    seg.update(1,1, n, pos, pos);
  }
  reverse(v.begin(), v.end());
  seg2.build(1, 1, n);
  for(auto [val, pos] : v){
    lc[pos] = rc[pos] = -1;
    seg2.update(1, 1, n, pos, val);
  }
  construct();
  int raiz = 0;
  for(int i = 1;i <= n;i++){
    if(h[i-1] == n) raiz = i;
    if(lc[i] != -1){
      g[lc[i]].push_back(i);
      g[i].push_back(lc[i]);
    }
    if(rc[i] != -1) {
      g[rc[i]].push_back(i);
      g[i].push_back(rc[i]);
    }
    //cout << lc[i] << ' ' << rc[i] << '\n';
  }
  tmm = 1;
  g[raiz].push_back(0);
  g[0].push_back(raiz);
  pai[raiz][0] = 0;
  pai2[raiz][0] = 0;
  dfs(0, 0);
  for(int i = 1;i <= n;i++){
    if(l[i] == -1 and r[i] == -1) {
      continue;
    }
    if(l[i] == -1) pai[i][0] = r[i];
    else if(r[i] == -1) pai[i][0] = l[i];
    else{
      int u = l[i], v = r[i];
      if(tin[u] <= tin[v] and tout[v] <= tout[u]){
        pai[i][0] = u;
      }
      else{
        pai[i][0] = v;
      }
    }
  }  
  alturas.build(1, 1, n);
  for(int i = 1;i <= n;i++){
    alturas.update(1, 1, n, i, alt[i]);
  }
  for(int bit = 1;bit < LOGN;bit++){
    for(int i = 1;i <= n;i++){
      pai[i][bit] = pai[pai[i][bit-1]][bit-1];
      pai2[i][bit] = pai2[pai2[i][bit-1]][bit-1];
    }
  }
  return;
}

int check(int u, int v){
  return (tin[v] <= tin[u] and tout[u] <= tout[v]);
}

int choose(int a, int b, int c){
  a = max(a, il[c]);
  int t = alturas.query(1, a, b, 1, n).sc;
  return t;
}

int minimum_jumps(int a, int b, int c, int d) {
  // a=b and c = d
  a++;
  b++;
  c++;
  d++;
  int u = choose(a,b,c), v = c;
  if(!check(u, v)){
    return -1;
  }
  int res = 0;
  for(int bit = LOGN-1;bit >= 0;bit--){
    if(check(pai[u][bit], v)){
      u = pai[u][bit];
      int t = (1<<bit);
      res += t;
    }
  }
  for(int bit = LOGN-1;bit >= 0;bit--){
    if(check(pai2[u][bit], v)){
      u = pai2[u][bit];
      int t = (1<<bit);
      res += t;
    }
  }
  return res;
}

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