oj.uz

답안 #973839

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
973839 2024-05-02T11:40:40 Z Syrius 밀림 점프 (APIO21_jumps) C++14
4 / 100
 1084 ms 53700 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;
	node *left , *right;

	node (int l , int r) {
		tl = l , tr = r , tm = (l + r) / 2;
		mx = 0;
		left = right = NULL;
	}

	void build() {
		if (tl == tr) {
			mx = h[tl];
			return;
		}
		left = new node(tl , tm);
		right = new node(tm+1 , tr);
		left -> build();
		right -> build();
		mx = max(left -> mx , right -> mx);
	}

	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};
	}

} *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 (b + 1 == c) return (h1 == -1) ? -1 : 1;

	int hmid = root -> query(b+1 , c-1 , inf).ff;

	if (h1 > hmid) return 1;

	if (hmid > h2) return -1;
	int temp = root -> query(a , b , hmid).ff;
	if (temp == -1) return -1;
	return 1 + func(inv[temp] , inv[hmid]);
}

Compilation message

jumps.cpp: In function 'int func(int, int)':
jumps.cpp:106:6: warning: unused variable 'dis' [-Wunused-variable]
  106 |  int dis = 0;
      |      ^~~

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 123 ms 48168 KB Output is correct
4 Correct 929 ms 52684 KB Output is correct
5 Correct 852 ms 41812 KB Output is correct
6 Correct 1084 ms 52684 KB Output is correct
7 Correct 777 ms 45924 KB Output is correct
8 Correct 982 ms 52696 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 3 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

# 결과 실행 시간 메모리 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 3 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

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 31064 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 4 ms 31208 KB Output is correct
4 Correct 4 ms 31064 KB Output is correct
5 Correct 42 ms 49212 KB Output is correct
6 Correct 53 ms 53432 KB Output is correct
7 Correct 32 ms 42584 KB Output is correct
8 Correct 64 ms 53700 KB Output is correct
9 Correct 10 ms 34392 KB Output is correct
10 Correct 49 ms 53460 KB Output is correct
11 Correct 43 ms 52688 KB Output is correct
12 Correct 39 ms 53204 KB Output is correct
13 Incorrect 39 ms 52924 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 31060 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 4 ms 31064 KB Output is correct
4 Incorrect 169 ms 41384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 31060 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 4 ms 31064 KB Output is correct
4 Incorrect 169 ms 41384 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 31064 KB Output is correct
2 Correct 4 ms 31064 KB Output is correct
3 Correct 123 ms 48168 KB Output is correct
4 Correct 929 ms 52684 KB Output is correct
5 Correct 852 ms 41812 KB Output is correct
6 Correct 1084 ms 52684 KB Output is correct
7 Correct 777 ms 45924 KB Output is correct
8 Correct 982 ms 52696 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 3 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 -