Submission #551952

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
551952	2022-04-22 01:00:44	marsxiang5902	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1263 ms	54240 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 MN = 2e5+5, ML = 18;
int N, sptb[ML][MN], *ar = sptb[0], ainv[MN], nxL[MN], bl[ML][MN], blR[ML][MN], *nxR = blR[0];
int queMx(int l, int r){
    assert(l <= r);
    int d = __lg(r-l+1);
    return max(sptb[d][l], sptb[d][r-(1<<d)+1]);
}
void init(int _N, vector<int> _ar){
    N = _N; memcpy(ar+1, &_ar[0], N * sizeof ar[0]);
    set<int> st = {0, N+1};
    ar[0] = N+1; ar[N+1] = N+2;
    for(int i = 0; i <= N+1; i++)
        ainv[--ar[i]] = i;
    for(int val = N+1; val--; ){
        int pos = ainv[val];
        auto it = st.insert(pos).first;
        int l = *prev(it), r = *next(it);
        nxL[pos] = l;
        nxR[pos] = r;
        bl[0][pos] = ainv[max(ar[l], ar[r])];
    }
    nxL[0] = 0; nxR[0] = nxL[N+1] = nxR[N+1] = bl[0][0] = bl[0][N+1] = N+1;
    for(int l = 1; l < ML; l++)
        for(int i = 0; i <= N+1; i++){
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

jumps.cpp: In function 'void init(int, std::vector<int>)':
jumps.cpp:36:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   36 |             sptb[l][i] = max(sptb[l-1][i], sptb[l-1][i+(1<<l-1)]);
      |                                                            ~^~

• 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