oj.uz

Submission #978830

# Submission time Handle Problem Language Result Execution time Memory
978830 2024-05-09T18:27:01 Z Mher777 Rainforest Jumps (APIO21_jumps) C++17
23 / 100
 815 ms 101952 KB 
#include "jumps.h"
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <iomanip>
#include <array>
#include <string>
#include <algorithm>
#include <cmath>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <bitset>
#include <list>
#include <iterator>
#include <numeric>
#include <complex>
#include <utility>
#include <random>
#include <cassert>
#include <fstream>
using namespace std;
mt19937 rnd(7069);

/* -------------------- Typedefs -------------------- */

typedef int itn;
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
typedef float fl;
typedef long double ld;

/* -------------------- Usings -------------------- */

using vi = vector<int>;
using vll = vector<ll>;
using mii = map<int, int>;
using mll = map<ll, ll>;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

/* -------------------- Defines -------------------- */

#define ff first
#define ss second
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mpr make_pair
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define all(x) (x).begin(), (x).end()
#define USACO freopen("feast.in", "r", stdin); freopen("feast.out", "w", stdout);

/* -------------------- Constants -------------------- */

const int dx[8] = { -1, 0, 1, 0, -1, -1, 1, 1 };
const int dy[8] = { 0, -1, 0, 1, -1, 1, -1, 1 };
const int MAX = int(2e9 + 5);
const ll MAXL = ll(1e18) + 5ll;
const ll MOD = ll(1000000007);
const ll MOD2 = ll(998244353);

const int N = 200005, M = 30;
int a[N], dpl[N], dpr[N], tol[N], toh[N], upl[N][M], uph[N][M];
pii st[N][M];
int n, l1, r1, l2, r2, lg;

pii qry_max(int l, int r) {
	int lgx = log2(r - l + 1);
	return max(st[l][lgx], st[r - (1 << lgx) + 1][lgx]);
}

