Submission #577148

#TimeUsernameProblemLanguageResultExecution timeMemory
577148MilosMilutinovicStudentsko (COCI14_studentsko)C++14
100 / 100
3 ms468 KiB
#include <bits/stdc++.h> using namespace std; template <typename T> class fenwick { public: vector<T> fenw; int n; fenwick(int _n) : n(_n) { fenw.resize(n); } void modify(int x, T v) { while (x < n) { fenw[x] += v; x |= (x + 1); } } T get(int x) { T v{}; while (x >= 0) { v += fenw[x]; x = (x & (x + 1)) - 1; } return v; } }; struct node { int a = 0; // don't forget to set default value inline void operator += (node &other) { a = max(a, other.a); } }; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) { cin >> a[i]; } vector<int> order(n); iota(order.begin(), order.end(), 0); sort(order.begin(), order.end(), [&](int i, int j) { return a[i] > a[j]; }); vector<int> id(n); for (int i = 0; i < n; i++) { id[order[i]] = i / k; } sort(order.begin(), order.end(), [&](int i, int j) { if (id[i] == id[j]) { return i < j; } else { return a[i] < a[j]; } }); for (int i = 0; i < n; i++) { id[order[i]] = i; } fenwick<node> fenw(n); vector<int> dp(n); for (int i = 0; i < n; i++) { dp[i] = fenw.get(id[i]).a + 1; fenw.modify(id[i], {dp[i]}); } cout << n - *max_element(dp.begin(), dp.end()) << '\n'; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...