oj.uz

Submission #948432

# Submission time Handle Problem Language Result Execution time Memory
948432 2024-03-18T05:55:03 Z brendonw Rabbit Carrot (LMIO19_triusis) C++17
0 / 100
 1 ms 348 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
using pll = pair<ll, ll>;
const ll MAX_A = 5e3;

template<typename T>
struct segtree {
	T size;
	vector<T> val;
	T id = 0;

	segtree(T n) {
		size = 1;
		while (size < n) {
			size *= 2;
		}
		val.assign(size * 2, id);
	}

	void update(T i, T v, T x, T lx, T rx) {
		if (rx - lx == 1) {
			val[x] = v;
			return;
		}
		T mid = (lx + rx) / 2;
		if (i < mid) {
			update(i, v, 2 * x + 1, lx, mid);
		} else {
			update(i, v, 2 * x + 2, mid, rx);
		}
		val[x] = max(val[2 * x + 1], val[2 * x + 2]);
	}

	void update(T i, T v) {
		update(i, v, 0, 0, size);
	}

	T query(T l, T r, T x, T lx, T rx) {
		if (r <= lx || l >= rx) {
			return id;
		}
		if (lx >= l && rx <= r) {
			return val[x];
		}
		T mid = (lx + rx) / 2;
		T calc1 = query(l, r, 2 * x + 1, lx, mid);
		T calc2 = query(l, r, 2 * x + 2, mid, rx);
		return max(calc1, calc2);
	}

	T query(T l, T r) {
		if (l > r) {
			return -1;
		}
		if (l == r) {
			return id;
		}
		return query(l, r, 0, 0, size);
	}
};


int solve() {
	ll n, m;
	cin >> n >> m;
	vector<ll> a(n);
	set<ll> heights;
	for (ll i = 0; i < n; ++i) {
		cin >> a[i];
		a[i] -= (i + 1) * m;
		heights.insert(a[i]);
	}
	heights.insert(0);
	ll cnt = 0;
	map<ll, ll> idx;
	for (ll i: heights) {
		if (!idx.count(i)) { idx[i] = ++cnt; }
	}
	segtree<ll> dp(idx.size() + 1);
	for (ll i = 0; i < n; ++i) {
		a[i] = idx[a[i]];
		ll max_prev = dp.query(a[i], idx[0]);
		dp.update(a[i], max_prev + 1);
	}

	cout << n - dp.query(0, idx.size() + 1);

	return 0;
}

#ifndef MY_UNIT_TEST

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	solve();
}

#endif

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Incorrect 0 ms 348 KB Output isn't correct
13 Halted 0 ms 0 KB -