Submission #919207

#	Time	Username	Problem	Language	Result	Execution time	Memory
919207		hariaakas646	Rainforest Jumps (APIO21_jumps)	C++14	48 / 100	1004 ms	65624 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
 
using namespace std;
 
#define scd(t) scanf("%d", &t)
#define sclld(t) scanf("%lld", &t)
#define forr(i, l, r) for(int i=l; i<r; i++)
#define frange(i, l) forr(i, 0, l)
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define all(x) x.begin(), x.end()
 
typedef vector<int> vi;
typedef pair<int, int> pii;
typedef vector<pii> vii;
typedef long long lli;
typedef vector<vi> vvi;
typedef vector<lli> vll;
typedef vector<bool> vb;
typedef set<int> seti;
typedef multiset<int> mseti;

template <class T>
struct SegTree
{
    int size = 1, n;
    vector<T> segtree;
    vector<T> vec;

    T def; // Assign a value

    void init(int l, T defv)
    {
        n = l;
        def = defv;

        while (size < n)
            size *= 2;

        segtree.assign(2 * size, def);
        vec.assign(size, def);
    }

    T operation(T x, T y)
    {
        return max(x, y); // Any required operation
    }

    void recalculate(int x)
    {
        segtree[x] = operation(segtree[2 * x + 1], segtree[2 * x + 2]);
    }

    void build(int x, int l, int r)
    {
        if (l == r)
        {
            segtree[x] = vec[l];
            return;
        }
        int mid = (l + r) / 2;
        build(2 * x + 1, l, mid);
        build(2 * x + 2, mid + 1, r);
        recalculate(x);
    }

    void build()
    {
        build(0, 0, size - 1);
    }

    void set(int id, T val)
    {
        vec[id] = val;
    }

    void update(int x, int l, int r, int id, T val)
    {
        if (l == r)
        {
            segtree[x] = val;
            return;
        }
        int mid = (l + r) / 2;
        if (id <= mid)
        {
            update(2 * x + 1, l, mid, id, val);
        }
        else
        {
            update(2 * x + 2, mid + 1, r, id, val);
        }
        recalculate(x);
    }

    void update(int id, T val)
    {
        update(0, 0, size - 1, id, val);
    }

    T query(int x, int l, int r, int lx, int rx)
    {
        if (lx > r || rx < l)
        {
            return def;
        }
        if (lx <= l && r <= rx)
        {
            return segtree[x];
        }
        int mid = (l + r) / 2;
        T v1 = query(2 * x + 1, l, mid, lx, rx);
        T v2 = query(2 * x + 2, mid + 1, r, lx, rx);
        return operation(v1, v2);
    }

    T query(int lx, int rx)
    {
      if(lx > rx) return def;
        return query(0, 0, size - 1, lx, rx);
    }
};


vvi graph;
int n;
vvi lifti, lifta, rgt;
vii mi, ma;
vi hgt;
SegTree<pair<int, int>> tree;

int lift(int x, int h, int pos, int d) {
  int c = 0;
  for(int i=19; i>=0; i--) {
    int xt1 = lifta[i][x];
    int xt2 = lifti[i][x];
    if(hgt[xt1] < h && xt1 < pos && xt2 < pos) {
      x = xt1;
      c+=(1<<i);
    }
  }

  for(int i=19; i>=0; i--) {
    int xt = rgt[i][x];
    if(hgt[xt] < h && xt < pos) {
      x = xt;
      c += (1<<i);
    }
  }
  if(pos <= rgt[0][x] && rgt[0][x] <= d) return c + 1;
  else return -1;
}

void init(int N, std::vector<int> h) {
  n = N;
  graph = vvi(n);
  hgt = h;
  deque<int> dq;
  mi = vii(n, mp(2e9, -1));
  ma = vii(n, mp(-1, -1));
  frange(i, n) {
    while(dq.size() && h[i] >= h[dq.back()]) dq.pop_back();
    if(dq.size()) {
      mi[i] = mp(h[dq.back()], dq.back());
      ma[i] = mp(h[dq.back()], dq.back());
    }
    dq.pb(i);
  }

  dq = {};

  rgt = vvi(20, vi(n));

  for(int i=n-1; i>=0; i--) {
    while(dq.size() && h[i] >= h[dq.back()]) dq.pop_back();
    if(dq.size()) {
      pii p = mp(h[dq.back()], dq.back());
      rgt[0][i] = p.s;
      if(p > ma[i]) ma[i] = p;
      if(p < mi[i]) mi[i] = p;
    }
    else rgt[0][i] = i;
    dq.pb(i);
  }

  
  tree.init(n, mp(0, -1));

  frange(i, n) tree.set(i, mp(h[i], i));

  tree.build();

  lifti = lifta = vvi(20, vi(n));

  frange(i, n) {
    if(mi[i].s != -1) lifti[0][i] = mi[i].s;
    else lifti[0][i] = i;
    if(ma[i].s != -1) lifta[0][i] = ma[i].s;
    else lifta[0][i] = i;
  }

  forr(i, 1, 20) {
    frange(j, n) {
      lifti[i][j] = lifti[i-1][lifti[i-1][j]];
      lifta[i][j] = lifta[i-1][lifta[i-1][j]];
      rgt[i][j] = rgt[i-1][rgt[i-1][j]];
    }
  }

}

int minimum_jumps(int a, int b, int c, int d) {

  // queue<pii> q;
  // forr(i, A, B+1) q.push(mp(i, 0));
  // vb vis(n);

  // while(q.size()) {
  //   auto p = q.front();
  //   q.pop();

  //   if(C <= p.f && p.f <= D) return p.s;
  //   if(vis[p.f]) continue;
  //   vis[p.f] = true;

  //   for(auto e : graph[p.f]) {
  //     q.push(mp(e, p.s+1));
  //   }
  // }

  // if(d < a)
  //   return -1;
  // else return max(0, c - b);

  pii v = tree.query(c, d);
  
  if(ma[v.s].s < v.s && ma[v.s].s != -1) {
    pii p = tree.query(max(a, ma[v.s].s+1), b);
    if(p.s == -1) return -1;
    return lift(p.s, hgt[v.s], c, d);
  }
  else if(mi[v.s].s < v.s && mi[v.s].s != -1) {
    pii p = tree.query(max(a, mi[v.s].s+1), b);
    if(p.s == -1) return -1;
    return lift(p.s, hgt[v.s], c, d);
  }
  else {
    pii p = tree.query(a, b);
    // printf("%d\n", p.s);
    if(p.s == -1) return -1;
    return lift(p.s, hgt[v.s], c, d);
  }
  
}

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