oj.uz

Submission #566893

# Submission time Handle Problem Language Result Execution time Memory
566893 2022-05-23T05:44:44 Z amunduzbaev Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 4000 ms 78308 KB 
#include "jumps.h"

#ifndef EVAL
#include "stub.cpp"
#endif

#include "bits/stdc++.h"
using namespace std;

const int B = 205;
const int N = 2e5 + 5;
const int lg = 18;
int mx[N][lg], mn[N][lg], h[N], pos[N];
int lx[N], rx[N], prec[N/B][N];

struct ST{
	vector<int> tree[N << 2];
	int mx[N << 2];
	void build(int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x].push_back(h[lx]); return; }
		int m = (lx + rx) >> 1;
		build(lx, m, x << 1);
		build(m + 1, rx, x << 1 | 1);
		tree[x].insert(tree[x].end(), tree[x<<1].begin(), tree[x<<1].end());
		tree[x].insert(tree[x].end(), tree[x<<1|1].begin(), tree[x<<1|1].end());
		sort(tree[x].begin(), tree[x].end());
		mx[x] = max(mx[x<<1], mx[x<<1|1]);
	}
	
	int get_(int l, int r, int v, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r){
			if(mx[x] <= v) return -1;
			if(lx == rx) return lx;
			int m = (lx + rx) >> 1;
			if(mx[x << 1 | 1] > v) return get_(l, r, v, m + 1, rx, x<<1 | 1);
			else return get_(l, r, v, lx, m, x << 1);
		} int m = (lx + rx) >> 1;
		int R = get_(l, r, v, m + 1, rx, x << 1 | 1);
		if(~R) return R;
		return get_(l, r, v, lx, m, x << 1);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return -1;
		if(lx >= l && rx <= r) return mx[x];
		int m = (lx + rx) >> 1;
		return max(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}tree;

void init(int n, vector<int> H){
	for(int i=0;i<n;i++){
		h[i] = H[i];
		pos[h[i]] = i;
	}
	vector<int> ss;
	for(int i=0;i<n;i++){
		while(!ss.empty() && h[ss.back()] < h[i]) ss.pop_back();
		if(!ss.empty()) lx[i] = ss.back();
		else lx[i] = n;
		ss.push_back(i);
	} ss.clear();
	for(int i=n-1;~i;i--){
		while(!ss.empty() && h[ss.back()] < h[i]) ss.pop_back();
		if(!ss.empty()) rx[i] = ss.back();
		else rx[i] = n;
		ss.push_back(i);
	} ss.clear();
	h[n] = N;
	tree.build();
	for(int i=0;i<n;i++){
		if(h[lx[i]] < h[rx[i]]){
			swap(lx[i], rx[i]);
		} 
		mn[i][0] = rx[i];
		mx[i][0] = lx[i];
	}
	mn[n][0] = mx[n][0] = n;
	//~ for(int i=0;i<n;i++) cout<<mn[i][0]<<" ";
	//~ cout<<"\n";
	//~ for(int i=0;i<n;i++) cout<<mx[i][0]<<" ";
	//~ cout<<"\n";
	
	for(int j=1;j<lg;j++){
		for(int i=0;i<=n;i++){
			mn[i][j] = mn[mn[i][j-1]][j-1];
			mx[i][j] = mx[mx[i][j-1]][j-1];
		}
	}
}

int check(int a, int c){
	int res = 0;
	for(int i=lg-1;~i;i--){
		if(h[mx[a][i]] <= h[c]){
			//~ cout<<mx[a][i]<<" "<<h[mx[a][i]]<<" "<<h[c]<<"\n";
			//~ cout<<i<<"\n";
			a = mx[a][i], res += (1 << i);
		}
	}
	for(int i=lg-1;~i;i--){
		if(h[mn[a][i]] <= h[c]){
			//~ cout<<mx[a][i]<<" "<<h[mx[a][i]]<<" "<<h[c]<<"\n";
			a = mn[a][i], res += (1 << i);
		}
	}
	
	if(a != c) return N;
	return res;
}

