oj.uz

Submission #567050

# Submission time Handle Problem Language Result Execution time Memory
567050 2022-05-23T07:38:37 Z amunduzbaev Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 924 ms 1048576 KB 
#include "jumps.h"

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

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

const int B = 450;
const int N = 2e5 + 5;
const int lg = 18;
vector<int> edges[N];
int mx[N][lg], mn[N][lg], h[N], pos[N];
int st[N][lg], pre[N/B][N];
int lx[N], rx[N];

struct ST{
	int tree[N << 2], b;
	void build(int lx = 0, int rx = N, int x = 1){
		if(lx == rx) { tree[x] = pre[b][x]; return; }
		int m = (lx + rx) >> 1;
		build(lx, m, x << 1);
		build(m + 1, rx, x << 1 | 1);
		tree[x] = min(tree[x<<1], tree[x<<1 | 1]);
	}
	
	int get(int l, int r, int lx = 0, int rx = N, int x = 1){
		if(lx > r || rx < l) return N;
		if(lx >= l && rx <= r) return tree[x];
		int m = (lx + rx) >> 1;
		return min(get(l, r, lx, m, x<<1), get(l, r, m+1, rx, x<<1|1));
	}
}tree[N/B];

void init(int n, vector<int> H){
	for(int i=0;i<n;i++){
		h[i] = H[i];
		pos[h[i]] = i;
	}
	//~ tree.build();
	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;
	for(int i=0;i<n;i++){
		if(h[lx[i]] < h[rx[i]]){
			swap(lx[i], rx[i]);
		} 
		edges[lx[i]].push_back(i);
		edges[rx[i]].push_back(i);
		mn[i][0] = rx[i];
		mx[i][0] = lx[i];
		lx[i] = min(lx[i], rx[i]);
		if(lx[i] == n) lx[i] = -1;
	}
	mn[n][0] = mx[n][0] = n;
	edges[n].clear();
	
	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];
		}
	}
	
	for(int b=0;b<=n/B;b++){
		memset(pre[b], 127, sizeof pre[b]);
		queue<int> q;
		for(int i=0;i<B;i++){
			q.push(b * B + i);
			pre[b][b * B + i] = 0;
		}
		
		while(!q.empty()){
			int u = q.front(); q.pop();
			for(auto x : edges[u]){
				if(pre[b][x] > pre[b][u] + 1){
					pre[b][x] = pre[b][u] + 1;
					q.push(x);
				}
			}
		}
		tree[b].b = b;
		tree[b].build();
	}
	
	for(int i=0;i<n;i++){
		st[i][0] = h[i];
	}
	
	for(int j=1;j<lg;j++){
		for(int i=0;i+(1 << (j - 1))<n;i++){
			st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j-1]);
		}
	}
}

int get(int l, int r){
	int lg = __lg(r - l + 1);
	return max(st[l][lg], st[r - (1 << lg) + 1][lg]);
}

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 -1;
	return res;
}

int minimum_jumps(int a, int b, int c, int d) {
	int bl = c / B, br = d / B;
	int res = N;
	for(int j=bl+1;j<br;j++){
		assert(false);
		res = min(res, tree[j].get(a, b));
	}
	
	auto calc = [&](int l, int r){
		for(int i=l;i<=r;i++){
			int L = max(lx[i] + 1, a);
			if(L <= b){
				int mx = pos[get(L, b)];
				res = min(res, check(mx, i));
			}
		}
	};
	
	if(bl == br){
		calc(c, d);
	} else {
		if(c % B == 0) res = min(res, tree[bl].get(a, b));
		else calc(c, (bl + 1) * B - 1);
		if(d % B == B - 1) res = min(res, tree[br].get(a, b));
		else calc(br * B, d);
	}
	
	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 4 ms 7888 KB Output is correct
2 Correct 5 ms 7888 KB Output is correct
3 Runtime error 924 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7888 KB Output is correct
2 Correct 4 ms 7888 KB Output is correct
3 Correct 5 ms 7888 KB Output is correct
4 Correct 5 ms 7904 KB Output is correct
5 Incorrect 5 ms 7888 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 7888 KB Output is correct
2 Correct 4 ms 7888 KB Output is correct
3 Correct 5 ms 7888 KB Output is correct
4 Correct 5 ms 7904 KB Output is correct
5 Incorrect 5 ms 7888 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7888 KB Output is correct
2 Correct 5 ms 7888 KB Output is correct
3 Correct 4 ms 7888 KB Output is correct
4 Correct 5 ms 7888 KB Output is correct
5 Runtime error 770 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 7888 KB Output is correct
2 Correct 5 ms 7888 KB Output is correct
3 Correct 6 ms 7888 KB Output is correct
4 Incorrect 614 ms 608248 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 7888 KB Output is correct
2 Correct 5 ms 7888 KB Output is correct
3 Correct 6 ms 7888 KB Output is correct
4 Incorrect 614 ms 608248 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7888 KB Output is correct
2 Correct 5 ms 7888 KB Output is correct
3 Runtime error 924 ms 1048576 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -