oj.uz

Submission #963605

# Submission time Handle Problem Language Result Execution time Memory
963605 2024-04-15T11:36:24 Z socpite Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 797 ms 46544 KB 
#include<bits/stdc++.h>
using namespace std;

const int maxn = 2e5+5;
const int lg = 18;

int n;

int sp_left[lg][maxn], sp_both[lg][maxn], sp_right[lg][maxn];
int l[maxn], r[maxn];

void init(int N, vector<int> H){
	n = N;
    stack<int> stk;
    for(int i = 0; i < N; i++){
        while(!stk.empty() && H[stk.top()] < H[i])stk.pop();
        if(stk.empty())l[i] = sp_left[0][i] = -1;
        else l[i] = sp_left[0][i] = stk.top();
        stk.push(i);
    }
    while(!stk.empty())stk.pop();
    for(int i = N-1; i >= 0; i--){
        while(!stk.empty() && H[stk.top()] < H[i])stk.pop();
        if(stk.empty())r[i] = sp_right[0][i] = N;
        else r[i] = sp_right[0][i] = stk.top();
        stk.push(i);
        if(l[i] == -1 && r[i] == N)sp_both[0][i] = -1;
        else if(l[i] == -1 || (r[i] != N && H[r[i]] > H[r[i]]))sp_both[0][i] = r[i];
        else sp_both[0][i] = l[i];
    }
    for(int i = 1; i < lg; i++){
        for(int j = 0; j < N; j++){
            if(sp_left[i-1][j] == -1)sp_left[i][j] = -1;
            else sp_left[i][j] = sp_left[i-1][sp_left[i-1][j]];
            if(sp_both[i-1][j] == -1)sp_both[i][j] = -1;
            else sp_both[i][j] = sp_both[i-1][sp_both[i-1][j]];
            if(sp_right[i-1][j] == N)sp_right[i][j] = N;
            else sp_right[i][j] = sp_right[i-1][sp_right[i-1][j]];
        }
    }
}

int minimum_jumps(int A, int B, int C, int D){
    if(r[B] > D)return -1;
    for(int i = lg-1; i >= 0; i--){
        if(sp_left[i][B] < A || r[sp_left[i][B]] > D)continue;
		B = sp_left[i][B];
    }
	// r[B] <= D
	int res = 0;
	for(int i = lg-1; i >= 0; i--){
		if(sp_both[i][B] == -1 || r[sp_both[i][B]] > C)continue;
		// cout << i << " " << sp_both[i][B] << endl;
		res += (1<<i);
		B = sp_both[i][B];
	}
	for(int i = lg-1; i >= 0; i--){
		if(sp_right[i][B] == n || r[sp_right[i][B]] > C)continue;
		res += (1<<i);
		B = sp_right[i][B];
	}
	if(r[B] >= C)return res+1;
	// next move makes r[B] > C
	B = r[B];
	res++;
	if(r[B] <= D)return res+1;
	return -1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 43352 KB Output is correct
2 Correct 7 ms 43352 KB Output is correct
3 Correct 108 ms 45868 KB Output is correct
4 Correct 797 ms 46544 KB Output is correct
5 Correct 683 ms 44880 KB Output is correct
6 Correct 716 ms 46540 KB Output is correct
7 Correct 627 ms 45512 KB Output is correct
8 Correct 733 ms 46540 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 43348 KB Output is correct
2 Correct 5 ms 43352 KB Output is correct
3 Correct 5 ms 43352 KB Output is correct
4 Correct 5 ms 43516 KB Output is correct
5 Correct 26 ms 45360 KB Output is correct
6 Correct 33 ms 45912 KB Output is correct
7 Correct 23 ms 44624 KB Output is correct
8 Correct 32 ms 45752 KB Output is correct
9 Correct 9 ms 43812 KB Output is correct
10 Correct 32 ms 45904 KB Output is correct
11 Correct 40 ms 46520 KB Output is correct
12 Correct 26 ms 46396 KB Output is correct
13 Incorrect 29 ms 46232 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 43352 KB Output is correct
2 Correct 5 ms 43352 KB Output is correct
3 Correct 5 ms 43480 KB Output is correct
4 Incorrect 157 ms 44300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 43352 KB Output is correct
2 Correct 5 ms 43352 KB Output is correct
3 Correct 5 ms 43480 KB Output is correct
4 Incorrect 157 ms 44300 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 17 ms 43352 KB Output is correct
2 Correct 7 ms 43352 KB Output is correct
3 Correct 108 ms 45868 KB Output is correct
4 Correct 797 ms 46544 KB Output is correct
5 Correct 683 ms 44880 KB Output is correct
6 Correct 716 ms 46540 KB Output is correct
7 Correct 627 ms 45512 KB Output is correct
8 Correct 733 ms 46540 KB Output is correct
9 Correct 5 ms 43352 KB Output is correct
10 Correct 6 ms 43352 KB Output is correct
11 Correct 6 ms 43608 KB Output is correct
12 Correct 5 ms 43352 KB Output is correct
13 Incorrect 5 ms 43352 KB Output isn't correct
14 Halted 0 ms 0 KB -