| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1171546 | khangai11 | Studentsko (COCI14_studentsko) | C++20 | 0 ms | 0 KiB |
#include <iostream>
#include<string>
#include<algorithm>
#include<functional>
#include<cmath>
#include<queue>
#include<vector>
#include<map>
#include<stack>
#include<list>
#include<deque>
#include<set>
#include<unordered_set>
#include<unordered_map>
#include<numeric>
#include<bitset>
#include<iomanip>
#include<cstdlib>
#include<time.h>
#include <functional>
#include <chrono>
#include <thread>
#include <fstream>
#include <random>
using namespace std;
#ifdef _DEBUG
#define prnt(a) cout<<#a<<"="<<a<<endl
#else
#define prnt(a) (void)0
#endif // _DEBUG
#ifdef _MSC_VER
# include <intrin.h>
# define __builtin_popcount __popcnt
#endif
#define ull unsigned long long
#define ll long long
#define ld long double
#define INF (1LL<<30)
#define INFLL (1LL<<62)
#define MOD 1000000007
#define MOD2 998244353
#define rep(i,st,en) for(ll i=(st);i<(en);++i)
#define vld vector<ld>
#define vll vector<ll>
#define vvll vector<vll>
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vpii vector<pii>
#define vpll vector<pll>
#define VS vector<string>
#define MY_PI 3.141592653589793238462643383279502884L
#define all(v) (v).begin(), (v).end()
#define rd(...) __VA_ARGS__; read(__VA_ARGS__)
#define rdv(value,...) value(__VA_ARGS__);cin >> value
template <class T> auto& operator>>(istream& is, vector<T>& xs) {
for (auto& x : xs) is >> x;
return is;
}
template <class T> auto& operator<<(ostream& os, vector<T>& xs) {
int sz = xs.size();
rep(i, 0, sz) os << xs[i] << " \n"[i + 1 == sz];
return os;
}
template <class T, class Y> auto& operator<<(ostream& os, pair<T, Y>& xs) {
os << "{" << xs.first << ", " << xs.second << "}";
return os;
}
template <class T, class Y> auto& operator>>(istream& is, vector<pair<T, Y>>& xs) {
for (auto& [x1, x2] : xs) is >> x1 >> x2;
return is;
}
template <class ...Args>
auto& read(Args & ...args) { return (cin >> ... >> args); }
#define write(...) writemy(__VA_ARGS__);cout<<"\n"
void writemy() {}
template <typename Head, class ...Args>
void writemy(const Head& head, const Args & ...args) {
cout << head << " ";
writemy(args...);
}
class UnionFindTree {
public:
vector<ll> parent;
vector<ll> union_size;
vector<ll> w;
int len;
int nn;
ll value = 0;
UnionFindTree(int n) {
len = n;
nn = n;
parent.resize(n + 1, 0);
w.resize(n + 1, 0);
rep(i, 0, n + 1) {
w[i] = i;
}
union_size.resize(n + 1, 1);
value = 0;
rep(i, 0, n + 1) parent[i] = i;
}
ll root(int a) {
if (parent[a] == a)
return a;
parent[a] = root(parent[a]);
return parent[a];
}
void setWeight(int a, ll we) {
w[a] = we;
}
ll getWeight(int a) {
int ra = root(a);
return w[ra];
}
bool join(int a, int b) {
if (a<0 || a>nn) return false;
if (b<0 || b>nn) return false;
int ra = root(a);
int rb = root(b);
if (ra == rb)
return false;
if (ra > rb) {
parent[rb] = ra;
union_size[ra] += union_size[rb];
w[ra] ^= w[rb];
}
else {
parent[ra] = rb;
union_size[rb] += union_size[ra];
w[rb] ^= w[ra];
}
len--;
return true;
}
ll size(int a) {
return union_size[root(a)];
}
};
ll lis(vll& v, ll maxVal) {
int n = v.size();
vll dp(n, maxVal);
for (int i = 0; i < n; i++) {
//not acceptable same number
int x = (upper_bound(dp.begin(), dp.end(), v[i]) - dp.begin());
//accept same number
//int x = (lower_bound(dp.begin(), dp.end(), v[i]) - dp.begin());
dp[x] = v[i];
}
return (lower_bound(dp.begin(), dp.end(), maxVal) - dp.begin());
}
void findPrimeDividers(ll n, vpll& p) {
//vpll p;
ll ps = primes.size();
ll i = 0;
if (n == 1) {
p.emplace_back(1, 1);
return;
}
while (n > 1 && i < ps) {
if (n % primes[i] == 0) {
ll d = 0;
while (n % primes[i] == 0) {
d++;
n /= primes[i];
}
p.emplace_back(primes[i], d);
}
i++;
}
if (n > 1) {
p.emplace_back(n, 1);
}
}
void findDivisors(ll n, vll& divs) {
vpll p;
findPrimeDividers(n, p);
vll v(p.size(), 0);
findDiv(p, v, divs);
}
#define MOS_BLOCK 710
bool cmp(pll p, pll q) {
if (p.first / MOS_BLOCK != q.first / MOS_BLOCK)
return p < q;
return p.second < q.second;
}
void func_add(vll& mp, vll& a, ll ind, ll& sum) {
ll tmp = mp[a[ind]];
sum += (2 * tmp + 1) * a[ind];
mp[a[ind]]++;
}
void func_minus(vll& mp, vll& a, ll ind, ll& sum) {
ll tmp = mp[a[ind]];
tmp--;
sum -= (2 * tmp + 1) * a[ind];
mp[a[ind]]--;
}
//
//void solve_mos(int test) {
// ll rd(n, t);
// vll rdv(a, n);
// vpll rdv(q, t);
// map<pll, vll> mpq;
// rep(i, 0, t) {
// q[i].first--;
// q[i].second--;
// mpq[q[i]].push_back(i);
// }
// vll mp(1001001, 0);
// sort(all(q), cmp);
// vll ans(t);
// ll l = 0, r = 0;
// mp[a[l]]++;
// ll sum = a[l];
// rep(i, 0, t) {
// while (l > q[i].first) {
// l--;
// func_add(mp, a, l, sum);
// }
// while (r < q[i].second) {
// r++;
// func_add(mp, a, r, sum);
// }
// while (r > q[i].second) {
// func_minus(mp, a, r, sum);
// r--;
// }
// while (l < q[i].first) {
// func_minus(mp, a, l, sum);
// l++;
// }
// for (auto inde : mpq[q[i]])
// ans[inde] = sum;
// }
// rep(i, 0, t) {
// cout << ans[i] << "\n";
// }
//}
vll ps;
void siev(ll n) {
ps.resize(n + 1, 1);
for (int i = 2; i <= n; i++) {
if (ps[i] == 1) {
for (ll j = i; j <= n; j += i) {
if (ps[j] == 1)
ps[j] = i;
}
}
}
ps[1] = 0;
}
void solve(ll test) {
ll rd(n, k);
vll rdv(a, n);
vpll b(n);
rep(i, 0, n) {
b[i].first = a[i];
b[i].second = i;
}
sort(all(b));
vll c(n);
rep(i, 0, n) {
c[b[i].second] = i / k;
}
ll val = lis(c, INFLL);
cout << (n - val)<<"\n";
}
int main() {
//initFacts(100, MOD2);
//findPrimes(400000);
//freopen("four_in_a_burrow_input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test = 1;
//cin >> test;
for (int t = 1; t <= test; t++)
solve(t);
return 0;
}