oj.uz

Submission #973963

# Submission time Handle Problem Language Result Execution time Memory
973963 2024-05-02T13:39:17 Z akacool445k Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1115 ms 53620 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 h2 = root -> query(c , d , inf).ff;
	int h1 = root -> query(a , b , h2).ff;
	if (h1 == -1) return -1;
    int hp = root -> query(a, d, inf).ff;
	int hbef = -1;
	if (a != 0) hbef = root -> queryy(0 , a-1 , hp).ff;
 
	if (b + 1 == c) return 1;
 
	int hmid = root -> query(b + 1 , c - 1 , inf).ff;
	if (h1 > hmid) return 1;
	if (hmid > h2) return -1;
	
	int ans = 1 + func(inv[h1] , inv[hmid]);
	if (hbef != -1 && root->query(a , c-1 , inf).ff < hbef) ans = min(ans , 1 + func(inv[h1] , inv[hbef]));
 
	return 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 31064 KB Output is correct
2 Correct 4 ms 31208 KB Output is correct
3 Correct 134 ms 48176 KB Output is correct
4 Correct 1006 ms 52668 KB Output is correct
5 Correct 868 ms 41896 KB Output is correct
6 Correct 1072 ms 52668 KB Output is correct
7 Correct 781 ms 45780 KB Output is correct
8 Correct 1115 ms 52676 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 31060 KB Output is correct
3 Correct 4 ms 31064 KB Output is correct
4 Correct 4 ms 31064 KB Output is correct
5 Correct 4 ms 31064 KB Output is correct
6 Incorrect 6 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 31060 KB Output is correct
3 Correct 4 ms 31064 KB Output is correct
4 Correct 4 ms 31064 KB Output is correct
5 Correct 4 ms 31064 KB Output is correct
6 Incorrect 6 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 3 ms 31064 KB Output is correct
4 Correct 4 ms 31064 KB Output is correct
5 Correct 40 ms 49192 KB Output is correct
6 Correct 51 ms 53620 KB Output is correct
7 Correct 26 ms 42604 KB Output is correct
8 Correct 49 ms 53460 KB Output is correct
9 Correct 9 ms 34392 KB Output is correct
10 Correct 51 ms 53616 KB Output is correct
11 Correct 46 ms 52668 KB Output is correct
12 Correct 43 ms 53184 KB Output is correct
13 Incorrect 39 ms 52948 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 168 ms 41164 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 168 ms 41164 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 31064 KB Output is correct
2 Correct 4 ms 31208 KB Output is correct
3 Correct 134 ms 48176 KB Output is correct
4 Correct 1006 ms 52668 KB Output is correct
5 Correct 868 ms 41896 KB Output is correct
6 Correct 1072 ms 52668 KB Output is correct
7 Correct 781 ms 45780 KB Output is correct
8 Correct 1115 ms 52676 KB Output is correct
9 Correct 4 ms 31064 KB Output is correct
10 Correct 4 ms 31060 KB Output is correct
11 Correct 4 ms 31064 KB Output is correct
12 Correct 4 ms 31064 KB Output is correct
13 Correct 4 ms 31064 KB Output is correct
14 Incorrect 6 ms 31064 KB Output isn't correct
15 Halted 0 ms 0 KB -