oj.uz

답안 #973899

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
973899 2024-05-02T12:30:13 Z Syrius 밀림 점프 (APIO21_jumps) C++14
4 / 100
 992 ms 53604 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 && root->query(a , c-1 , inf).ff < hbef) 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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 31064 KB Output is correct
2 Correct 8 ms 31212 KB Output is correct
3 Correct 138 ms 48168 KB Output is correct
4 Correct 981 ms 52684 KB Output is correct
5 Correct 733 ms 41804 KB Output is correct
6 Correct 992 ms 52856 KB Output is correct
7 Correct 743 ms 45912 KB Output is correct
8 Correct 985 ms 52692 KB Output is correct

Subtask #2
0 / 8.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 Correct 4 ms 31064 KB Output is correct
5 Correct 5 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 4 ms 31064 KB Output is correct
3 Correct 3 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 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 3 ms 31064 KB Output is correct
3 Correct 5 ms 31064 KB Output is correct
4 Correct 5 ms 31064 KB Output is correct
5 Correct 46 ms 49192 KB Output is correct
6 Correct 50 ms 53436 KB Output is correct
7 Correct 25 ms 42836 KB Output is correct
8 Correct 55 ms 53604 KB Output is correct
9 Correct 11 ms 34388 KB Output is correct
10 Correct 49 ms 53436 KB Output is correct
11 Correct 43 ms 52848 KB Output is correct
12 Correct 37 ms 53200 KB Output is correct
13 Incorrect 37 ms 52928 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 168 ms 41260 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 168 ms 41260 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 8 ms 31212 KB Output is correct
3 Correct 138 ms 48168 KB Output is correct
4 Correct 981 ms 52684 KB Output is correct
5 Correct 733 ms 41804 KB Output is correct
6 Correct 992 ms 52856 KB Output is correct
7 Correct 743 ms 45912 KB Output is correct
8 Correct 985 ms 52692 KB Output is correct
9 Correct 4 ms 31064 KB Output is correct
10 Correct 4 ms 31064 KB Output is correct
11 Correct 3 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 4 ms 31064 KB Output isn't correct
15 Halted 0 ms 0 KB -