oj.uz

Submission #83494

# Submission time Handle Problem Language Result Execution time Memory
83494 2018-11-08T11:51:39 Z Noam527 Studentsko (COCI14_studentsko) C++17
100 / 100
 7 ms 2404 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 644 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 764 KB Output is correct
2 Correct 2 ms 836 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 900 KB Output is correct
2 Correct 2 ms 904 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1332 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1348 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1672 KB Output is correct
2 Correct 5 ms 1672 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1784 KB Output is correct
2 Correct 5 ms 1796 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 1976 KB Output is correct
2 Correct 5 ms 2028 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 2072 KB Output is correct
2 Correct 5 ms 2124 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 2228 KB Output is correct
2 Correct 5 ms 2404 KB Output is correct