제출 #1208884

#제출 시각아이디문제언어결과실행 시간메모리
1208884aykhnThe short shank; Redemption (BOI21_prison)C++20
80 / 100
2101 ms129924 KiB
#include<bits/stdc++.h> using namespace std; const int MXN = 2e6 + 5; const int LOG = 20; int n, D, T, res; int arr[MXN], L[MXN], val[MXN]; array<int, 2> mx[MXN]; vector<int> adj[MXN]; void dfs(int a, int w) { mx[a] = {w, a}; for (int &v : adj[a]) { dfs(v, w + 1); mx[a] = max(mx[a], mx[v]); } val[mx[a][1]]++; } void _() { cin >> n >> D >> T; res = n; for (int i = 1; i <= n; i++) cin >> arr[i]; { multiset<array<int, 2>> ms; multiset<int> mx; for (int i = 1; i <= n; i++) { ms.insert({arr[i] - i, i}); mx.insert(i); while (!ms.empty() && T - i < (*ms.rbegin())[0]) { mx.erase(mx.find((*ms.rbegin())[1])); ms.erase(prev(ms.end())); } if (!mx.empty()) L[i] = *mx.rbegin(); } } vector<int> v; for (int i = 1; i <= n; i++) { if (!L[i]) { res--; continue; } if (L[i] == i) continue; while (!v.empty() && L[v.back()] >= L[i]) { adj[i].push_back(v.back()); v.pop_back(); } v.push_back(i); } for (int &i : v) dfs(i, 0); sort(val + 1, val + n + 1, greater<int>()); for (int i = 1; i <= D; i++) res -= val[i]; cout << res << '\n'; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; while (t--) _(); }
#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...