int minimum_jumps(int a, int b, int c, int d) {
	//~ int l = max(a, tree.get_(a, b, h[c]) + 1);
	//~ if(l > b) return -1;
	//~ a = tree.get(l, b);
	//~ return check(pos[a], c);
	int res = N;	
	for(int i=c;i<=d;i++){
		int mx = b + 1, L = a;
		for(int j=b;j>=a;j--){
			if(h[j] > h[i]) { L = j + 1; break; }
			if(mx > b || h[j] > h[mx]) mx = j;
			res = min(res, check(j, i));
		}
		if(L <= b){
			int mx = tree.get(L, b);
			res = min(res, check(pos[mx], i));
		}
		//~ if(mx <= b) res = min(res, check(mx, i));
	}
	if(res == N) return -1;
	return res;
}

/*

7 2
3 2 1 6 4 5 7
4 4 6 6
0 1 2 2

*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 44656 KB Output is correct
2 Correct 87 ms 44672 KB Output is correct
3 Execution timed out 4053 ms 71360 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 44676 KB Output is correct
2 Correct 91 ms 44572 KB Output is correct
3 Correct 87 ms 44644 KB Output is correct
4 Correct 88 ms 44672 KB Output is correct
5 Incorrect 87 ms 44604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 44676 KB Output is correct
2 Correct 91 ms 44572 KB Output is correct
3 Correct 87 ms 44644 KB Output is correct
4 Correct 88 ms 44672 KB Output is correct
5 Incorrect 87 ms 44604 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 44576 KB Output is correct
2 Correct 90 ms 44696 KB Output is correct
3 Correct 92 ms 44572 KB Output is correct
4 Correct 87 ms 44656 KB Output is correct
5 Correct 232 ms 70652 KB Output is correct
6 Correct 345 ms 77212 KB Output is correct
7 Correct 180 ms 61148 KB Output is correct
8 Correct 337 ms 77264 KB Output is correct
9 Correct 110 ms 49264 KB Output is correct
10 Correct 387 ms 77060 KB Output is correct
11 Execution timed out 4051 ms 78308 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 44652 KB Output is correct
2 Correct 95 ms 44588 KB Output is correct
3 Correct 108 ms 44672 KB Output is correct
4 Correct 406 ms 59296 KB Output is correct
5 Correct 1155 ms 77052 KB Output is correct
6 Correct 416 ms 49676 KB Output is correct
7 Correct 996 ms 77148 KB Output is correct
8 Correct 595 ms 55616 KB Output is correct
9 Correct 1042 ms 77116 KB Output is correct
10 Correct 1029 ms 78264 KB Output is correct
11 Correct 1035 ms 78204 KB Output is correct
12 Correct 1221 ms 78196 KB Output is correct
13 Correct 1027 ms 77132 KB Output is correct
14 Incorrect 976 ms 77524 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 99 ms 44652 KB Output is correct
2 Correct 95 ms 44588 KB Output is correct
3 Correct 108 ms 44672 KB Output is correct
4 Correct 406 ms 59296 KB Output is correct
5 Correct 1155 ms 77052 KB Output is correct
6 Correct 416 ms 49676 KB Output is correct
7 Correct 996 ms 77148 KB Output is correct
8 Correct 595 ms 55616 KB Output is correct
9 Correct 1042 ms 77116 KB Output is correct
10 Correct 1029 ms 78264 KB Output is correct
11 Correct 1035 ms 78204 KB Output is correct
12 Correct 1221 ms 78196 KB Output is correct
13 Correct 1027 ms 77132 KB Output is correct
14 Incorrect 976 ms 77524 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 44656 KB Output is correct
2 Correct 87 ms 44672 KB Output is correct
3 Execution timed out 4053 ms 71360 KB Time limit exceeded
4 Halted 0 ms 0 KB -