Submission #1112787

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112787		PagodePaiva	Rainforest Jumps (APIO21_jumps)	C++17	33 / 100	4041 ms	12388 KiB

jumps

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

using namespace std;

const int N = 200010;
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;

int l[N], r[N];
int n;

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);
  }
}

int dist[N];

int minimum_jumps(int a, int b, int c, int d) {
  queue <int> q;
  a++;
  b++;
  c++;
  d++;
  for(int i = 1;i <= n;i++){
    dist[i] = -1;
  }
  for(int i = a;i <= b;i++){
    dist[i] = 0;
    q.push(i);
  }
  while(!q.empty()){
    int v = q.front();
    q.pop();
    if(l[v] != -1){
      if(dist[l[v]] == -1){
        dist[l[v]] = dist[v]+1;
        q.push(l[v]);
      }
    }
    if(r[v] != -1){
      if(dist[r[v]] == -1){
        dist[r[v]] = dist[v]+1;
        q.push(r[v]);
      }
    }
  }
  int res = 1e8;
  for(int i = c;i <= d;i++){
    if(dist[i] == -1) continue;
    res = min(res, dist[i]);
  }
  return (res == 1e8 ? -1 : res);
}

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