Submission #675884

#TimeUsernameProblemLanguageResultExecution timeMemory
675884ParsaSThe short shank; Redemption (BOI21_prison)C++17
0 / 100
90 ms51588 KiB
// In the name of God #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 = 1e6 + 5; int n, D, T, t[N]; int lt[N], par[N], tim, tin[N], tout[N]; vector<int> adj[N]; vector<pair<int, int> > vec; bool vis[N]; int seg[N << 2], mx[N << 2], lz[N << 2], h[N]; void dfs(int v) { tin[v] = tim++; vec.pb(mp(h[v], v)); for (auto u : adj[v]) { h[u] = h[v] + 1; dfs(u); } tout[v] = tim - 1; } void build(int v = 1, int tl = 0, int tr = tim) { if (tl == tr) { seg[v] = vec[tl].se; mx[v] = vec[tl].fi; return; } int mid = (tl + tr) >> 1; build(v << 1, tl, mid); build(v << 1 | 1, mid + 1, tr); seg[v] = seg[v << 1]; mx[v] = max(mx[v << 1], mx[v << 1 | 1]); if (h[seg[v << 1 | 1]] > h[seg[v << 1]]) seg[v] = seg[v << 1 | 1]; } 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 v = 1, int tl = 0, int tr = tim) { shift(v, tl, tr); if (l > tr || r < tl) return; if (tl >= l && tr <= r) { lz[v]++; shift(v, tl, tr); return; } int mid = (tl + tr) >> 1; upd(l, r, v << 1, tl, mid); upd(l, r, v << 1 | 1, mid + 1, tr); seg[v] = seg[v << 1]; mx[v] = max(mx[v << 1], mx[v << 1 | 1]); if (mx[v] == mx[v << 1 | 1]) seg[v] = seg[v << 1 | 1]; } pair<int, int> query(int l, int r, int v = 1, int tl = 0, int tr = tim) { shift(v, tl, tr); pair<int, int> out(-1, n + 1); if (l > tr || r < tl) return mp(-1, n + 1); if (tl >= l && tr <= r) return mp(mx[v], seg[v]); int mid = (tl + tr) >> 1; pair<int, int> pl = query(l, r, v << 1, tl, mid); pair<int, int> pr = query(l, r, v << 1 | 1, mid + 1, tr); return pl > pr ? pl : pr; } void solve() { cin >> n >> D >> T; for (int i = 0; i < n; i++) cin >> t[i]; stack<int> st; memset(par, -1, sizeof par); memset(lt, -1, sizeof lt); vector<int> tmp; for (int i = 0; i < n; i++) { while (!st.empty() && t[st.top()] + i - st.top() > T) { tmp.pb(st.top()); st.pop(); } if (!st.empty() && t[i] > T) { lt[i] = st.top(); while (!tmp.empty() && tmp.back() >= lt[i]) { int j = tmp.back(); if (lt[j] != -1) { adj[i].pb(j); par[j] = i; } tmp.pop_back(); } } st.push(i); } for (int i = 0; i < n; i++) { if (par[i] == -1 && lt[i] != -1) { adj[n].pb(i); par[i] = n; } } dfs(n); tim--; build(); vis[n] = true; int ans = 0; while (D--) { shift(1, 0, n); int v = seg[1]; if (mx[1] <= 0) break; ans += mx[1]; while (!vis[v]) { upd(tin[v], tout[v]); vis[v] = true; v = par[v]; } } 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...