oj.uz

답안 #973897

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
973897 2024-05-02T12:26:30 Z Syrius 밀림 점프 (APIO21_jumps) C++14
4 / 100
 1109 ms 53580 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 hbef = -1;
	if (a != 0) hbef = root -> queryy(0 , a-1 , h1).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) 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;
      |      ^~~
jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:152:6: warning: variable 'hbef' set but not used [-Wunused-but-set-variable]
  152 |  int hbef = -1;
      |      ^~~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 31064 KB Output is correct
2 Correct 10 ms 31204 KB Output is correct
3 Correct 128 ms 48168 KB Output is correct
4 Correct 1107 ms 52684 KB Output is correct
5 Correct 780 ms 41804 KB Output is correct
6 Correct 1039 ms 52680 KB Output is correct
7 Correct 799 ms 45772 KB Output is correct
8 Correct 1109 ms 53072 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 3 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 4 ms 31064 KB Output is correct
6 Incorrect 4 ms 31064 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 3 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 4 ms 31064 KB Output is correct
6 Incorrect 4 ms 31064 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# 결과 실행 시간 메모리 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 41 ms 49204 KB Output is correct
6 Correct 62 ms 53440 KB Output is correct
7 Correct 28 ms 42584 KB Output is correct
8 Correct 48 ms 53580 KB Output is correct
9 Correct 10 ms 34392 KB Output is correct
10 Correct 48 ms 53456 KB Output is correct
11 Correct 43 ms 52684 KB Output is correct
12 Correct 46 ms 53184 KB Output is correct
13 Incorrect 40 ms 53108 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 Incorrect 193 ms 41256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 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 Incorrect 193 ms 41256 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 31064 KB Output is correct
2 Correct 10 ms 31204 KB Output is correct
3 Correct 128 ms 48168 KB Output is correct
4 Correct 1107 ms 52684 KB Output is correct
5 Correct 780 ms 41804 KB Output is correct
6 Correct 1039 ms 52680 KB Output is correct
7 Correct 799 ms 45772 KB Output is correct
8 Correct 1109 ms 53072 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 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 4 ms 31064 KB Output isn't correct
15 Halted 0 ms 0 KB -