oj.uz

Submission #978845

# Submission time Handle Problem Language Result Execution time Memory
978845 2024-05-09T18:55:47 Z Mher777 Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 1061 ms 120924 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) {
	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;
	for (int l = lg; l >= 0; --l) {
		if (uph[ind][l] == MAX) continue;
		if (uph[ind][l] > h) continue;
		int old = l;
		while (l >= 0) {
			if (id[uph[ind][l]] < l2) {
				ind = uph[ind][l];
				ans += (1 << l);
				l = lg;
				break;
			}
			--l;
		}
		if (l != -1) continue;
		return ans + 1;
	}
	for (int l = lg; l >= 0; --l) {
		if (upl[ind][l] == MAX) continue;
		if (upl[ind][l] > h) continue;
		int old = l;
		while (l >= 0) {
			if (id[upl[ind][l]] < l2) {
				ind = upl[ind][l];
				ans += (1 << l);
				l = lg;
				break;
			}
			--l;
		}
		if (l != -1) continue;
		return ans + 1;
	}
	return -1;
}

/*
10 100
1 2 3 4 5 6 7 8 9 10
1 2 4 5
*/

Compilation message

jumps.cpp: In function 'int minimum_jumps(int, int, int, int)':
jumps.cpp:192:7: warning: unused variable 'old' [-Wunused-variable]
  192 |   int old = l;
      |       ^~~
jumps.cpp:208:7: warning: unused variable 'old' [-Wunused-variable]
  208 |   int old = l;
      |       ^~~

Subtask #1
4.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 Correct 223 ms 103816 KB Output is correct
4 Correct 1061 ms 120876 KB Output is correct
5 Correct 752 ms 69880 KB Output is correct
6 Correct 988 ms 120924 KB Output is correct
7 Correct 796 ms 90676 KB Output is correct
8 Correct 1026 ms 120900 KB Output is correct

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 1 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 1 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 223 ms 106136 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 236 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 236 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 Correct 223 ms 103816 KB Output is correct
4 Correct 1061 ms 120876 KB Output is correct
5 Correct 752 ms 69880 KB Output is correct
6 Correct 988 ms 120924 KB Output is correct
7 Correct 796 ms 90676 KB Output is correct
8 Correct 1026 ms 120900 KB Output is correct
9 Correct 1 ms 8536 KB Output is correct
10 Correct 1 ms 8536 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 1 ms 8536 KB Output is correct
13 Incorrect 2 ms 8536 KB Output isn't correct
14 Halted 0 ms 0 KB -