Submission #837378

#	Time	Username	Problem	Language	Result	Execution time	Memory
837378		mychecksedad	Rainforest Jumps (APIO21_jumps)	C++17	0 / 100	202 ms	81504 KiB

jumps

#include "jumps.h"
#include<bits/stdc++.h>
#define ll long long int
#define mod1 (1000000000+7)
#define mod (998244353)
#define pb push_back
#define all(x) x.begin(), x.end()
#define en cout << '\n'
using namespace std;
const int N = 200000+10, K = 20;

int n, dp[N][K], R[N], A[N], up[N][K];
vector<int> T[4*N];
void build(int l, int r, int k){
  if(l == r){
    T[k] = {R[l]};
    return;
  }
  int m = l+r>>1;
  build(l, m, k<<1);
  build(m+1, r, k<<1|1);
  merge(all(T[k<<1]), all(T[k<<1|1]), back_inserter(T[k]));
}

int get_max(int l, int r, int ql, int qr, int k, int X, int Y){
  if(ql > r || l > qr) return -1;
  if(ql <= l && r <= qr){
    int pos = upper_bound(all(T[k]), Y) - T[k].begin();
    if(pos > 0){
      int val = T[k][pos - 1];
      return (val >= X ? val : -1);
    }
    return -1;
  }
  int m = l+r>>1;
  return max(get_max(l, m, ql, qr, k<<1, X, Y), get_max(m+1, r, ql, qr, k<<1|1, X, Y));
}



int get(int l, int r){
  int k = int(log2(r-l+1));
  if(A[dp[l][k]] >= A[dp[r - (1<<k) + 1][k]])
    return dp[l][k];
  return dp[r - (1<<k) + 1][k];
}

void init(int _N, std::vector<int> H) {
  n = _N;
  for(int i = 1; i <= n; ++i) A[i] = H[i - 1];
  for(int i = 1; i <= n; ++i) dp[i][0] = i;
  for(int j = 1; j < K; ++j)
    for(int i = 1; i + (1<<j) <= n + 1; ++i){
      if(A[dp[i][j - 1]] >= A[dp[i+(1<<(j-1))][j - 1]])
        dp[i][j] = dp[i][j - 1];
      else
        dp[i][j] = dp[i+(1<<(j-1))][j - 1];
    }
  R[n] = n + 1;
  deque<int> q;
  q.pb(n);
  for(int i = n - 1; i >= 1; --i){
    while(!q.empty() && A[q.front()] <= A[i]) q.pop_front();
    if(q.empty()) R[i] = n + 1;
    else R[i] = q.front();
    q.push_front(i);
  }
  build(1, n, 1);
  R[n + 1] = n + 1;
  for(int i = 1; i <= n + 1; ++i) up[i][0] = R[i];
  for(int j = 1; j < K; ++j)
    for(int i = 1; i <= n + 1; ++i) up[i][j] = up[up[i][j - 1]][j - 1];
}

int minimum_jumps(int A, int B, int C, int D) {
  A++, B++, C++, D++;
  int ans = mod, M = 0;
  if(B < C - 1){
    M = get(B+1, C-1);
    int v = M, co = 0;
    for(int j = K - 1; j >= 0; --j){
      if(up[v][j] <= D)
        v = up[v][j], co++;
      if(v >= C) break;
    }
    if(v >= C){
      int p = get_max(1, n, A, B, 1, B+1, M);
      if(p != -1){
        co++;
        for(int j = K - 1; j >= 0; --j){
          if(up[p][j] <= M)
            p = up[p][j], co++;
        }
        ans = co;
      }
    }
  }
  int co = 1;
  int p = get_max(1, n, A, B, 1, M + 1, D);
  if(p != -1){
	  for(int j = K - 1; j >= 0; --j){
	    if(p >= C) break;
	    if(up[p][j] <= D)
	      p = up[p][j], co++;
	  }
	  ans = min(ans, co);
  }
  return (ans==mod?-1:ans);
}

Compilation message (stderr)

jumps.cpp: In function 'void build(int, int, int)':
jumps.cpp:19:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   19 |   int m = l+r>>1;
      |           ~^~
jumps.cpp: In function 'int get_max(int, int, int, int, int, int, int)':
jumps.cpp:35:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   35 |   int m = l+r>>1;
      |           ~^~

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