Submission #417927

#	Time	Username	Problem	Language	Result	Execution time	Memory
417927		aymanrs	Rainforest Jumps (APIO21_jumps)	C++14	21 / 100	2876 ms	1048580 KiB

jumps

#include <bits/stdc++.h>
using namespace std;
struct node {
	int l, r, v = 1e9, i, lz = 0;
	node *le = nullptr, *ri = nullptr, *c;
};
vector<node*> versions;
void prop(node* n){
	if(n->l == n->r) goto gh;
	if(n->le->i != n->i){
		prop(n->le);
		prop(n->c->le);
		n->le = new node(*n->le);
		n->le->i = n->i;
		n->le->c = n->c->le;
		n->le->v = min(n->le->v, n->le->c->v);
	}
	if(n->ri->i != n->i){
		prop(n->ri);
		prop(n->c->ri);
		n->ri = new node(*n->ri);
		n->ri->i = n->i;
		n->ri->c = n->c->ri;
		n->ri->v = min(n->ri->v, n->ri->c->v);
	}
	gh:
	if(n->lz){
		n->v += n->lz;
		if(n->l != n->r){
			n->le->lz += n->lz;
			n->ri->lz += n->lz;
		}
		n->lz = 0;
	}
}
int get(node* n, int a, int b){
	if(n->v >= 1e9) {
		n->lz = 0;
		return 1e9;
	}
	prop(n);
	if(n->r < a || b < n->l) return 1e9;
	if(a <= n->l && n->r <= b){
		return n->v;
	}
	return min(get(n->le, a, b), get(n->ri, a, b));
}
void upd(node* n){
	prop(n);
	n->v = 0;
	if(n->l == n->r) return;
	if(n->i <= n->le->r) upd(n->le);
	else upd(n->ri);
}
void cons(node* n){
	if(n->l <= n->i && n->i <= n->r) n->v = 0;
	else n->v = 1e9;
	if(n->l == n->r) return;
	int mid = (n->l+n->r)/2;
	n->le = new node;
	n->le->i = n->i;
	n->le->l = n->l;
	n->le->r = mid;
	cons(n->le);
	n->ri = new node;
	n->ri->i = n->i;
	n->ri->l = mid+1;
	n->ri->r = n->r;
	cons(n->ri);
}
void init(int N, vector<int> H){
	int sparse[N][18];
	for(int i = 0;i < N;i++){
		sparse[i][0] = H[i];
	}
	for(int k = 1;k < 18;k++){
		for(int i = 0;i + (1 << k) - 1 < N;i++){
			sparse[i][k] = max(sparse[i][k-1], sparse[i + (1 << (k-1))][k-1]);
		}
	}
	int bl[N+1] = {0};
	for(int i = 2;i <= N;i++){
		bl[i] = bl[i-1];
		if((i&-i) == i) bl[i]++;
	}
	versions.resize(N, nullptr);
	int mx = max_element(H.begin(), H.end()) - H.begin();
	node* inst = new node;
	inst->i = mx;
	inst->l = 0;
	inst->r = N-1;
	cons(inst);
	versions[mx] = inst;
	int f, t;
	pair<int, int> tem[N];
	for(int i= 0;i < N;i++) tem[i] = {H[i], i};
	sort(tem, tem+N, greater<pair<int, int>>());
	for(int j = 1;j < N;j++){
		int i = tem[j].second;
		f = t = -1;
		int l = 0, r = i-1, m, b = -1;
		while(l <= r){
			m = (l+r)/2;
			int d = r-m+1;
			if(max(sparse[m][bl[d]], sparse[r - (1 << bl[d]) + 1][bl[d]]) > H[i]){
				l = m+1;
				if(H[m] > H[i]) b = max(b, m);
			} else r = m-1;
		}
		if(b!=-1) f = b;
		l = i+1, r = N-1,b = N;
		while(l <= r){
			m = (l+r)/2;
			int d = m-l+1;
			if(max(sparse[l][bl[d]], sparse[m - (1 << bl[d]) + 1][bl[d]]) > H[i]){
				r = m-1;
				if(H[m] > H[i]) b = min(b, m);
			} else l = m+1;
		}
		if(b!=N) t = b;
		if(f == -1) {
			versions[i] = new node(*versions[t]);
			versions[i]->i = i;
			versions[i]->c = versions[t];
		} else if (t == -1){
			versions[i] = new node(*versions[f]);
			versions[i]->i = i;
			versions[i]->c = versions[f];
		} else {
			versions[i] = new node(*versions[f]);
			versions[i]->i = i;
			versions[i]->c = versions[t];
		}
		versions[i]->lz++;
		upd(versions[i]);
	}
}
int minimum_jumps(int A, int B, int C, int D){
	int a = 1e9;
	for(int i = A;i <= B;i++){
		a = min(a, get(versions[i], C, D));
	}
	return a >= 1e9 ? -1 : a;
}
// int main(){
// 	init(7, {3, 2, 1, 6, 4, 5, 7});
// 	cout << minimum_jumps(4, 4, 6, 6) << '\n';
// 	cout << minimum_jumps(1, 3, 5, 6) << '\n';
// 	cout << minimum_jumps(0, 1, 2, 2) << '\n';
// }

• Subtask 1: 0 / 4
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 23
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19