oj.uz

Submission #975379

# Submission time Handle Problem Language Result Execution time Memory
975379 2024-05-05T04:10:44 Z akacool445k Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1112 ms 53640 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 (mx < x) return {-1 , 0};
			return {mx , 1};
		}
		if (tl == l && tr == r) {
			if (mx < x) return {-1, 0};
			pint pr = right -> query(tm+1, tr, x);
			if (pr.ss == 1) return pr;
			return left -> queryy(tl, tm, x);
		}
		if (r <= tm) return left -> queryy(l, r, x);
		if (l > tm) return right -> queryy(l, r, x);
		pint pr = right -> query(tm+1, tr, x);
		if (pr.ss == 1) return pr;
		return left -> queryy(tl, tm, x);
	}
 
} *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 && hbef < h2) ans = min(ans , 1 + func(inv[h1] , inv[hbef]));
	return ans;
}

Compilation message

jumps.cpp: In function 'int func(int, int)':
jumps.cpp:126:6: warning: unused variable 'dis' [-Wunused-variable]
  126 |  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 144 ms 48348 KB Output is correct
4 Correct 1100 ms 52688 KB Output is correct
5 Correct 880 ms 41804 KB Output is correct
6 Correct 1107 ms 52776 KB Output is correct
7 Correct 819 ms 45904 KB Output is correct
8 Correct 1112 ms 52672 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 31064 KB Output is correct
3 Correct 4 ms 31316 KB Output is correct
4 Correct 4 ms 31064 KB Output is correct
5 Correct 4 ms 31064 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 31064 KB Output is correct
3 Correct 4 ms 31316 KB Output is correct
4 Correct 4 ms 31064 KB Output is correct
5 Correct 4 ms 31064 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 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 39 ms 49204 KB Output is correct
6 Correct 49 ms 53456 KB Output is correct
7 Correct 27 ms 42828 KB Output is correct
8 Correct 49 ms 53448 KB Output is correct
9 Correct 10 ms 34392 KB Output is correct
10 Correct 52 ms 53640 KB Output is correct
11 Correct 40 ms 52688 KB Output is correct
12 Correct 38 ms 53328 KB Output is correct
13 Incorrect 39 ms 52940 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 31204 KB Output is correct
2 Correct 3 ms 31064 KB Output is correct
3 Correct 3 ms 31316 KB Output is correct
4 Incorrect 204 ms 41260 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 31204 KB Output is correct
2 Correct 3 ms 31064 KB Output is correct
3 Correct 3 ms 31316 KB Output is correct
4 Incorrect 204 ms 41260 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 144 ms 48348 KB Output is correct
4 Correct 1100 ms 52688 KB Output is correct
5 Correct 880 ms 41804 KB Output is correct
6 Correct 1107 ms 52776 KB Output is correct
7 Correct 819 ms 45904 KB Output is correct
8 Correct 1112 ms 52672 KB Output is correct
9 Correct 4 ms 31064 KB Output is correct
10 Correct 3 ms 31064 KB Output is correct
11 Correct 4 ms 31316 KB Output is correct
12 Correct 4 ms 31064 KB Output is correct
13 Correct 4 ms 31064 KB Output is correct
14 Incorrect 5 ms 31064 KB Output isn't correct
15 Halted 0 ms 0 KB -