oj.uz

Submission #975373

# Submission time Handle Problem Language Result Execution time Memory
975373 2024-05-05T03:42:15 Z akacool445k Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1085 ms 53584 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 && 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: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 31064 KB Output is correct
2 Correct 5 ms 31064 KB Output is correct
3 Correct 136 ms 48172 KB Output is correct
4 Correct 1061 ms 52668 KB Output is correct
5 Correct 884 ms 41788 KB Output is correct
6 Correct 1073 ms 52692 KB Output is correct
7 Correct 820 ms 45796 KB Output is correct
8 Correct 1085 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 31064 KB Output is correct
3 Correct 4 ms 31064 KB Output is correct
4 Correct 5 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 4 ms 31064 KB Output is correct
3 Correct 4 ms 31064 KB Output is correct
4 Correct 5 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 5 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 40 ms 49188 KB Output is correct
6 Correct 62 ms 53584 KB Output is correct
7 Correct 31 ms 42548 KB Output is correct
8 Correct 50 ms 53448 KB Output is correct
9 Correct 10 ms 34604 KB Output is correct
10 Correct 49 ms 53452 KB Output is correct
11 Correct 37 ms 52816 KB Output is correct
12 Correct 37 ms 53180 KB Output is correct
13 Incorrect 40 ms 52928 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 186 ms 41264 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 186 ms 41264 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 5 ms 31064 KB Output is correct
3 Correct 136 ms 48172 KB Output is correct
4 Correct 1061 ms 52668 KB Output is correct
5 Correct 884 ms 41788 KB Output is correct
6 Correct 1073 ms 52692 KB Output is correct
7 Correct 820 ms 45796 KB Output is correct
8 Correct 1085 ms 52676 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 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 -