oj.uz

Submission #691621

# Submission time Handle Problem Language Result Execution time Memory
691621 2023-01-31T10:43:11 Z Dan4Life Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1097 ms 48664 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
const int mxN = (int)2e5+10;
const int mxLg = 19;

stack<pair<int,int>> S;
int n, pr[mxN], nx[mxN];
int l[mxLg][mxN], r[mxLg][mxN], hi[mxLg][mxN];

void calc(int jmp[][mxN]){
    for(int i = 1; i < mxLg; i++)
        for(int j = 1; j <= n; j++)
            jmp[i][j] = jmp[i-1][jmp[i-1][j]];
}

void init(int N, vector<int> a) {
    n = N; a.insert(a.begin(),-1);
    for(int i = 1; i <= n; i++){
        while(!S.empty() and S.top().fi<a[i]) S.pop();
        if(!S.empty()) pr[i] = S.top().se;
        S.push({a[i],i});
    }
    while(!S.empty()) S.pop();
    for(int i = n; i>=1; i--){
        while(!S.empty() and S.top().fi<a[i]) S.pop();
        if(!S.empty()) nx[i] = S.top().se;
        S.push({a[i],i});
    }
    for(int i = 1; i <= n; i++){
        l[0][i]=pr[i], r[0][i]=nx[i];
        if(l[0][i] and r[0][i])
            hi[0][i] = (a[pr[i]]<a[nx[i]]?nx[i]:pr[i]);
    }
    calc(l), calc(r), calc(hi);
}

int get_path(int *x, int y, int z, int jmp[][mxN], int rx=1, int tot=0){
    for(int i = mxLg-1; i >= 0; i--)
        if(jmp[i][*x]>=rx and jmp[i][*x]<y)
            if(nx[jmp[i][*x]] and nx[jmp[i][*x]]<=z)
                *x = jmp[i][*x], tot+=(1<<i);
    return tot;
}

int minimum_jumps(int A, int B, int C, int D) {
    A++,B++,C++,D++;
    int x = B; get_path(&x,C,D,l,A);
    if(nx[x]>=C and nx[x]<=D) return 1;
    int ans = get_path(&x,C,C-1,hi);
    if(nx[x]>=C and nx[x]<=D) return ans+2;
    ans+=get_path(&x,C,D,r);
    return (nx[x]>=C and nx[x]<=D)?ans+1:-1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 138 ms 38576 KB Output is correct
4 Correct 1037 ms 48056 KB Output is correct
5 Correct 946 ms 24620 KB Output is correct
6 Correct 1031 ms 48036 KB Output is correct
7 Correct 886 ms 33196 KB Output is correct
8 Correct 1097 ms 48036 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 0 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Incorrect 2 ms 592 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 0 ms 592 KB Output is correct
5 Correct 2 ms 592 KB Output is correct
6 Incorrect 2 ms 592 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 592 KB Output is correct
2 Correct 0 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Correct 1 ms 624 KB Output is correct
5 Correct 53 ms 38952 KB Output is correct
6 Correct 53 ms 48016 KB Output is correct
7 Correct 34 ms 25008 KB Output is correct
8 Correct 60 ms 47928 KB Output is correct
9 Correct 9 ms 7844 KB Output is correct
10 Correct 68 ms 47916 KB Output is correct
11 Correct 52 ms 48264 KB Output is correct
12 Correct 49 ms 48664 KB Output is correct
13 Incorrect 47 ms 48020 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Incorrect 217 ms 22308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 1 ms 592 KB Output is correct
4 Incorrect 217 ms 22308 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 592 KB Output is correct
2 Correct 1 ms 592 KB Output is correct
3 Correct 138 ms 38576 KB Output is correct
4 Correct 1037 ms 48056 KB Output is correct
5 Correct 946 ms 24620 KB Output is correct
6 Correct 1031 ms 48036 KB Output is correct
7 Correct 886 ms 33196 KB Output is correct
8 Correct 1097 ms 48036 KB Output is correct
9 Correct 0 ms 592 KB Output is correct
10 Correct 1 ms 592 KB Output is correct
11 Correct 1 ms 592 KB Output is correct
12 Correct 0 ms 592 KB Output is correct
13 Correct 2 ms 592 KB Output is correct
14 Incorrect 2 ms 592 KB Output isn't correct
15 Halted 0 ms 0 KB -