Submission #1052554

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052554		Zbyszek99	Rainforest Jumps (APIO21_jumps)	C++17	60 / 100	4019 ms	43648 KiB

jumps

#include "jumps.h"
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define size(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace std;
//mt19937 mt;void random(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll rand(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;

int next_[200001];
int prev_[200001];
int jump[200001][20];
int jump2[200001][20];
int h[200001];
int odl[200001];
bitset<200001> odw;
int n;
bool subtask1 = true;

int skok(int v, int k)
{
  rep(bit,20)
  {
    if(k & (1 << bit)) v = jump[v][bit];
  }
  return v;
}

int skok2(int v, int k)
{
  rep(bit,20)
  {
    if(k & (1 << bit)) v = jump2[v][bit];
  }
  return v;
}

void init(int N, vector<int> H) 
{
  n = N;
  rep(i,n) h[i] = H[i];
  vector<pii> q;
  rep(i,n)
  {
    if(i != 0)
    {
      if(h[i] < h[i-1]) subtask1 = false;
    }
    while(size(q) > 0 && h[i] > q.back().ff) q.pop_back();
    if(size(q) != 0)
    {
      prev_[i] = q.back().ss;
    } 
    else prev_[i] = i;
    q.pb({h[i],i});
  }
  q = {};
  for(int i = n-1; i >= 0; i--)
  {
    while(size(q) > 0 && h[i] > q.back().ff) q.pop_back();
    if(size(q) != 0)
    {
      next_[i] = q.back().ss;
    } 
    else next_[i] = i;
    q.pb({h[i],i});
  }
  rep(i,n)
  {
    if(h[next_[i]] < h[prev_[i]])
    {
      swap(next_[i],prev_[i]);
    }
    cerr << i << " " << next_[i] << " " << prev_[i] << " nx prv\n";
    jump[i][0] = next_[i];
    if(prev_[i] != i) jump2[i][0] = prev_[i];
    else jump2[i][0] = next_[i];
  }
  rep2(bit,1,19)
  {
    rep(i,n)
    {
      jump[i][bit] = jump[jump[i][bit-1]][bit-1];
    }
  }
  rep2(bit,1,19)
  {
    rep(i,n)
    {
      jump2[i][bit] = jump2[jump2[i][bit-1]][bit-1];
    }
  }
}

int minimum_jumps(int A, int B, int C, int D) {
  bool subtask5 = A == B && C == D;
  //subtask5 = false;
  if(!subtask1 && !subtask5)
  {
    rep(i,n) odl[i] = 1e9;
    rep(i,n) odw[i] = 0;
    rep2(i,A,B) odl[i] = 0;
    queue<int> kol; 
    rep2(i,A,B) kol.push(i);
    int wyn = 1e9;
    while(!kol.empty())
    {
      int t = kol.front();
      kol.pop();
      if(odw[t] == 1) continue;
      if(t >= C && t <= D) wyn = min(wyn,odl[t]);
      odl[next_[t]] = min(odl[next_[t]],odl[t]+1);
      odl[prev_[t]] = min(odl[prev_[t]],odl[t]+1);
      kol.push(next_[t]);
      kol.push(prev_[t]);
      odw[t] = 1;
    }
    if(wyn == 1e9) return -1;
    return wyn;
  }
  else if(subtask1)
  {
    int ans = 1e9;
    if(C-B >= 0) ans = C-B;
    if(C <= B) ans = 0;
    if(ans == 1e9) return -1;
    return ans;    
  }
  else
  {
    if(A == C) return 0;
    int pocz = 0;
    int kon = 200000;
    int ans = 0;
    while(pocz <= kon)
    {
      int srod = (pocz+kon)/2;
      int new_v = skok(A,srod);
      if(h[new_v] >= h[C])
      {
        kon = srod-1;
      }
      else
      {
        ans = srod;
        pocz = srod+1;
      }
    }
    int v = skok(A,ans);
    cerr << v << " " << ans << " v\n";
    if(prev_[v] == C || next_[v] == C) return ans+1;
    int ans2 = ans;
    pocz = 0;
    kon = 200000;
    ans = 0;
    while(pocz <= kon)
    {
      int srod = (pocz+kon)/2;
      int new_v = skok2(v,srod);
      if(h[new_v] >= h[C])
      {
        kon = srod-1;
      }
      else
      {
        ans = srod;
        pocz = srod+1;
      }
    }
    v = skok2(v,ans);
    cerr << v << " " << ans << " v\n";    
    if(h[v] > h[C]) return -1;
    if(prev_[v] == C || next_[v] == C) return ans+1+ans2;
    return -1;
  }
  return 0;
}

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