Submission #956299

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
956299	2024-04-01 14:26:28	MrBrionix	Rainforest Jumps (APIO21_jumps)	C++17	100 / 100	1008 ms	98488 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 MAXN = 200'005, LOGN = 20;
pair<int,int> succl[MAXN][LOGN],succr[MAXN][LOGN],succ[MAXN][LOGN];
vector<int> h;
void init(int N,vector<int> H){
    
    h=H;
    h.insert(h.begin(),0);
    
    stack<pair<int,int>> ds;
    ds.push({MAXN,0});
    succl[0][0]=ds.top();
    
    for(int i=0;i<N;i++){
        while(ds.top().first<H[i])ds.pop();
        succl[i+1][0]=ds.top();
        ds.push({H[i],i+1});
    }
    succl[N+1][0]={MAXN,0};
    
    while(!ds.empty())ds.pop();
    ds.push({MAXN,N+1});
    succr[N+1][0]=ds.top();
    
    for(int i=N-1;i>=0;i--){
        while(ds.top().first<H[i])ds.pop();
        succr[i+1][0]=ds.top();
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
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