Submission #523481

#TimeUsernameProblemLanguageResultExecution timeMemory
523481blueStudentsko (COCI14_studentsko)C++17
0 / 100
5 ms708 KiB
#include <iostream> #include <map> #include <vector> #include <algorithm> #include <numeric> using namespace std; int* v; using vi = vector<int>; int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); int N, K; cin >> N >> K; map<int, int> ct; v = new int[1+N]; for(int i = 1; i <= N; i++) { cin >> v[i]; ct[v[i]] = 0; } int x = -1; for(auto& z : ct) z.second = ++x; for(int i = 1; i <= N; i++) v[i] = ct[v[i]] / K; vi BIT(1+N, 0); vi I(N); iota(I.begin(), I.end(), 1); sort(I.begin(), I.end(), [] (int p, int q) { if(v[p] == v[q]) return p < q; else return v[p] < v[q]; }); int res = N; for(int i : I) { int curr = 1; for(int j = i-1; j >= 1; j -= j&-j) curr = max(BIT[i], BIT[j] + 1); res = min(res, N - curr); for(int j = i; j <= N; j += j&-j) BIT[j] = max(BIT[j], curr); } cout << res << '\n'; }
#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...