Submission #599054

#TimeUsernameProblemLanguageResultExecution timeMemory
599054MohammadAghilThe short shank; Redemption (BOI21_prison)C++17
0 / 100
14 ms23892 KiB
#include <bits/stdc++.h> // #pragma GCC optimize ("Ofast,unroll-loops") // #pragma GCC target ("avx2") using namespace std; typedef long long ll; typedef pair<int, int> pp; #define er(args ...) cerr << __LINE__ << ": ", err(new istringstream(string(#args)), args), cerr << endl #define per(i,r,l) for(int i = (r); i >= (l); i--) #define rep(i,l,r) for(int i = (l); i < (r); i++) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() #define pb push_back #define ss second #define ff first void err(istringstream *iss){}template<typename T,typename ...Args> void err(istringstream *iss,const T &_val, const Args&...args){string _name;*iss>>_name;if(_name.back()==',')_name.pop_back();cerr<<_name<<" = "<<_val<<", ",err(iss,args...);} void IOS(){ cin.tie(0) -> sync_with_stdio(0); // #ifndef ONLINE_JUDGE // freopen("in.in", "r", stdin); // freopen("out.out", "w", stdout); // #endif } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 1e9 + 7, maxn = 1e6 + 5, lg = 22, inf = ll(1e9) + 5; ll pw(ll a,ll b,ll md=mod){if(!b)return 1;ll k=pw(a,b>>1ll);return k*k%md*(b&1ll?a:1)%md;} pp seg[maxn<<2]; int laz[maxn<<2]; void updNode(int x, int k){ seg[x].ff += k, laz[x] += k; } void shift(int x){ if(laz[x]){ updNode(x<<1, laz[x]); updNode(x<<1|1, laz[x]); laz[x] = 0; } } pp get(){ return seg[1]; } int get(int i, int x = 1, int lx = 0, int rx = maxn){ if(lx + 1 == rx) return seg[x].ff; int mid = (lx + rx)>>1; shift(x); if(i < mid) return get(i, x<<1, lx, mid); return get(i, x<<1|1, mid, rx); } void upd(int l, int r, int k, int x = 1, int lx = 0, int rx = maxn){ if(l <= lx && r >= rx){ updNode(x, k); return; } shift(x); int mid = (lx + rx)>>1; if(l < mid) upd(l, r, k, x<<1, lx, mid); if(mid < r) upd(l, r, k, x<<1|1, mid, rx); seg[x] = max(seg[x<<1], seg[x<<1|1]); } vector<int> adj[maxn]; int par[maxn], h[maxn], st[maxn], en[maxn], tt, inv[maxn]; bool vis[maxn]; void dfs(int r){ inv[tt] = r, st[r] = tt++, vis[r] = true; for(int c: adj[r]) h[c] = h[r] + 1, dfs(c); en[r] = tt; } int main(){ IOS(); int n, d, t; cin >> n >> d >> t; vector<int> a(n), e(n); rep(i,0,n) cin >> a[i], e[i] = t - a[i] + i; vector<bool> is(n); int mx = -1, ans = 0; rep(i,0,n){ if(a[i] > t) { if(mx < i) ans++; else is[i] = true, er(i); } mx = max(mx, e[i]); } vector<int> stk; per(i,n-1,0){ if(is[i]){ par[i] = -1; if(sz(stk)) par[i] = stk.back(), adj[par[i]].pb(i); stk.pb(i); }else{ while(sz(stk) && stk.back() <= e[i]) stk.pop_back(); } } rep(i,0,n) { if(!vis[i]) h[i] = 1, dfs(i); upd(st[i], st[i]+1, h[i]); } while(d--){ auto[hh, id] = get(); if(hh <= 0) break; int r = inv[id]; while(r + 1 && vis[r]){ ans++; int H = get(st[r], st[r]+1); upd(st[r], en[r], -H); vis[r] = false, r = par[r]; } } cout << n - 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...