oj.uz

Submission #975372

# Submission time Handle Problem Language Result Execution time Memory
975372 2024-05-05T03:39:00 Z Syrius Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1105 ms 53644 KB 
#include <bits/stdc++.h>
#include "jumps.h"
using namespace std;

// #define int long long
#define ll long long
#define ff first
#define ss second
#define pint pair < int , int >
#define fast ios_base::sync_with_stdio(NULL); cin.tie(NULL)
typedef vector < int > vint;

const int inf = 1e9 + 9;
const int mxn = 2e5 + 5;
const int mod = 1e9 + 7;

int n;
int h[mxn] , le[mxn] , ri[mxn];
int inv[mxn];
int spx[19][mxn] , spn[19][mxn];

vint v;

struct node {

	int tl , tm , tr;
	int mx , mn;
	node *left , *right;

	node (int l , int r) {
		tl = l , tr = r , tm = (l + r) / 2;
		mx = 0;
		mn = inf;
		left = right = NULL;
	}

	void build() {
		if (tl == tr) {
			mx = mn = h[tl];
			return;
		}
		left = new node(tl , tm);
		right = new node(tm+1 , tr);
		left -> build();
		right -> build();
		mx = max(left -> mx , right -> mx);
		mn = min(left -> mn , right -> mn);
	}

	pint query(int l , int r , int x) {
		if (tl == tr) {
			if (mx > x) return {-1 , 0};
			return {mx , 1};
		}
		if (tl == l && tr == r) {
			if (mx < x) return {mx , 1};
			pint pr = right -> query(tm+1 , r , x);
			if (pr.ss == 0) return pr;
			pint pl = left -> query(tl , tm , x);
			return {max(pl.ff , pr.ff) , 0};
		}
		if (r <= tm) return left -> query(l , r , x);
		if (l > tm) return right -> query(l , r , x);

		pint pr = right -> query(tm+1 , r , x);
		if (pr.ss == 0) return pr;
		pint pl = left -> query(l , tm , x);
		return {max(pl.ff , pr.ff) , pl.ss};
	}

	pint queryy(int l , int r , int x) {
		if (tl == tr) {
			if (mn < x) return {-1 , 0};
			return {mn , 1};
		}
		if (tl == l && tr == r) {
			if (mn > x) return {mn , 1};
			pint pr = right -> queryy(tm+1 , r , x);
			if (pr.ss == 0) return pr;
			pint pl = left -> queryy(tl , tm , x);
			return {min(pl.ff , pr.ff) , 0};
		}
		if (r <= tm) return left -> queryy(l , r , x);
		if (l > tm) return right -> queryy(l , r , x);

		pint pr = right -> queryy(tm+1 , r , x);
		if (pr.ss == 0) return pr;
		pint pl = left -> queryy(l , tm , x);
		return {min(pl.ff , pr.ff) , pl.ss};
	}

} *root;

void init(int N , vint H) {
	n = N;
	for (int i = 0; i < n; i++) {
		h[i] = H[i];
		inv[h[i]] = i;
	}

	root = new node(0 , n-1);
	root -> build();

	for (int i = 0; i < n; i++) {
		while (v.size() > 0 && v.back() < h[i]) {
			ri[v.back()] = h[i];
			v.pop_back();
		}
		if (v.size() > 0) le[h[i]] = v.back();
		v.push_back(h[i]);
	}

	for (int i = 0; i < n; i++) {
		spx[0][h[i]] = max(le[h[i]] , ri[h[i]]);
		spn[0][h[i]] = min(le[h[i]] , ri[h[i]]);
		if (spn[0][h[i]] == 0) spn[0][h[i]] = spx[0][h[i]];
	}

	for (int j = 1; j < 19; j++) {
		for (int i = 0; i < n; i++) {
			spx[j][h[i]] = spx[j-1][spx[j-1][h[i]]];
			spn[j][h[i]] = spn[j-1][spn[j-1][h[i]]];
		}
	}
}

int func(int a , int d) {
	if (h[a] > h[d]) return -1;
	int dis = 0;
	for (int i = 18; i >= 0; i--) {
		if (spx[i][h[a]] > h[d] || spx[i][h[a]] == 0) continue;
		if (spx[i][h[a]] == h[d]) return (1 << i);
		int t = func(inv[spx[i][h[a]]] , d);
		return (t == -1) ? t : ((1<<i) + t);
	}

	for (int i = 18; i >= 0; i--) {
		if (spn[i][h[a]] > h[d] || spn[i][h[a]] == 0) continue;
		if (spn[i][h[a]] == h[d]) return (1 << i);
		int t = func(inv[spn[i][h[a]]] , d);
		return (t == -1) ? t : ((1<<i) + t);
	}

	return -1;
}

int minimum_jumps(int a , int b , int c , int d) {

	int ans = inf;
	int hmax = root -> query(a , c-1 , inf).ff;

	int h2 = root -> query(c , d , inf).ff;
	int h1 = root -> query(a , b , h2).ff;
	if (h1 == -1) return -1;

	int hbef = -1;
	if (a > 0) hbef = root -> queryy(0 , a-1 , hmax).ff;
	if (hbef != -1 && hbef < h2) ans = min(ans , 1 + func(inv[h1] , inv[hbef]));

	int hmid = -1;
	if (b + 1 != c) hmid = root -> query(b+1 , c-1 , inf).ff;
	else return 1;
	
	if (hmid > h2) return -1;
	if (h1 > hmid) return 1;

	if (hmid != -1) ans = min(ans , 1 + func(inv[h1] , inv[hmid]));
	return (ans == inf) ? -1 : ans;
}

Compilation message

jumps.cpp: In function 'int func(int, int)':
jumps.cpp:129:6: warning: unused variable 'dis' [-Wunused-variable]
  129 |  int dis = 0;
      |      ^~~

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31316 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 127 ms 48164 KB Output is correct
4 Correct 1049 ms 52792 KB Output is correct
5 Correct 806 ms 41808 KB Output is correct
6 Correct 1042 ms 52680 KB Output is correct
7 Correct 757 ms 45760 KB Output is correct
8 Correct 1105 ms 52688 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 3 ms 31188 KB Output is correct
3 Correct 4 ms 31064 KB Output is correct
4 Correct 4 ms 31064 KB Output is correct
5 Correct 42 ms 49216 KB Output is correct
6 Correct 53 ms 53460 KB Output is correct
7 Correct 33 ms 42560 KB Output is correct
8 Correct 52 ms 53460 KB Output is correct
9 Correct 10 ms 34392 KB Output is correct
10 Correct 51 ms 53644 KB Output is correct
11 Correct 40 ms 52672 KB Output is correct
12 Correct 38 ms 53196 KB Output is correct
13 Incorrect 37 ms 53040 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

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

Subtask #6
0 / 21.0

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

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 31316 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 127 ms 48164 KB Output is correct
4 Correct 1049 ms 52792 KB Output is correct
5 Correct 806 ms 41808 KB Output is correct
6 Correct 1042 ms 52680 KB Output is correct
7 Correct 757 ms 45760 KB Output is correct
8 Correct 1105 ms 52688 KB Output is correct
9 Correct 4 ms 31064 KB Output is correct
10 Correct 4 ms 31064 KB Output is correct
11 Correct 4 ms 31064 KB Output is correct
12 Correct 5 ms 31440 KB Output is correct
13 Correct 4 ms 31064 KB Output is correct
14 Incorrect 4 ms 31064 KB Output isn't correct
15 Halted 0 ms 0 KB -