oj.uz

Submission #526321

# Submission time Handle Problem Language Result Execution time Memory
526321 2022-02-14T10:25:00 Z Vladithur Rainforest Jumps (APIO21_jumps) C++17
4 / 100
 3044 ms 40828 KB 
#include "jumps.h"
#include <bits/stdc++.h>
using namespace std;

const int maxn = 200001, logn = 20;
int t[maxn * 4], t2[maxn * 4], up[maxn][logn], up2[maxn][logn];
vector<int> h;

void update(int v, int tl, int tr, int i, int x) {
	if (tl == tr - 1) {
		t[v] = x;
		t2[v] = tl;
	} else {
		int tm = (tl + tr) / 2;
		if (i < tm) update(2*v + 1, tl, tm, i, x);
		else update(2*v + 2, tm, tr, i, x);
		t[v] = max(t[2*v + 1], t[2*v + 2]);
		if (t[2*v + 1] > t[2*v + 2]) t2[v] = t2[2*v + 1];
		else t2[v] = t2[2*v + 2];
	}
}

pair<int, int> query(int v, int tl, int tr, int l, int r) {
	if (l >= r) return {0, 0};
	else if (tl == l && tr == r) return {t[v], t2[v]};
	else {
		int tm = (tl + tr) / 2;
		auto r1 = query(2*v + 1, tl, tm, l, min(r, tm));
		return max(r1, query(2*v + 2, tm, tr, max(l, tm), r));
	}
}
	
	
int n;

void init(int N, std::vector<int> H) {
	n = N;
	h = H;
	n++;
	h.push_back(n + 1);
	for (int i = 0; i < n; i++) update(0, 0, n, i, h[i]);
	vector<pair<int, int>> b;
	for (int i = 0; i < n; i++) b.emplace_back(h[i], i);
	sort(b.rbegin(), b.rend());
	for (auto tp: b) {
		int i = tp.second;
		int g1 = i, g2 = i;
		
		{
			int lb = 0, ub = i - 1;
			while (lb <= ub) {
				int tm = (lb + ub) / 2;
				auto r = query(0, 0, n, tm, i + 1);
				if (r.second != i) {
					g1 = r.second;
					lb = tm + 1;
				} else {
					ub = tm - 1;
				}
			}
		}
		
		{
			int lb = i + 1, ub = n - 1;
			while (lb <= ub) {
				int tm = (lb + ub) / 2;
				auto r = query(0, 0, n, i, tm + 1);
				if (r.second != i) {
					g2 = r.second;
					ub = tm - 1;
				} else {
					lb = tm + 1;
				}
			}
		}
		
		if (h[g2] > h[g1]) swap(g2, g1);
		
		if (g1 == i) g1 = n - 1;
		if (g2 == i) g2 = n - 1;
		
		up[i][0] = g1;
		up2[i][0] = g2;
		for (int j = 1; j < logn; j++) {
			up[i][j] = up[up[i][j - 1]][j - 1];
			up2[i][j] = up2[up2[i][j - 1]][j - 1];
		}
	}
}

int minimum_jumps(int A, int B, int C, int D) {
	
	int x = query(0, 0, n, C, D + 1).first;
	int y = query(0, 0, n, B + 1, C).first;
	if (y >= x) return -1;
	
	int lb = A, ub = B, tans = -1;
	while (lb <= ub) {
		int tm = (lb + ub) / 2;
		if (query(0, 0, n, tm, B + 1).first < x) {
			tans = tm;
			ub = tm - 1;
		} else {
			lb = tm + 1;
		}
	}
	
	if (tans == -1) return -1;
	int v = query(0, 0, n, tans, B + 1).second;
	
	int ans = 0;
	
	for (int i = logn - 1; i >= 0; i--) {
		if (h[up[v][i]] <= y) {
			v = up[v][i];
			ans += (1 << i);
		}
	}
	if (h[v] < y && up[v][0] <= y) {
		ans++;
		v = up[v][0];
	}
	
	//cout << v << ' ' << ans << endl;
	
	if (h[up[v][0]] < x) {
		return ans + 1;
	}
	
	for (int i = logn - 1; i >= 0; i--) {
		if (h[up2[v][i]] <= y) {
			v = up2[v][i];
			ans += (1 << i);
		}
	}
	
	if (h[v] < y && up2[v][0] <= y) {
		ans++;
		v = up2[v][0];
	}
	
	return ans + 1;
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1266 ms 33576 KB Output is correct
4 Correct 3044 ms 40800 KB Output is correct
5 Correct 1917 ms 20656 KB Output is correct
6 Correct 2860 ms 40712 KB Output is correct
7 Correct 1981 ms 28624 KB Output is correct
8 Correct 2864 ms 40760 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Incorrect 3 ms 328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 2 ms 200 KB Output is correct
6 Incorrect 3 ms 328 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 0 ms 200 KB Output is correct
4 Correct 0 ms 200 KB Output is correct
5 Correct 1488 ms 33764 KB Output is correct
6 Correct 1917 ms 40648 KB Output is correct
7 Correct 839 ms 20872 KB Output is correct
8 Correct 1894 ms 40652 KB Output is correct
9 Correct 190 ms 6204 KB Output is correct
10 Correct 1900 ms 40620 KB Output is correct
11 Correct 1462 ms 40616 KB Output is correct
12 Incorrect 1474 ms 40828 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Incorrect 956 ms 18900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1 ms 200 KB Output is correct
4 Incorrect 956 ms 18900 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 200 KB Output is correct
2 Correct 0 ms 200 KB Output is correct
3 Correct 1266 ms 33576 KB Output is correct
4 Correct 3044 ms 40800 KB Output is correct
5 Correct 1917 ms 20656 KB Output is correct
6 Correct 2860 ms 40712 KB Output is correct
7 Correct 1981 ms 28624 KB Output is correct
8 Correct 2864 ms 40760 KB Output is correct
9 Correct 0 ms 200 KB Output is correct
10 Correct 0 ms 200 KB Output is correct
11 Correct 0 ms 200 KB Output is correct
12 Correct 0 ms 200 KB Output is correct
13 Correct 2 ms 200 KB Output is correct
14 Incorrect 3 ms 328 KB Output isn't correct
15 Halted 0 ms 0 KB -