Submission #1052696

#	Time	Username	Problem	Language	Result	Execution time	Memory
1052696		Zbyszek99	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	3257 ms	49092 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(s1 > s2) return {-1,-1};
  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 n;
bool subtask1 = true;

void init(int N, vector<int> H) 
{
  h[n] = 1e9;
  n = N;
  rep(i,n) h[i] = H[i];
  rep(i,n) drzewo[wiel/2+i] = {h[i],i};
  rep2(i,wiel/2 +n,wiel-1) drzewo[i] = {-1,-1};
  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] = n;
    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] = n;
    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];
  }
  jump[n][0] = n;
  jump2[n][0] = n;
  rep2(bit,1,19)
  {
    rep(i,n+1)
    {
      jump[i][bit] = jump[jump[i][bit-1]][bit-1];
    }
  }
  rep2(bit,1,19)
  {
    rep(i,n+1)
    {
      jump2[i][bit] = jump2[jump2[i][bit-1]][bit-1];
    }
  }
  h[n] = 1e9;
}

int minimum_jumps(int A, int B, int C, int D) {
    if(A <= C && C <= B) return 0;
    if(A <= D && D <= B) return 0;
    if(C <= A && A <= D) return 0;
    if(C <= B && B <= D) return 0;
    
    int maxsrod = query_t(1,0,wiel/2,B+1,C-1).ff;
    if(A > C) maxsrod = query_t(1,0,wiel/2,D+1,A-1).ff;
    int maxkon = query_t(1,0,wiel/2,C,D).ff;
    if(maxkon < maxsrod) return -1;
    cerr << maxsrod << " maxsrod\n";
   // if(A < C) if(maxsrod > query_t(1,0,wiel/2,0,B).ff) return -1;
   // else if(maxsrod > query_t(1,0,wiel/2,A,n-1).ff) return -1;
    
    int start = A;
    int domh = h[C];
    if(C > B)
    {
      int pocz = A;
      int kon = B;
      start = B;
      while(pocz <= kon)
      {
        int srod = (pocz+kon)/2;
        if(query_t(1,0,wiel/2,srod,B).ff < maxkon)
        {
          start =  srod;
          kon = srod-1;
        }
        else pocz = srod+1;
      }
      start = query_t(1,0,wiel/2,start,B).ss;
      if(start == -1) return -1;
    }
    else
    {
      domh = h[D];
      int pocz = A;
      int kon = B;
      start = A;
      while(pocz <= kon)
      {
      
        int srod = (pocz+kon)/2;
        if(query_t(1,0,wiel/2,A,srod).ff < maxkon)
        {
          start =  srod;
          pocz = srod+1;
        }
        else kon = srod-1;
      }
      //cerr << start << " " << query_t(1,0,wiel/2,A,start).ff << " " << h[C] << " ans\n";
      start = query_t(1,0,wiel/2,A,start).ss;
      if(start == -1) return -1; 
    }
    int ans = 0;
    cerr << start << " start\n";
    if(h[start] > maxkon) return -1;
    for(int bit = 19; bit >= 0; bit--)
    {
      if(h[jump[start][bit]] <= maxsrod)
      {
        start = jump[start][bit];
        ans += (1 << bit);
      }
    }
    if(h[jump[start][0]] <= maxkon && h[start] < maxsrod && maxsrod != -1)
    {
      start = jump[start][0];
      ans++;
    }
    for(int bit = 19; bit >= 0; bit--)
    {
      if(h[jump2[start][bit]] <= maxsrod)
      {
        start = jump2[start][bit];
        ans += (1 << bit);
      }
    }
    if(A < C && start >= C) return ans;
    if(A > C && start <= D) return ans;
    cerr << h[start] << " "<< start << " " << ans << " " << jump[start][0] << " " << jump2[start][0]<< " start\n";
    for(int bit = 19; bit >= 0; bit--)
    {
      if(h[jump[start][bit]] <= domh)
      {
        start = jump[start][bit];
        ans += (1 << bit);
      }
    }
    if(h[start] == domh) return ans;
    cerr << h[start] << " "<< start << " " << ans << " " << jump[start][0] << " " << jump2[start][0]<< " start\n";
    for(int bit = 19; bit >= 0; bit--)
    {
      if(h[jump2[start][bit]] < domh)
      {
        start = jump2[start][bit];
        ans += (1 << bit);
      }
    }
    cerr << start << " " << ans << " start\n";
    return ans+1;
}

• 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