Submission #414614

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
414614	2021-05-30 18:10:45	tatyam	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1654 ms	46288 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;
 
int N, lgN;
vector<vector<int>> rmq, low, high;
void init(int N, vector<int> H) {
    ::N = N;
    lgN = __lg(N);
    rmq.assign(lgN + 1, vector<int>(N));
    low.assign(lgN + 1, vector<int>(N, -1));
    high.assign(lgN + 1, vector<int>(N, -1));
    rmq[0] = H;
    for(int i = 0; i < lgN; i++) for(int j = 0; j + (2 << i) <= N; j++) rmq[i + 1][j] = max(rmq[i][j], rmq[i][j + (1 << i)]);
    vector<int> q;
    for(int i = 0; i < N; i++){
        while(q.size() && H[q.back()] < H[i]){
            const int j = q.back();
            q.pop_back();
            low[0][j] = i;
        }
        q.push_back(i);
    }
    for(int i = N; i--; ){
        while(q.size() && H[q.back()] < H[i]){
            const int j = q.back();
            q.pop_back();
            high[0][j] = i;
        }
        q.push_back(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