oj.uz

Submission #645482

# Submission time Handle Problem Language Result Execution time Memory
645482 2022-09-27T08:22:02 Z baojiaopisu Rainforest Jumps (APIO21_jumps) C++14
4 / 100
 1148 ms 63920 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using ull = unsigned long long;

using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pld = pair<ld, ld>;

#define fi first
#define se second
#define pb push_back
#define pf push_front
#define mp make_pair
#define ins insert
#define btpc __builtin_popcount
#define btclz __builtin_clz

#define sz(x) (int)(x.size());
#define all(x) x.begin(), x.end()
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

template<class X, class Y>
    bool minimize(X &x, const Y &y) {
        if (x > y)
        {
            x = y;
            return true;
        }
        return false;
    }
template<class X, class Y>
    bool maximize(X &x, const Y &y) {
        if (x < y)
        {
            x = y;
            return true;
        }
        return false;
    }

const int MOD = 1e9 + 7; //998244353

template<class X, class Y>
	void add(X &x, const Y &y) {
		x = (x + y);
		if(x >= MOD) x -= MOD;
	}

template<class X, class Y> 
	void sub(X &x, const Y &y) {
		x = (x - y);
		if(x < 0) x += MOD;
	}

/* Author : Le Ngoc Bao Anh, 12A5, LQD High School for Gifted Student*/

const ll INF = 1e9;
const int N = 2e5 + 10;
const int LOG = 17;

pii f[N][LOG + 2];
int jump[N][LOG + 2], jr[N][LOG + 2];
int a[N], L[N], R[N];

void init(int n, vector<int> aa) {
	for(int i = 1; i <= n; i++) {
		a[i] = aa[i - 1];
		f[i][0] = mp(aa[i - 1], i);
	}

	for(int j = 1; j <= LOG; j++) {
		for(int i = 1; i <= n - (1 << j) + 1; i++) {
			int u = i + (1 << (j - 1));
			f[i][j].se = (f[i][j - 1].fi > f[u][j - 1].fi ? f[i][j - 1].se : f[u][j - 1].se);
			f[i][j].fi = max(f[i][j - 1].fi, f[u][j - 1].fi);
		}
	}

	stack<int> st;
	for(int i = 1; i <= n; i++) {
		while(!st.empty() && a[st.top()] <= a[i]) st.pop();
		if(!st.empty()) L[i] = st.top();
		st.push(i);
	}

	while(!st.empty()) st.pop();

	for(int i = n; i >= 1; i--) {
		while(!st.empty() && a[st.top()] <= a[i]) st.pop();
		if(!st.empty()) R[i] = st.top();
		st.push(i);
	}

	for(int i = 1; i <= n; i++) {
		jump[i][0] = (a[L[i]] > a[R[i]] ? L[i] : R[i]);
		jr[i][0] = R[i];
	}

	for(int j = 1; j <= LOG; j++) {
		for(int i = 1; i <= n; i++) {
			int u = jump[i][j - 1];
			jump[i][j] = jump[u][j - 1];
			u = jr[i][j - 1];
			jr[i][j] = jr[u][j - 1];
		}
	}
}

pii query(int L, int R) {
	if(L > R) return mp(0, 0);
	int x = 31 - btclz(R - L + 1);
	if(f[L][x] > f[R - (1 << x) + 1][x]) return f[L][x];
	else return f[R - (1 << x) + 1][x];
}

int minimum_jumps(int l, int r, int u, int v) {
	++l; ++r; ++u; ++v;
	if(query(r + 1, u - 1).fi >= query(u, v).fi) return -1;
	int pos = -1;
	int L = l, R = r;
	while(L <= R) {
		int mid = (L + R) >> 1;
		if(query(mid, r).fi < query(u, v).fi) {
			pos = mid;
			R = mid - 1;
		} else L = mid + 1;
	}

	if(pos < 0) return -1;

	int ans = 0;
	pos = query(pos, r).se;

	for(int i = LOG; i >= 0; i--) {
		if(!jump[pos][i]) continue;
		if(a[jump[pos][i]] < query(r + 1, u - 1).fi) {
			pos = jump[pos][i];
			ans += (1 << i);
		}
	}

	if(jump[pos][0] && a[jump[pos][0]] <= query(r + 1, u - 1).fi) pos = jump[pos][0], ++ans;

	for(int i = LOG; i >= 0; i--) {
		if(jr[pos][i] && jr[pos][i] < u) {
			pos = jr[pos][i];
			ans += (1 << i);
		}
	}

	return ans + (pos < u);
}

Subtask #1
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 211 ms 50720 KB Output is correct
4 Correct 1148 ms 63644 KB Output is correct
5 Correct 1026 ms 32268 KB Output is correct
6 Correct 1102 ms 63688 KB Output is correct
7 Correct 938 ms 43668 KB Output is correct
8 Correct 1008 ms 63688 KB Output is correct

Subtask #2
0 / 8.0

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

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 2 ms 336 KB Output is correct
6 Incorrect 3 ms 336 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 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Correct 0 ms 336 KB Output is correct
5 Correct 91 ms 51244 KB Output is correct
6 Correct 137 ms 63680 KB Output is correct
7 Correct 63 ms 32664 KB Output is correct
8 Correct 124 ms 63804 KB Output is correct
9 Correct 10 ms 9884 KB Output is correct
10 Correct 122 ms 63708 KB Output is correct
11 Correct 107 ms 63688 KB Output is correct
12 Correct 121 ms 63920 KB Output is correct
13 Incorrect 118 ms 63644 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Incorrect 297 ms 29216 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 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Correct 0 ms 336 KB Output is correct
4 Incorrect 297 ms 29216 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 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 211 ms 50720 KB Output is correct
4 Correct 1148 ms 63644 KB Output is correct
5 Correct 1026 ms 32268 KB Output is correct
6 Correct 1102 ms 63688 KB Output is correct
7 Correct 938 ms 43668 KB Output is correct
8 Correct 1008 ms 63688 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 0 ms 336 KB Output is correct
11 Correct 0 ms 336 KB Output is correct
12 Correct 0 ms 336 KB Output is correct
13 Correct 2 ms 336 KB Output is correct
14 Incorrect 3 ms 336 KB Output isn't correct
15 Halted 0 ms 0 KB -