oj.uz

Submission #417426

# Submission time Handle Problem Language Result Execution time Memory
417426 2021-06-03T17:23:38 Z CSQ31 Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1298 ms 51252 KB 
#include "jumps.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)(a.size())
typedef long long int ll;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
const int MAXN = 2e5+5;
int l[20][MAXN],r[20][MAXN],high[20][MAXN];
vector<int>H;
void init(int n, vector<int>h){
	H = h;
	H.insert(H.begin(),1e9);
	H.pb(1e9);
	stack<pii>stk;
	for(int i=0;i<=n+1;i++){
		while(!stk.empty() && stk.top().fi <= H[i])stk.pop();
		if(!stk.empty())l[0][i] = stk.top().se;
		else l[0][i] = i;
		stk.push({H[i],i});
	}
	while(!stk.empty())stk.pop();
	for(int i=n+1;i>=0;i--){
	    while(!stk.empty() && stk.top().fi <= H[i])stk.pop();
		if(!stk.empty())r[0][i] = stk.top().se;
		else r[0][i] = i;
		stk.push({H[i],i});
	}
	for(int i=0;i<=n+1;i++){
		high[0][i] = (H[r[0][i]] > H[l[0][i]])?r[0][i]:l[0][i];
	}
	//cout<<high[0][1]<<'\n';
	for(int j=1;j<20;j++){
		for(int i=0;i<=n+1;i++){
			l[j][i] = l[j-1][l[j-1][i]];
			r[j][i] = r[j-1][r[j-1][i]];
			high[j][i] = high[j-1][high[j-1][i]];
		}
	}
	
}
//
int minimum_jumps(int a,int b,int c,int d){
	a++;
	b++;
	c++;
	d++;
	if(c-1 == b){
		return r[0][b] <=d?1:-1;
	}
	int mid = b+1; //mid just means bigger element in (b,c),cuz we have to cross mid regardless
	for(int i=19;i>=0;i--)if(r[i][mid] < c)mid = r[i][mid];
	if(r[0][mid] > d || r[0][b] > d)return -1;
	if(H[b] > mid && r[0][b] <=d)return 1;
	int cur = b;
	for(int i=19;i>=0;i--)if(l[i][cur] >= a && H[l[i][cur]] < H[mid])cur = l[i][cur]; //cur is where we should start from
	int ans= 0;
	//if(a == 1)cout<<l[0][cur]<<'\n';
	if(l[0][cur] >= a){
		if(r[0][l[0][cur]] <= d)return 1; //if this case fails it just means we can never ever again go left
	}else{
		for(int i=19;i>=0;i--){
			if(H[high[i][cur]] <= H[mid]){
				cur = high[i][cur];
				ans+=(1<<i);
			}
		}
		//if(a == 1)cout<<cur<<" "<<ans<<'\n';
		if(cur == mid)return r[0][mid] <=d?ans+1:-1;
		else if(l[0][cur] != 0 && r[0][l[0][cur]] <= d)return ans+2; 
	}
	for(int i=19;i>=0;i--){
		if(r[i][cur] < c){
			cur = r[i][cur];
			ans+=(1<<i);
		}
	}
	cur = r[0][cur];
	if(c<=cur && cur<=d)return ans+1;
	else return -1; 
	
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 162 ms 41040 KB Output is correct
4 Correct 1184 ms 51244 KB Output is correct
5 Correct 1054 ms 26144 KB Output is correct
6 Correct 1298 ms 51208 KB Output is correct
7 Correct 1006 ms 35336 KB Output is correct
8 Correct 1132 ms 51252 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Correct 1 ms 584 KB Output is correct
5 Correct 55 ms 40220 KB Output is correct
6 Correct 79 ms 49584 KB Output is correct
7 Correct 31 ms 25776 KB Output is correct
8 Correct 62 ms 49548 KB Output is correct
9 Correct 10 ms 8136 KB Output is correct
10 Correct 81 ms 49560 KB Output is correct
11 Correct 80 ms 51232 KB Output is correct
12 Correct 73 ms 50712 KB Output is correct
13 Correct 57 ms 50720 KB Output is correct
14 Incorrect 60 ms 49600 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 1 ms 584 KB Output is correct
4 Incorrect 191 ms 23048 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 584 KB Output is correct
2 Correct 1 ms 584 KB Output is correct
3 Correct 162 ms 41040 KB Output is correct
4 Correct 1184 ms 51244 KB Output is correct
5 Correct 1054 ms 26144 KB Output is correct
6 Correct 1298 ms 51208 KB Output is correct
7 Correct 1006 ms 35336 KB Output is correct
8 Correct 1132 ms 51252 KB Output is correct
9 Correct 1 ms 584 KB Output is correct
10 Correct 1 ms 584 KB Output is correct
11 Correct 1 ms 584 KB Output is correct
12 Correct 1 ms 584 KB Output is correct
13 Incorrect 2 ms 584 KB Output isn't correct
14 Halted 0 ms 0 KB -