제출 #672850

#제출 시각아이디문제언어결과실행 시간메모리
672850ParsaSThe short shank; Redemption (BOI21_prison)C++17
80 / 100
2093 ms285316 KiB
// In the name of God #pragma GCC optimize("Ofast", "unroll-loops") #include<bits/stdc++.h> using namespace std; #define pb push_back #define fi first #define se second #define mp make_pair typedef long long ll; const int N = 2e6 + 5, M = 4194310; int n, D, T; int t[N], L[N]; bool vis[N]; vector<int> vec[M]; int seg[M], mx[M], lz[M]; void shift(int v, int tl, int tr) { mx[v] += lz[v]; if (tl < tr) { lz[v << 1] += lz[v]; lz[v << 1 | 1] += lz[v]; } lz[v] = 0; } void upd(int l, int r, int val, int v = 1, int tl = 0, int tr = n - 1) { shift(v, tl, tr); if (l > tr || r < tl) return; if (tl >= l && tr <= r) { lz[v] += val; shift(v, tl, tr); return; } int mid = (tl + tr) >> 1; upd(l, r, val, v << 1, tl, mid); upd(l, r, val, v << 1 | 1, mid + 1, tr); mx[v] = max(mx[v << 1], mx[v << 1 | 1]); if (mx[v] == mx[v << 1]) seg[v] = seg[v << 1]; else seg[v] = seg[v << 1 | 1]; } void add(int i, int r, int v = 1, int tl = 0, int tr = n - 1) { if (tl == tr && tl == i) { vec[v].pb(r); return; } int mid = (tl + tr) >> 1; if (i <= mid) add(i, r, v << 1, tl, mid); else add(i, r, v << 1 | 1, mid + 1, tr); } void buildSeg(int v = 1, int tl = 0, int tr = n - 1) { seg[v] = tl; if (tl == tr) return; int mid = (tl + tr) >> 1; buildSeg(v << 1, tl, mid); buildSeg(v << 1 | 1, mid + 1, tr); } void build(int v = 1, int tl = 0, int tr = n - 1) { if (tl == tr) { sort(vec[v].begin(), vec[v].end()); vec[v].shrink_to_fit(); return; } int mid = (tl + tr) >> 1; build(v << 1, tl, mid); build(v << 1 | 1, mid + 1, tr); int l = 0, r = 0; int lc = v << 1, rc = v << 1 | 1; while (l < (int)vec[lc].size() && vec[lc][l] < tr) l++; while (r < (int)vec[rc].size() && vec[rc][r] < tr) r++; while (l < (int)vec[lc].size() && r < (int)vec[rc].size()) { if (vec[lc][l] <= vec[rc][r]) { vec[v].pb(vec[lc][l++]); l++; } else vec[v].pb(vec[rc][r++]); } while (l < (int)vec[lc].size()) vec[v].pb(vec[lc][l++]); while (r < (int)vec[rc].size()) vec[v].pb(vec[rc][r++]); vec[v].shrink_to_fit(); } void rem(int r, int v = 1, int tl = 0, int tr = n - 1) { if (tr <= r) { while (!vec[v].empty() && vec[v].back() >= r) { int u = vec[v].back(); vec[v].pop_back(); if (!vis[u]) { upd(L[u], u, -1); vis[u] = true; } } vec[v].shrink_to_fit(); return; } int mid = (tl + tr) >> 1; rem(r, v << 1, tl, mid); if (r > mid) rem(r, v << 1 | 1, mid + 1, tr); } void solve() { cin >> n >> D >> T; for (int i = 0; i < n; i++) cin >> t[i]; vector<int> st; int ans = 0; buildSeg(); for (int i = 0; i < n; i++) { while (!st.empty() && (t[st.back()] >= t[i] || t[st.back()] + i - st.back() > T)) st.pop_back(); if (!st.empty() && t[i] > T) { // st.top(), i - 1 L[i - 1] = st.back(); add(st.back(), i - 1); upd(st.back(), i - 1, 1); } else ans += t[i] > T; st.pb(i); } build(); while (D--) { shift(1, 0, n - 1); int i = seg[1]; ans += mx[1]; rem(i); } cout << n - ans << '\n'; } int32_t main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); solve(); 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...