제출 #485620

#제출 시각아이디문제언어결과실행 시간메모리
485620pooyashamsThe short shank; Redemption (BOI21_prison)C++14
0 / 100
111 ms82108 KiB
#include <algorithm> #include <numeric> #include <iostream> #include <cstring> #include <cmath> #include <vector> #include <stack> #include <queue> #include <set> #include <map> #include <cassert> using namespace std; typedef long long ll; typedef pair<int, int> pii; const int maxn = 2e6+10; int n, D, T; vector<int> kids[maxn]; int stme[maxn]; int tmi[maxn]; int frit[maxn]; int par[maxn]; int init[maxn]; bool vis[maxn]; int tin[maxn]; int tout[maxn]; int inord[maxn]; int timer = 0; struct seg { int l, r; inline bool operator<(seg& b) { return l < b.l or (l == b.l and r > b.r); } inline bool in(seg& b) { return b.l <= l and r <= b.r; } } segs[maxn]; void dfs(int v, int h) { init[v] = h; tin[v] = timer++; inord[tin[v]] = v; for(int u: kids[v]) dfs(u, h+1); tout[v] = timer; } struct lzst { vector<int> vals; // max vector<int> vidx; // max index vector<int> lazy; int n; lzst(int len) { vals = vector<int>(len * 4, 0); vidx = vector<int>(len * 4, 0); lazy = vector<int>(len * 4, 0); n = len; build(0, len, 1); } inline void upd(int v) { vals[v] = max(vals[2*v], vals[2*v+1]); if(vals[v] == vals[2*v]) vidx[v] = vidx[2*v]; else vidx[v] = vidx[2*v+1]; } inline void put(int x, int v) { vals[v] += x; lazy[v] += x; } inline void shift(int v) { if(lazy[v] == 0) return; put(lazy[v], 2*v); put(lazy[v], 2*v+1); lazy[v] = 0; } void build(int l, int r, int v) { if(r - l == 1) { vals[v] = init[inord[l]]; vidx[v] = inord[l]; lazy[v] = 0; return; } int m = (l+r) / 2; build(l, m, 2*v); build(m, r, 2*v+1); upd(v); } void _add(int l, int r, int s, int e, int x, int v) { if(e <= l or r <= s) return; if(s <= l and r <= e) return put(x, v); int m = (l+r) / 2; shift(v); _add(l, m, s, e, x, 2*v); _add(m, r, s, e, x, 2*v+1); upd(v); } inline void add(int s, int e, int x) { _add(0, n, s, e, x, 1); } }; int main() { ios::sync_with_stdio(false); cin.tie(0); cin >> n >> D >> T; stack<int> st; int scnt = 0; segs[scnt++] = {0, n}; int rem = n+1; for(int i = 0; i < n; i++) { cin >> stme[i]; tmi[i] = stme[i] - i; st.push(i); while(!st.empty() and tmi[st.top()] > T-i) st.pop(); if(st.empty()) frit[i] = 0; else frit[i] = st.top(); if(frit[i] != i) segs[scnt++] = {frit[i], i}; //cerr << frit[i] << endl; } sort(segs, segs+scnt); //for(int i = 0; i < scnt; i++) cerr << i << ": " << segs[i].l << " " << segs[i].r << endl; //cerr << endl; int lst = 0; par[0] = -1; for(int i = 1; i < scnt; i++) { while(!segs[i].in(segs[lst])) lst = par[lst]; par[i] = lst; kids[lst].push_back(i); lst = i; //cerr << i << " " << par[i] << endl; } dfs(0, 1); lzst mf(scnt); //cerr << rem << endl; //for(int i = 0; i < 15; i++) cerr << mf.vals[i] << " "; cerr << endl << endl; while(D--) { int v = mf.vidx[1]; //cerr << v << endl; while(v != -1 and !vis[v]) { mf.add(tin[v], tout[v], -1); vis[v] = true; rem--; v = par[v]; } } cout << rem << 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...