제출 #1307697

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1307697		repmann	밀림 점프 (APIO21_jumps)	C++20	100 / 100	468 ms	47616 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
int N;
int A[200001];
int LG[200001], SP[18][200001], L[200001], R[18][200001], MAX[18][200001];
inline void Setup()
{
  for(int i = 2; i <= N; i++) LG[i] = LG[i - 1] + !(i & (i - 1));
  for(int i = 1; i <= N; i++) SP[0][i] = i;
  for(int j = 1; (1 << j) < N; j++)
  {
    for(int i = 1; (i + (1 << j) - 1) <= N; i++) SP[j][i] = (A[SP[j - 1][i]] > A[SP[j - 1][i + (1 << (j - 1))]]) ? SP[j - 1][i] : SP[j - 1][i + (1 << (j - 1))];
  }
  return;
}
inline int Get(int l, int r)
{
  int j = LG[r - l + 1];
  return (A[SP[j][l]] > A[SP[j][r - (1 << j) + 1]]) ? SP[j][l] : SP[j][r - (1 << j) + 1];
}
void init(int n, vector <int> a)
{
  N = n;
  for(int i = 1; i <= N; i++) A[i] = a[i - 1];
  Setup();
  stack <pair <int, int>> S;
  for(int i = 1; i <= N; i++)
  {
    while(S.size() && (S.top().first < A[i])) S.pop();
    if(S.size()) L[i] = S.top().second;
    S.push({A[i], i});
  }
  while(S.size()) S.pop();
  for(int i = N; i >= 1; i--)
  {
    while(S.size() && (S.top().first < A[i])) S.pop();
    if(S.size()) R[0][i] = S.top().second;
    S.push({A[i], i});
  }
  vector <int> V(N);
  for(int i = 1; i <= N; i++) V[i - 1] = N - i + 1;
  for(int x : V) for(int j = 1; j <= 17; j++) R[j][x] = R[j - 1][R[j - 1][x]];
  sort(V.begin(), V.end(), [&](int i, int j) {return A[i] > A[j];});
  for(int i = 1; i <= N; i++) MAX[0][i] = (A[L[i]] > A[R[0][i]]) ? L[i] : R[0][i];
  for(int x : V) for(int j = 1; j <= 17; j++) MAX[j][x] = MAX[j - 1][MAX[j - 1][x]];
  return;
}
int minimum_jumps(int a, int b, int c, int d)
{
  a++, b++, c++, d++;
  int ret = 0;
  a = max(L[Get(c, d)] + 1, a);
  if(a > b) return -1;
  a = Get(a, b);
  for(int j = 17; j >= 0; j--) if(MAX[j][a] && R[0][MAX[j][a]] && (R[0][MAX[j][a]] < c)) {a = MAX[j][a]; ret += 1 << j;}
  if((R[0][a] && (R[0][a] < c) && MAX[0][a] && R[0][MAX[0][a]] && (R[0][MAX[0][a]] <= d))) {a = MAX[0][a]; ret++;}
  for(int j = 17; (a < c) && (j >= 0); j--) if(R[j][a] && (R[j][a] < c)) {a = R[j][a]; ret += 1 << j;}
  return ret + 1;
}
//int main()
//{
//  int n;
//  cin >> n;
//  vector <int> h(n);
//  for(int i = 0; i < n; i++) cin >> h[i];
//  init(n, h);
//  int q, a, b, c, d;
//  cin >> q;
//  while(q--)
//  {
//    cin >> a >> b >> c >> d;
//    cout << minimum_jumps(a, b, c, d) << '\n';
//  }
//  return 0;
//}

• 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