oj.uz

Submission #973889

# Submission time Handle Problem Language Result Execution time Memory
973889 2024-05-02T12:20:37 Z Syrius Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1094 ms 53648 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;
	node *left , *right;
 
	node (int l , int r) {
		tl = l , tr = r , tm = (l + r) / 2;
		mx = 0;
		left = right = NULL;
	}
 
	void build() {
		if (tl == tr) {
			mx = h[tl];
			return;
		}
		left = new node(tl , tm);
		right = new node(tm+1 , tr);
		left -> build();
		right -> build();
		mx = max(left -> mx , right -> mx);
	}
 
	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};
	}
 
} *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 h2 = root -> query(c , d , inf).ff;
	int h1 = root -> query(a , b , h2).ff;
 	if (h1 == -1) return -1;
	if (b + 1 == c) return (h1 == -1) ? -1 : 1;
 
	int hmid = root -> query(b+1 , c-1 , inf).ff;
 
	if (h1 > hmid) return 1;
 
	if (hmid > h2) return -1;
	int temp = root -> query(a , b , hmid).ff;
	if (temp == -1) return -1;
	return 1 + func(inv[temp] , inv[hmid]);
}

Compilation message

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

Subtask #1
4.0 / 4.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 147 ms 48176 KB Output is correct
4 Correct 1083 ms 52668 KB Output is correct
5 Correct 807 ms 41800 KB Output is correct
6 Correct 1033 ms 52828 KB Output is correct
7 Correct 725 ms 45784 KB Output is correct
8 Correct 1094 ms 52924 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 3 ms 31064 KB Output is correct
5 Correct 5 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 3 ms 31064 KB Output is correct
5 Correct 5 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 3 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 4 ms 31064 KB Output is correct
5 Correct 41 ms 49212 KB Output is correct
6 Correct 58 ms 53440 KB Output is correct
7 Correct 26 ms 42576 KB Output is correct
8 Correct 65 ms 53432 KB Output is correct
9 Correct 10 ms 34628 KB Output is correct
10 Correct 55 ms 53648 KB Output is correct
11 Correct 44 ms 52684 KB Output is correct
12 Correct 37 ms 53328 KB Output is correct
13 Incorrect 38 ms 52944 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 31196 KB Output is correct
3 Correct 3 ms 31064 KB Output is correct
4 Incorrect 182 ms 41388 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 31196 KB Output is correct
3 Correct 3 ms 31064 KB Output is correct
4 Incorrect 182 ms 41388 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 31064 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 147 ms 48176 KB Output is correct
4 Correct 1083 ms 52668 KB Output is correct
5 Correct 807 ms 41800 KB Output is correct
6 Correct 1033 ms 52828 KB Output is correct
7 Correct 725 ms 45784 KB Output is correct
8 Correct 1094 ms 52924 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 3 ms 31064 KB Output is correct
13 Correct 5 ms 31064 KB Output is correct
14 Incorrect 4 ms 31064 KB Output isn't correct
15 Halted 0 ms 0 KB -