oj.uz

Submission #978858

# Submission time Handle Problem Language Result Execution time Memory
978858 2024-05-09T19:58:03 Z Mher777 Rainforest Jumps (APIO21_jumps) C++17
0 / 100
 237 ms 105924 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], id[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) {
	if (r < l) return { 0,0 };
	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;
	set<int> s;
	mii pox;
	for (int i = 0; i < n; ++i) {
		a[i + 1] = H[i];
		s.insert(a[i + 1]);
	}
	int cur = 0;
	for (auto elem : s) {
		pox[elem] = ++cur;
	}
	for (int i = 1; i <= n; ++i) {
		a[i] = pox[a[i]];
		id[a[i]] = i;
		st[i][0] = { a[i],i };
		v.pub({ a[i],i });
	}
	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 h = qry_max(l2, r2).ff;
	int lx = l1, rx = r1, ind = -1, ans = 0;
	while (lx <= rx) {
		int mid = (lx + rx) / 2;
		pii p = qry_max(mid, r1);
		if (p.ff > h) {
			lx = mid + 1;
		}
		else {
			ind = p.ss;
			rx = mid - 1;
		}
	}
	if (ind == -1) return -1;
	if (r1 + 1 > l2 - 1) return 1;
	int hx = qry_max(r1 + 1, l2 - 1).ff;
	if (hx > h) return -1;
	if (hx < a[ind]) return 1;
	int answ = MAX;
	for (int l = lg; l >= 0; --l) {
		if (uph[ind][l] == MAX) continue;
		if (a[uph[ind][l]] >= hx) {
			answ = min(answ, ans + (1 << l) + 1);
			continue;
		}
		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]] >= hx) {
			answ = min(answ, ans + (1 << l) + 1);
		}
		ind = upl[ind][l];
		ans += (1 << l);
	}
	return min(ans + 2, answ);
}

/*
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 235 ms 103644 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 8.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 Correct 2 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Incorrect 2 ms 8536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 13.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 Correct 2 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Incorrect 2 ms 8536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 12.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 Correct 1 ms 8536 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Incorrect 229 ms 105924 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 23.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 Correct 1 ms 8536 KB Output is correct
4 Incorrect 237 ms 64632 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.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 Correct 1 ms 8536 KB Output is correct
4 Incorrect 237 ms 64632 KB Output isn't correct
5 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 235 ms 103644 KB Output isn't correct
4 Halted 0 ms 0 KB -