Submission #1052593

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052593		Zbyszek99	Rainforest Jumps (APIO21_jumps)	C++17	81 / 100	4006 ms	50448 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;

const int wiel = 1024*512-1;
pii drzewo[wiel];

pii query_t(int akt, int p1, int p2, int s1, int s2)
{
  if(p2 < s1 || p1 > s2) return {-1,-1};
  if(p1 >= s1 && p2 <= s2) return drzewo[akt-1];
  return max(query_t(akt*2,p1,(p1+p2)/2,s1,s2),query_t(akt*2+1,(p1+p2)/2+1,p2,s1,s2));
}

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;

void init(int N, vector<int> H) 
{
  n = N;
  rep(i,n) h[i] = H[i];
  rep(i,n) drzewo[wiel/2+i] = {h[i],i};
  for(int i = wiel/2-1; i >= 0; i--)
  {
    drzewo[i] = max(drzewo[i*2+1],drzewo[i*2+2]);
  }
  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 subtask5_f(int A, int B, int C, int D)
{
  cerr << A << " " << B << " " << C << " " << D << " ABCD\n";
  if(A == C) return 0;
    int pocz = 0;
    int kon = 200000;
    int new_v = A;
    int bit = 19;
    int ans = 0;
    while(bit >= 0)
    {
      if(h[jump[new_v][bit]] >= h[C])
      {
        
      }
      else 
      {
        new_v = jump[new_v][bit];
        ans += (1 << bit);
      }
      bit--;
    }
    int v = new_v;
    cerr << v << " " << ans << " v\n";
    if(prev_[v] == C || next_[v] == C) return ans+1;
    bit = 19;
    while(bit >= 0)
    {
      if(h[jump2[v][bit]] >= h[C])
      {
        
      }
      else 
      {
        v = jump2[v][bit];
        ans += (1 << bit);
      }
      bit--;
    }
    cerr << v << " " << ans << " v\n";    
    if(h[v] > h[C]) return -1;
    if(prev_[v] == C || next_[v] == C) return ans+1;
    return -1;
}

int minimum_jumps(int A, int B, int C, int D) {
  bool subtask5 = A == B && C == D;
  bool subtask6 = A != B && C == D;
  //subtask5 = false;
  if(!subtask1 && !subtask5 && !subtask6)
  {
    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(subtask5)
  {
    return subtask5_f(A,B,C,D);    
  }
  else if(subtask6)
  {
    if(C >= A && C <= B) return 0;
    if(C > B)
    {
      int pocz = A;
      int kon = B;
      int ans = 0;
      while(pocz <= kon)
      {
        int srod = (pocz+kon)/2;
        if(query_t(1,0,wiel/2,srod,B).ff < h[C])
        {
          ans =  srod;
          kon = srod-1;
        }
        else pocz = srod+1;
      }
      ans = query_t(1,0,wiel/2,ans,B).ss;
      if(ans == -1) return -1;
      return subtask5_f(ans,ans,C,D);
    }
    else
    {
      int pocz = A;
      int kon = B;
      int ans = 0;
      while(pocz <= kon)
      {
        int srod = (pocz+kon)/2;
        if(query_t(1,0,wiel/2,A,srod).ff < h[C])
        {
          ans =  srod;
          pocz = srod+1;
        }
        else kon = srod-1;
      }
      cerr << ans << " " << query_t(1,0,wiel/2,A,ans).ff << " " << h[C] << " ans\n";
      ans = query_t(1,0,wiel/2,A,ans).ss;
      if(ans == -1) return -1;
      return subtask5_f(ans,ans,C,D);
      
    }
  }
  return 0;
}

Compilation message (stderr)

jumps.cpp: In function 'int subtask5_f(int, int, int, int)':
jumps.cpp:110:9: warning: unused variable 'pocz' [-Wunused-variable]
  110 |     int pocz = 0;
      |         ^~~~
jumps.cpp:111:9: warning: unused variable 'kon' [-Wunused-variable]
  111 |     int kon = 200000;
      |         ^~~

• 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: 0 / 19