Submission #1186488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186488		Hanksburger	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1411 ms	55224 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
int h[200005], l[200005], r[200005], good[20][200005], bad[20][200005], n;
struct node
{
  node *lc, *rc;
  int l, r;
  pair<int, int> val;
  node(int l, int r) : lc(0), rc(0), l(l), r(r), val({0, 0}) {}
} *root;
void build(node *i)
{
  if (i->l==i->r)
  {
    i->val={h[i->l], i->l};
    return;
  }
  int mid=(i->l+i->r)/2;
  i->lc=new node(i->l, mid);
  i->rc=new node(mid+1, i->r);
  build(i->lc);
  build(i->rc);
  i->val=max(i->lc->val, i->rc->val);
}
pair<int, int> query(node *i, int ql, int qr)
{
  if (ql<=i->l && i->r<=qr)
    return i->val;
  int mid=(i->l+i->r)/2;
  pair<int, int> ans={0, 0};
  if (i->l<=qr && ql<=mid)
    ans=max(ans, query(i->lc, ql, qr));
  if (mid<qr && ql<=i->r)
    ans=max(ans, query(i->rc, ql, qr));
  return ans;
}
void init(int N, vector<int> H)
{
  n=N;
  h[0]=h[n+1]=1e9;
  for (int i=1; i<=n; i++)
    h[i]=H[i-1];
  stack<int> q;
  q.push(0);
  for (int i=1; i<=n; i++)
  {
    while (h[q.top()]<h[i])
      q.pop();
    l[i]=q.top();
    q.push(i);
  }
  while (q.size())
    q.pop();
  q.push(n+1);
  for (int i=n; i; i--)
  {
    while (h[q.top()]<h[i])
      q.pop();
    r[i]=q.top();
    q.push(i);
  }
  good[0][n+1]=bad[0][n+1]=n+1;
  for (int i=1; i<=n; i++)
  {
    good[0][i]=h[l[i]]>h[r[i]]?l[i]:r[i];
    bad[0][i]=h[l[i]]<h[r[i]]?l[i]:r[i];
  }
  for (int i=1; i<20; i++)
  {
    for (int j=0; j<=n+1; j++)
    {
      good[i][j]=good[i-1][good[i-1][j]];
      bad[i][j]=bad[i-1][bad[i-1][j]];
    }
  }
  root=new node(1, n);
  build(root);
}
int calc(int u, int v)
{
  int ans=0;
  for (int i=19; i>=0; i--)
  {
    if (h[good[i][u]]<=h[v])
    {
      u=good[i][u];
      ans+=1<<i;
    }
  }
  for (int i=19; i>=0; i--)
  {
    if (h[bad[i][u]]<=h[v])
    {
      u=bad[i][u];
      ans+=1<<i;
    }
  }
  if (u==v)
    return ans;
  return -1;
}
int minimum_jumps(int a, int b, int c, int d)
{
  a++, b++, c++, d++;
  pair<int, int> ans1=query(root, c, d);
  int l=a, r=b+1;
  while (l<r)
  {
    int mid=(l+r)/2;
    pair<int, int> ans2=query(root, mid, b);
    if (ans2.first>ans1.first)
      l=mid+1;
    else
      r=mid;
  }
  if (l==b+1)
    return -1;
  pair<int, int> ans2=query(root, l, b);
  pair<int, int> ans4=(b+2<=c)?query(root, b+1, c-1):make_pair(0, 0);
  int ll=c, rr=d;
  while (ll<rr)
  {
    int mid=(ll+rr)/2;
    pair<int, int> ans3=query(root, c, mid);
    if (max(ans2.first, ans4.first)<ans3.first)
      rr=mid;
    else
      ll=mid+1;
  }
  pair<int, int> ans3=query(root, c, ll);
  int res=calc(ans2.second, ans3.second);
  if (l==a)
  {
    if (ans2.first>ans4.first)
      return 1;
    int ans=0, u=ans2.second;
    for (int i=19; i>=0; i--)
    {
      if (h[good[i][u]]<ans4.first)
      {
        u=good[i][u];
        ans+=1<<i;
      }
    }
    u=good[0][u];
    if (h[u]<ans1.first)
    {
      ans+=2;
      if (res==-1)
        res=ans;
      else
        res=min(res, ans);
    }
  }
  return res;
}

• 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