Submission #83494

#	Time	Username	Problem	Language	Result	Execution time	Memory
83494		Noam527	Studentsko (COCI14_studentsko)	C++17	100 / 100	7 ms	2404 KiB

studentsko

#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
#define endl '\n'
#define fast ios::sync_with_stdio(0), cin.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

int n, k;
vector<int> a;
map<int, int> m; int nxt = 0;

int calc() {
	vector<int> dp(n + 1, inf);
	dp[0] = -1;
	int L = 0, lo, hi, mid;
	for (auto &i : a) {
		lo = 0, hi = L + 1;
		while (lo < hi) {
			mid = (lo + hi) / 2;
			if (i < dp[mid]) hi = mid;
			else lo = mid + 1;
		}
		dp[lo] = i;
		L = max(L, lo);
	}
	return L;
}

int main() {
	fast;
	cin >> n >> k;
	a.resize(n);
	for (auto &i : a) cin >> i, m[i] = 0;
	for (auto &i : m) i.second = nxt++;
	for (auto &i : a) i = m[i] / k;
	cout << n - calc() << endl;
}

• Subtask 1: 10 / 10
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 10 / 10
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10