Submission #478306

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
478306	2021-10-06 23:45:08	couplefire	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1541 ms	52900 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 <bits/stdc++.h>
using namespace std;
const int N = 200005;
int n, h[N], r_nxt[N], l_nxt[N], nxt[N], r_up[N][20], l_up[N][20], up[N][20];
void init(int N, vector<int> H){
    n = N;
    for(int i = 1; i<=n; ++i)
        h[i] = H[i-1];
    h[0] = h[n+1] = n+1;
    stack<int> st; st.push(0);
    for(int i = 1; i<=n; ++i){
        while(h[st.top()]<h[i]) st.pop();
        l_nxt[i] = st.top(); st.push(i);
    } l_nxt[0] = 0;
    while(st.size()) st.pop();
    st.push(n+1);
    for(int i = n; i>=1; --i){
        while(h[st.top()]<h[i]) st.pop();
        r_nxt[i] = st.top(); st.push(i);
    } r_nxt[n+1] = n+1;
    for(int i = 1; i<=n+1; ++i)
        if(!l_nxt[i]) nxt[i] = r_nxt[i];
        else if(r_nxt[i]==n+1) nxt[i] = l_nxt[i];
        else if(h[r_nxt[i]]>h[l_nxt[i]]) nxt[i] = r_nxt[i];
        else nxt[i] = l_nxt[i];
    for(int i = 0; i<=n; ++i){
        l_up[i][0] = l_nxt[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