oj.uz

Submission #676371

# Submission time Handle Problem Language Result Execution time Memory
676371 2022-12-30T14:08:30 Z penguin133 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1303 ms 86440 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;
 
int n, flag;
int X[200005], Y[200005], h[200005];
int par[20][200005], par2[20][200005], par3[20][200005], par4[20][200005];
 
struct node{
	int s,e,m, val;
	node *l, *r;
	node(int _s, int _e){
		s = _s, e = _e, m = (s + e)>>1;
		if(s != e){
			l = new node(s, m);
			r = new node(m+1, e);
			val = max(l->val, r->val);
		}
		else val = h[s];
	}
	
	int query(int a, int b){
		if(s == a && b == e)return val;
		else if(b <= m)return l->query(a, b);
		else if(a > m)return r->query(a, b);
		else return max(l->query(a, m), r->query(m+1, b));
	}
	
}*root;
 
 
void init(int N, vector<int> H){
	n = N;
	stack<int>s;
	for(int i=0;i<n;i++){
		h[i] = H[i];
		while(!s.empty() && H[s.top()] < H[i])s.pop();
		X[i] = (s.empty() ? -1 : s.top());
		par3[0][i] = X[i];
		s.push(i);
	}
	flag = 1;
	for(int i=0;i<n;i++)if(H[i] != i + 1)flag= 0;
	while(!s.empty())s.pop();
	for(int i=n-1;i>=0;i--){
		while(!s.empty() && H[s.top()] < H[i])s.pop();
		Y[i] = (s.empty() ? -1 : s.top());
		par4[0][i] = Y[i];
		s.push(i);
	}
	root = new node(0, n-1);
	for(int i=0;i<n;i++){
		if(X[i] == -1 && Y[i] == -1)par[0][i] = par2[0][i] = -1;
		else if(X[i] == -1)par[0][i] = Y[i], par2[0][i] = -1;
		else if(Y[i] == -1)par[0][i] = X[i], par2[0][i] = -1;
		else par[0][i] = (H[X[i]] > H[Y[i]] ? X[i] : Y[i]), par2[0][i] = (par[0][i] == X[i] ? Y[i] : X[i]);
	}
	for(int i=1;i<=19;i++)for(int j=0;j<n;j++)par[i][j] = (par[i-1][j] == -1 ? -1 : par[i-1][par[i-1][j]]);
	for(int i=1;i<=19;i++)for(int j=0;j<n;j++)par2[i][j] = (par2[i-1][j] == -1 ? -1 : par2[i-1][par2[i-1][j]]);
	for(int i=1;i<=19;i++)for(int j=0;j<n;j++)par3[i][j] = (par3[i-1][j] == -1 ? -1 : par3[i-1][par3[i-1][j]]);
	for(int i=1;i<=19;i++)for(int j=0;j<n;j++)par4[i][j] = (par4[i-1][j] == -1 ? -1 : par4[i-1][par4[i-1][j]]);
}
 
int minimum_jumps(int a, int b, int c, int d){

	int ans = 0, tmp = b;
	int mx = root->query(c, d);
	int mx2 = root->query(b, c-1);
	if(mx2 > mx)return -1;
	for(int i=19;i>=0;i--)if(par3[i][tmp] != -1 && par3[i][tmp] >= a && h[par3[i][tmp]] <= mx)tmp = par3[i][tmp];
	if(par4[0][tmp] >= c)return 1;
	for(int i=19;i>=0;i--)if(par[i][tmp] != -1 && (par4[0][par[i][tmp]] != -1 && par4[0][par[i][tmp]] < c) && h[par[i][tmp]] <= mx)tmp = par[i][tmp], ans += (1 << i);
	for(int i=19;i>=0;i--)if(par4[i][tmp] != -1 && par4[i][tmp] < c && h[par4[i][tmp]] <= mx)tmp = par4[i][tmp], ans += (1 << i);
//	cerr << tmp << '\n';
	assert(par4[0][tmp] >= c && par4[0][tmp] <= d);
	return ans + 1;
	
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 159 ms 69184 KB Output is correct
4 Correct 1303 ms 86440 KB Output is correct
5 Correct 993 ms 43976 KB Output is correct
6 Correct 1020 ms 86440 KB Output is correct
7 Correct 1042 ms 59408 KB Output is correct
8 Correct 1240 ms 86332 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 0 ms 720 KB Output is correct
4 Correct 1 ms 720 KB Output is correct
5 Correct 2 ms 720 KB Output is correct
6 Incorrect 2 ms 720 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 720 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 0 ms 720 KB Output is correct
4 Correct 0 ms 720 KB Output is correct
5 Correct 64 ms 69444 KB Output is correct
6 Correct 76 ms 85560 KB Output is correct
7 Correct 38 ms 44280 KB Output is correct
8 Correct 89 ms 85608 KB Output is correct
9 Correct 12 ms 13520 KB Output is correct
10 Correct 76 ms 85560 KB Output is correct
11 Correct 75 ms 86332 KB Output is correct
12 Correct 73 ms 85960 KB Output is correct
13 Incorrect 77 ms 86168 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 720 KB Output is correct
2 Correct 0 ms 720 KB Output is correct
3 Correct 0 ms 720 KB Output is correct
4 Incorrect 274 ms 39580 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 720 KB Output is correct
2 Correct 0 ms 720 KB Output is correct
3 Correct 0 ms 720 KB Output is correct
4 Incorrect 274 ms 39580 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 720 KB Output is correct
2 Correct 1 ms 720 KB Output is correct
3 Correct 159 ms 69184 KB Output is correct
4 Correct 1303 ms 86440 KB Output is correct
5 Correct 993 ms 43976 KB Output is correct
6 Correct 1020 ms 86440 KB Output is correct
7 Correct 1042 ms 59408 KB Output is correct
8 Correct 1240 ms 86332 KB Output is correct
9 Correct 1 ms 720 KB Output is correct
10 Correct 1 ms 720 KB Output is correct
11 Correct 0 ms 720 KB Output is correct
12 Correct 1 ms 720 KB Output is correct
13 Correct 2 ms 720 KB Output is correct
14 Incorrect 2 ms 720 KB Output isn't correct
15 Halted 0 ms 0 KB -