제출 #894504

#제출 시각아이디문제언어결과실행 시간메모리
894504d4xnThe short shank; Redemption (BOI21_prison)C++17
0 / 100
25 ms54876 KiB
#include <bits/stdc++.h> using namespace std; const int N = 5e5; int n, d, t, a[N], b[N]; vector<int> add[N], rem[N]; signed main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin >> n >> d >> t; for (int i = 0; i < n; i++) { cin >> a[i]; if (a[i] > t) continue; add[i].push_back(i); rem[min(n, i + t-a[i] + 1)].push_back(i); } int ans = 0; set<int> st; for (int i = 0; i < n; i++) { for (int& j : add[i]) st.insert(j); for (int& j : rem[i]) st.erase(j); if (a[i] <= t) { b[i] = -1; continue; } if (st.empty()) { b[i] = -1; ans++; } else b[i] = *prev(st.end()); } int mx = 0; st.clear(); for (int i = n-1; i >= 0; i--) { while (!st.empty() && *prev(st.end()) > i) { st.erase(st.end()); } int sz = st.size(); mx = max(mx, sz); if (b[i] != -1) st.insert(b[i]); } cout << n - ans - mx << "\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...