제출 #515930

#제출 시각아이디문제언어결과실행 시간메모리
515930Wayne_YanThe short shank; Redemption (BOI21_prison)C++17
0 / 100
135 ms135896 KiB
#include <bits/extc++.h> using namespace std; using namespace __gnu_pbds; typedef int64_t ll; typedef long double ld; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define pb emplace_back #define mp make_pair #define mt make_tuple #define pii pair<int,int> #define F(n) Fi(i,n) #define Fi(i,n) Fl(i,0,n) #define Fl(i,l,n) for(int i=l;i<n;i++) #define RF(n) RFi(i,n) #define RFi(i,n) RFl(i,0,n) #define RFl(i,l,n) for(int i=n-1;i>=l;i--) #define all(v) begin(v),end(v) #define siz(v) (ll(v.size())) #define get_pos(v,x) (lower_bound(all(v),x)-begin(v)) #define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v)) #define mem(v,x) memset(v,x,sizeof v) #define ff first #define ss second #define mid ((l+r)>>1) #define RAN(a,b) uniform_int_distribution<int> (a, b)(rng) #define debug(x) (cerr << (#x) << " = " << x << "\n") #define cmax(a,b) (a = max(a,b)) #define cmin(a,b) (a = min(a,b)) template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >; template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >; template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>; const int maxN = 2e6+10; int arr[maxN]; int fa[maxN]; int actual[maxN]; int previ[maxN]; vector<int> edge[maxN]; vector<int> cnt[maxN]; bool deleted[maxN]; int height[maxN], pointer[maxN]; void dfs(int c){ bool leaf = true; for(int i : edge[c]){ if(i == fa[c]) continue; leaf = false; dfs(i); if(height[i] + 1 > height[c]){ height[c] = height[i] + 1; pointer[c] = pointer[i]; } } if(leaf){ height[c] = 1; pointer[c] = c; } } signed main(){ fill(fa, fa+maxN, -1); fill(previ, previ+maxN, -1); fill(height, height+maxN, -1); cin.tie(0); ios_base::sync_with_stdio(false); int N,D,T; cin >> N >> D >> T; F(N) cin >> arr[i]; actual[0] = arr[0]; Fl(i, 1, N){ actual[i] = min(arr[i], actual[i-1]+1); } stack<int> st; stack<int> q; RF(N){ if(actual[i] <= T && arr[i] > T){ q.push(i); } if(arr[i] < T){ while(!q.empty() && arr[i] + q.top() - i <= T){ previ[q.top()] = i; q.pop(); } } } F(N){ if(actual[i] <= T && arr[i] > T){ while(!st.empty() && st.top() > previ[i]){ fa[st.top()] = i; edge[i].pb(st.top()); edge[st.top()].pb(i); st.pop(); } st.push(i); } } /* F(N) printf("%d ", actual[i]); printf("\n"); F(N) printf("%d ", previ[i]); printf("\n"); F(N) printf("%d ", fa[i]); printf("\n"); */ F(N) if(fa[i] == -1) dfs(i); F(N) if(actual[i] <= T && arr[i] > T) cnt[height[i]].pb(i); int suppressed = 0; RF(N){ for(int j : cnt[i]){ if(deleted[j]) continue; int cursor = pointer[j]; while(cursor != j){ deleted[cursor] = true; suppressed++; cursor = fa[cursor]; } deleted[j] = true; suppressed++; D--; if(D == 0) break; } if(D == 0) break; } printf("%d", N - suppressed); 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...