void init(int N, std::vector<int> H) {
	n = N;
	lg = log2(n);
	vector<pii> v;
	for (int i = 0; i < n; ++i) {
		a[i + 1] = H[i];
		st[i + 1][0] = { a[i + 1],i + 1 };
		v.pub({ a[i + 1],i + 1 });
	}
	for (int l = 1; l <= lg; ++l) {
		for (int i = 1; (i + (1 << l) - 1) <= n; ++i) {
			st[i][l] = max(st[i][l - 1], st[i + (1 << (l - 1))][l - 1]);
		}
	}
	sort(all(v));
	reverse(all(v));
	for (int i = 1; i <= n; ++i) {
		int ind = i - 1;
		while (ind && a[ind] <= a[i]) {
			ind = dpl[ind];
		}
		dpl[i] = ind;
	}
	for (int i = n; i >= 1; --i) {
		int ind = i + 1;
		while (ind <= n && a[ind] <= a[i]) {
			ind = dpr[ind];
		}
		dpr[i] = ind;
		if (dpl[i] != 0 && dpr[i] != n + 1) {
			tol[i] = dpl[i];
			toh[i] = dpr[i];
			if (a[dpl[i]] > a[dpr[i]]) {
				swap(tol[i], toh[i]);
			}
		}
		else if (dpl[i]) {
			tol[i] = dpl[i];
			toh[i] = MAX;
		}
		else if (dpr[i] != n + 1) {
			tol[i] = dpr[i];
			toh[i] = MAX;
		}
		else {
			tol[i] = toh[i] = MAX;
		}
	}
	for (auto elem : v) {
		int ind = elem.ss;
		if (tol[ind] == MAX) {
			for (int l = 0; l <= lg; ++l) {
				upl[ind][l] = uph[ind][l] = MAX;
			}
			continue;
		}
		upl[ind][0] = tol[ind];
		for (int l = 1; l <= lg; ++l) {
			if (upl[ind][l - 1] == MAX) {
				upl[ind][l] = MAX;
				continue;
			}
			upl[ind][l] = upl[upl[ind][l - 1]][l - 1];
		}
		if (toh[ind] == MAX) {
			for (int l = 0; l <= lg; ++l) {
				uph[ind][l] = MAX;
			}
			continue;
		}
		uph[ind][0] = toh[ind];
		for (int l = 1; l <= lg; ++l) {
			if (uph[ind][l - 1] == MAX) {
				uph[ind][l] = MAX;
				continue;
			}
			uph[ind][l] = uph[uph[ind][l - 1]][l - 1];
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	++A, ++B, ++C, ++D;
	l1 = A, r1 = B, l2 = C, r2 = D;
	int ind = -1;
	int lx = l1, rx = r1;
	while (lx <= rx) {
		int mid = (lx + rx) / 2;
		pii p = qry_max(mid, rx);
		if (p.ff > a[l2]) {
			lx = mid + 1;
		}
		else {
			ind = p.ss;
			rx = mid - 1;
		}
	}
	if (ind == -1) return -1;
	int h = a[l2];
	int ans = 0;
	for (int l = lg; l >= 0; --l) {
		if (uph[ind][l] == MAX) continue;
		if (a[uph[ind][l]] <= h) {
			ind = uph[ind][l];
			ans += (1 << l);
		}
	}
	for (int l = lg; l >= 0; --l) {
		if (upl[ind][l] == MAX) continue;
		if (a[upl[ind][l]] <= h) {
			ind = upl[ind][l];
			ans += (1 << l);
		}
	}
	if (a[ind] != h) return -1;
	return ans;
}

/*
7 100
3 2 1 6 4 5 7
4 4 6 6
1 3 5 6
0 1 2 2
*/

Subtask #1
0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Incorrect 140 ms 88160 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 8788 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 8536 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
23.0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8532 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 167 ms 55852 KB Output is correct
5 Correct 782 ms 101548 KB Output is correct
6 Correct 449 ms 25808 KB Output is correct
7 Correct 701 ms 101420 KB Output is correct
8 Correct 475 ms 43124 KB Output is correct
9 Correct 710 ms 101416 KB Output is correct
10 Correct 723 ms 101520 KB Output is correct
11 Correct 747 ms 101436 KB Output is correct
12 Correct 718 ms 101420 KB Output is correct
13 Correct 768 ms 101420 KB Output is correct
14 Correct 737 ms 101560 KB Output is correct
15 Correct 633 ms 101520 KB Output is correct
16 Correct 613 ms 101512 KB Output is correct
17 Correct 1 ms 8536 KB Output is correct
18 Correct 1 ms 8536 KB Output is correct
19 Correct 2 ms 8536 KB Output is correct
20 Correct 2 ms 8536 KB Output is correct
21 Correct 2 ms 8536 KB Output is correct
22 Correct 3 ms 8536 KB Output is correct
23 Correct 2 ms 8684 KB Output is correct
24 Correct 2 ms 8536 KB Output is correct
25 Correct 1 ms 8696 KB Output is correct
26 Correct 2 ms 10840 KB Output is correct
27 Correct 12 ms 10840 KB Output is correct
28 Correct 10 ms 11092 KB Output is correct
29 Correct 10 ms 10840 KB Output is correct
30 Correct 10 ms 10840 KB Output is correct
31 Correct 9 ms 10840 KB Output is correct
32 Correct 1 ms 8536 KB Output is correct
33 Correct 64 ms 66664 KB Output is correct
34 Correct 142 ms 101476 KB Output is correct
35 Correct 81 ms 101416 KB Output is correct
36 Correct 120 ms 101432 KB Output is correct
37 Correct 116 ms 101412 KB Output is correct
38 Correct 77 ms 101532 KB Output is correct

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8532 KB Output is correct
3 Correct 1 ms 8536 KB Output is correct
4 Correct 167 ms 55852 KB Output is correct
5 Correct 782 ms 101548 KB Output is correct
6 Correct 449 ms 25808 KB Output is correct
7 Correct 701 ms 101420 KB Output is correct
8 Correct 475 ms 43124 KB Output is correct
9 Correct 710 ms 101416 KB Output is correct
10 Correct 723 ms 101520 KB Output is correct
11 Correct 747 ms 101436 KB Output is correct
12 Correct 718 ms 101420 KB Output is correct
13 Correct 768 ms 101420 KB Output is correct
14 Correct 737 ms 101560 KB Output is correct
15 Correct 633 ms 101520 KB Output is correct
16 Correct 613 ms 101512 KB Output is correct
17 Correct 1 ms 8536 KB Output is correct
18 Correct 1 ms 8536 KB Output is correct
19 Correct 2 ms 8536 KB Output is correct
20 Correct 2 ms 8536 KB Output is correct
21 Correct 2 ms 8536 KB Output is correct
22 Correct 3 ms 8536 KB Output is correct
23 Correct 2 ms 8684 KB Output is correct
24 Correct 2 ms 8536 KB Output is correct
25 Correct 1 ms 8696 KB Output is correct
26 Correct 2 ms 10840 KB Output is correct
27 Correct 12 ms 10840 KB Output is correct
28 Correct 10 ms 11092 KB Output is correct
29 Correct 10 ms 10840 KB Output is correct
30 Correct 10 ms 10840 KB Output is correct
31 Correct 9 ms 10840 KB Output is correct
32 Correct 1 ms 8536 KB Output is correct
33 Correct 64 ms 66664 KB Output is correct
34 Correct 142 ms 101476 KB Output is correct
35 Correct 81 ms 101416 KB Output is correct
36 Correct 120 ms 101432 KB Output is correct
37 Correct 116 ms 101412 KB Output is correct
38 Correct 77 ms 101532 KB Output is correct
39 Correct 1 ms 8536 KB Output is correct
40 Correct 1 ms 8536 KB Output is correct
41 Correct 1 ms 8536 KB Output is correct
42 Correct 180 ms 55692 KB Output is correct
43 Correct 768 ms 101420 KB Output is correct
44 Correct 422 ms 25788 KB Output is correct
45 Correct 724 ms 101436 KB Output is correct
46 Correct 400 ms 42956 KB Output is correct
47 Correct 695 ms 101952 KB Output is correct
48 Correct 739 ms 101604 KB Output is correct
49 Correct 815 ms 101440 KB Output is correct
50 Correct 753 ms 101312 KB Output is correct
51 Correct 739 ms 101424 KB Output is correct
52 Correct 766 ms 101424 KB Output is correct
53 Correct 630 ms 101420 KB Output is correct
54 Correct 616 ms 101420 KB Output is correct
55 Correct 2 ms 8536 KB Output is correct
56 Incorrect 176 ms 101428 KB Output isn't correct
57 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Incorrect 140 ms 88160 KB Output isn't correct
4 Halted 0 ms 0 KB -