oj.uz

Submission #975378

# Submission time Handle Problem Language Result Execution time Memory
975378 2024-05-05T04:07:31 Z akacool445k Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1318 ms 53652 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 == 0) return {-1, 0};
			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 == 0) return {-1, 0};
		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 9 ms 31064 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 140 ms 48156 KB Output is correct
4 Correct 1265 ms 52688 KB Output is correct
5 Correct 971 ms 41784 KB Output is correct
6 Correct 1252 ms 52664 KB Output is correct
7 Correct 943 ms 45792 KB Output is correct
8 Correct 1318 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 4 ms 31064 KB Output is correct
5 Correct 5 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 4 ms 31064 KB Output is correct
5 Correct 5 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 4 ms 31064 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 4 ms 31188 KB Output is correct
4 Correct 4 ms 31064 KB Output is correct
5 Correct 47 ms 49200 KB Output is correct
6 Correct 55 ms 53652 KB Output is correct
7 Correct 30 ms 42408 KB Output is correct
8 Correct 53 ms 53636 KB Output is correct
9 Correct 10 ms 34392 KB Output is correct
10 Correct 52 ms 53440 KB Output is correct
11 Correct 42 ms 52840 KB Output is correct
12 Correct 43 ms 53192 KB Output is correct
13 Incorrect 46 ms 52960 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 229 ms 41408 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 229 ms 41408 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 31064 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 140 ms 48156 KB Output is correct
4 Correct 1265 ms 52688 KB Output is correct
5 Correct 971 ms 41784 KB Output is correct
6 Correct 1252 ms 52664 KB Output is correct
7 Correct 943 ms 45792 KB Output is correct
8 Correct 1318 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 4 ms 31064 KB Output is correct
13 Correct 5 ms 31064 KB Output is correct
14 Incorrect 5 ms 31064 KB Output isn't correct
15 Halted 0 ms 0 KB -