oj.uz

Submission #975367

# Submission time Handle Problem Language Result Execution time Memory
975367 2024-05-05T03:33:25 Z akacool445k Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1086 ms 53616 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, c - 1, 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 4 ms 31316 KB Output is correct
2 Correct 6 ms 31064 KB Output is correct
3 Correct 113 ms 48172 KB Output is correct
4 Correct 1059 ms 52664 KB Output is correct
5 Correct 818 ms 42016 KB Output is correct
6 Correct 1086 ms 52864 KB Output is correct
7 Correct 826 ms 45768 KB Output is correct
8 Correct 976 ms 53304 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 3 ms 31072 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 31200 KB Output is correct
6 Incorrect 5 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 3 ms 31072 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 31200 KB Output is correct
6 Incorrect 5 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 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 39 ms 49464 KB Output is correct
6 Correct 52 ms 53452 KB Output is correct
7 Correct 34 ms 42584 KB Output is correct
8 Correct 51 ms 53616 KB Output is correct
9 Correct 11 ms 34624 KB Output is correct
10 Correct 50 ms 53436 KB Output is correct
11 Correct 46 ms 52684 KB Output is correct
12 Correct 43 ms 53152 KB Output is correct
13 Incorrect 46 ms 53076 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 Incorrect 171 ms 41228 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.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 Incorrect 171 ms 41228 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 31316 KB Output is correct
2 Correct 6 ms 31064 KB Output is correct
3 Correct 113 ms 48172 KB Output is correct
4 Correct 1059 ms 52664 KB Output is correct
5 Correct 818 ms 42016 KB Output is correct
6 Correct 1086 ms 52864 KB Output is correct
7 Correct 826 ms 45768 KB Output is correct
8 Correct 976 ms 53304 KB Output is correct
9 Correct 4 ms 31064 KB Output is correct
10 Correct 3 ms 31072 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 31200 KB Output is correct
14 Incorrect 5 ms 31064 KB Output isn't correct
15 Halted 0 ms 0 KB -