| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 528379 | fatemetmhr | The short shank; Redemption (BOI21_prison) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn5 = 2e6 + 10;
const int maxnt = 8e6 + 10;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(x) x.begin(), x.end()
int n, ti = -1, st[maxn5], ft[maxn5], lazy[maxnt];
int h[maxn5], l[maxn5], ver[maxn5], ans = 0;
int per[maxn5], par[maxn5];
pair <int, int> mx[maxnt];
vector <int> adj[maxn5];
vector <pair<ll, int>> av;
set <pair<int, int>> seg;
bool mark[maxn5];
inline bool cmp(int i, int j){
return i - l[i] < j - l[j];
}
inline void add(int l, int r, int lq, int rq, int v){
if(rq <= l || r <= lq)
return;
if(lq <= l && r <= rq){
lazy[v]--;
mx[v].fi--;
return;
}
int mid = (l + r) >> 1;
add(l, mid, lq, rq, v * 2);
add(mid, r, lq, rq, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
mx[v].fi += lazy[v];
return;
}
inline void build(int l, int r, int v){
if(r - l == 1){
mx[v] = l > ti ? {-1, 0} : {h[ver[l]] + 1, ver[l]};
return;
}
int mid = (l + r) >> 1;
build(l, mid, v * 2);
build(mid, r, v * 2 + 1);
mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
return;
}
inline void upd(int v){
ans++;
mark[v] = true;
add(0, n, st[v], ft[v] + 1, 1);
if(par[v] != -1 && !mark[par[v]])
upd(par[v]);
return;
}
inline void dfs(int v){
st[v] = ++ti;
ver[ti] = v;
for(auto u : adj[v]){
h[u] = h[v] + 1;
dfs(u);
}
ft[v] = ti;
return;
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
int d; ll tim; cin >> n >> d >> tim;
for(int i = 0; i < n; i++){
ll t; cin >> t;
while(av.size() && av.back().fi >= t - i)
av.pop_back();
av.pb({t - i, i});
int p = upper_bound(all(av), mp(tim - i, maxn5)) - av.begin();
p--;
if(p == -1 || av[p].se == i)
l[i] = -maxn5;
else
l[i] = av[p].se;
per[i] = i;
}
sort(per, per + n, cmp);
memset(par, -1, sizeof par);
for(int i = 0; i < n; i++) if(l[i] >= 0){
auto it = seg.lower_bound(mp(l[i], -1));
for(; it != seg.end() && (it ->se) <= i;){
adj[i].pb(it->se);
par[it->se] = i;
auto itt = it;
it++;
seg.erase(itt);
}
seg.insert(mp(l[i], i));
}
for(int i = 0; i < n; i++) if(l[i] >= 0 && par[i] == -1)
dfs(i);
build(0, n, 1);
for(int i = 0; i < d && mx[1].fi > 0; i++){
int v = mx[1].se;
upd(v);
}
cout << n - ans << endl;
}