Submission #1063016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1063016		vjudge1	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	2020 ms	48368 KiB

jumps

#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
using namespace std;

using ll = long long;
using ld = long double;

//#define int ll
#define sz(x) ((int)(x).size())

using pii = pair<int,int>;
using tii = tuple<int,int,int>;

const int nmax = 2e5 + 5;
int toright[nmax][18], toleft[nmax][18];
int extreme[nmax][18];
int H[nmax];

int N;

void init(int N_, std::vector<int> H_) {
   N = N_;
   H_.emplace_back(1e9 + 5);
   for(int i = 0; i <= N; i++) H[i] = H_[i];
   
   vector<int> st;
   st.emplace_back(N);
   for(int i = 0; i < N; i++) {
      while(H[st.back()] < H[i]) st.pop_back();
      toleft[i][0] = st.back();
      st.emplace_back(i);
   }
   
   toleft[N][0] = N;
   for(int step = 1; step < 18; step++) for(int i = 0; i <= N; i++) toleft[i][step] = toleft[toleft[i][step - 1]][step - 1];
   
   st.clear();
   st.emplace_back(N);
   for(int i = N - 1; i >= 0; i--) {
      while(H[st.back()] < H[i]) st.pop_back();
      toright[i][0] = st.back();
      st.emplace_back(i);
   }
   
   toright[N][0] = N;
   for(int step = 1; step < 18; step++) for(int i = 0; i <= N; i++) toright[i][step] = toright[toright[i][step - 1]][step - 1];
   
   for(int i = 0; i < N; i++) {
      if(toleft[i][0] == N) extreme[i][0] = toright[i][0];
      else if(toright[i][0] == N) extreme[i][0] = toleft[i][0];
      else extreme[i][0] = (H[toleft[i][0]] > H[toright[i][0]]? toleft[i][0] : toright[i][0]);
   }
   
   extreme[N][0] = N;
   for(int step = 1; step < 18; step++) for(int i = 0; i <= N; i++) extreme[i][step] = extreme[extreme[i][step - 1]][step - 1];
}

int maxrange(int l, int r) {
   for(int i = 17; i >= 0; i--)
      if(toright[l][i] <= r) l = toright[l][i];
   return l;
}

int leftist(int B, int C, int D) {
   if(B == N) return -1;
   int cnt = 0;
   for(int i = 17; i >= 0; i--) {
      int cand = toright[B][i];
      if(cand >= C) continue;
      B = cand;
      cnt += (1 << i);
   }
   if(toright[B][0] > D) return -1;
   return cnt + 1;
}

int minimum_jumps(int A, int B, int C, int D) {
   for(int i = 17; i >= 0; i--) {
      int cand = toleft[B][i];
      //cerr << B << " -> " << cand << '\n';
      if(cand == N) continue;
      if(cand < A) continue;
      if(toright[cand][0] > D) continue;
      if(toright[cand][0] >= C) return 1;
      B = cand;
   } 
   
   cerr << B << '\n';
   
   int mx = maxrange(B + 1, C);
   for(int i = 17; i >= 0; i--) {
      if(H[toright[C][i]] < H[mx]) C = toright[C][i];
   }
   if(H[C] < H[mx]) C = toright[C][0];
   if(C > D) return -1;
   
   int delta = 0;
   for(int i = 17; i >= 0; i--)
      if(H[extreme[B][i]] < H[C]) delta += (1 << i), B = extreme[B][i];
   
   cerr << B << ' ' << delta << '\t' << extreme[B][0] << '\n';;   
   
   if(extreme[B][0] > D) return -1;
   if(extreme[B][0] >= C) return delta + 1;
   
   //cerr << "muie\n";
   
   int sol1 = leftist(B, C, D), sol2 = leftist(extreme[B][0], C, D);
   //cerr << sol1 << ' ' << sol2 << '\n';
   if(sol2 != -1) sol1 = (sol1 == -1? delta + sol2 + 1 : delta + min(sol1, sol2 + 1));
   else sol1 = (sol1 == -1? sol1 : sol1 + delta);
   return sol1;

}


/**
      Töte es durch genaue Untersuchung\Töte es kann es nur noch schlimmer machen\Es lässt es irgendwie atmen
--
*/ 

• 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