제출 #464017

#	제출 시각UTC-0	아이디	문제	언어	결과	실행 시간	메모리
464017	2021-08-12 07:51:47	prvocislo	밀림 점프 (APIO21_jumps)	C++17	100 / 100	1764 ms	47936 KiB

jumps

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include "jumps.h"
#include <vector>
using namespace std;
const int logn = 19, maxn = 2e5+5;
//const int logn = 19, maxn = 10;
int jumpl[logn][maxn], jumpr[logn][maxn], high[logn][maxn];
int n, top, h[maxn], stk[maxn];
void init(int N, vector<int> H) 
{
  n = N, top = 0;
  for (int i = 1; i <= n; i++) h[i] = H[i - 1];
  for (int i = 1; i <= n; i++)
  {
    while (top && h[stk[top - 1]] < h[i]) jumpr[0][stk[top - 1]] = i, top--;
    if (top) jumpl[0][i] = stk[top - 1];
    stk[top++] = i;
  }
  for (int i = 1; i <= n; i++)
  {
    int l = jumpl[0][i], r = jumpr[0][i];
    if (!r || (l && r && h[l] > h[r])) high[0][i] = l;
    else high[0][i] = r;
  }
  for (int l = 1; l < logn; l++) for (int i = 1; i <= n; i++)
  {
    jumpl[l][i] = jumpl[l - 1][jumpl[l - 1][i]];
    jumpr[l][i] = jumpr[l - 1][jumpr[l - 1][i]];
    high[l][i] = high[l - 1][high[l - 1][i]];
  }
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

• 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