Submission #720831

#TimeUsernameProblemLanguageResultExecution timeMemory
720831JohannThe short shank; Redemption (BOI21_prison)C++14
0 / 100
133 ms11176 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pii pair<int, int> #define vb vector<bool> #define vi vector<int> #define vpii vector<pii> #define vvb vector<vb> #define vvi vector<vi> #define vvpii vector<vpii> #define sz(x) (int)(x).size() int N, D, T; vi P; struct segtree { int size; vi arr; void init(int n) { size = 1; while (size < n) size *= 2; arr.assign(2 * size, 0); } int query(int l, int r) { return query(l, r, 1, 0, size); } int query(int l, int r, int x, int lx, int rx) { if (l <= lx && rx <= r) return arr[x]; if (r <= lx || rx <= l) return 0; int m = (lx + rx) / 2; return query(l, r, 2 * x, lx, m) + query(l, r, 2 * x + 1, m, rx); } void block(int l, int r) { block(l, r, 1, 0, size); } void block(int l, int r, int x, int lx, int rx) { if (rx - lx == 1) arr[x] = 1; if (r <= lx || rx <= l || arr[x] == rx - lx) return; int m = (lx + rx) / 2; block(l, r, 2 * x, lx, m); block(l, r, 2 * x + 1, m, rx); arr[x] = arr[2 * x] + arr[2 * x + 1]; } }; int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> N >> D >> T; D = min(D, N); P.resize(N); for (int i = 0; i < N; ++i) cin >> P[i]; vi pref(N + 1, 0); // number of protestants in range [0, i) int border = -1; for (int i = 0; i < N; ++i) { border = max(border, i + T - P[i]); pref[i + 1] = pref[i]; if (i <= border) pref[i + 1] += 1; } vi suff(N + 1, 0); // number of protestants in range [i, N-1] segtree seg; seg.init(N); for (int i = N - 1; i >= 0; --i) { if (P[i] <= T) seg.block(i, i + T - P[i] + 1); suff[i] = seg.query(0, N); } int ans = suff[0]; for (int i = 0; i < N; ++i) { ans = min(ans, suff[i] + pref[i]); } cout << ans << endl; 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...