Submission #1131029

#	Time	Username	Problem	Language	Result	Execution time	Memory
1131029		Hamed_Ghaffari	The short shank; Redemption (BOI21_prison)	C++20	100 / 100	1796 ms	280192 KiB

prison

#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,sse4,sse4.2,lzcnt,popcnt")

using pii = pair<int, int>;

#define X first
#define Y second
#define pb push_back
#define all(x) x.begin(), x.end()
#define SZ(x) int(x.size())

const int MXN = 2e6+5;

int n, D, T, t[MXN], ans, par[MXN];
int N;
vector<int> g[MXN];

void build_tree(vector<pii> vec) {
  sort(all(vec), [&](pii x, pii y) {
    return x.X<y.X || (x.X==y.X && x.Y>y.Y);
  });
  N = SZ(vec);
  for(int i=0; i<N; i++) {
    for(par[i]=i-1; par[i]!=-1 && vec[par[i]].Y<vec[i].Y; par[i]=par[par[i]]);
    if(par[i]!=-1) g[par[i]].pb(i);
  }
}

#define mid l+r>>1
#define lc id<<1
#define rc lc|1

pii seg[MXN<<2];
int lz[MXN<<2];

void build(int l=0, int r=N, int id=1) {
  lz[id] = 0;
  if(r-l==1) {
    seg[id] = pii(0, l);
    return;
  }
  build(l, mid, lc);
  build(mid, r, rc);
  seg[id] = max(seg[lc], seg[rc]);
}
void apply_add(int x, int id) {
  seg[id].X += x;
  lz[id] += x;
}
void push(int l, int r, int id) {
  if(r-l>1 && lz[id]) {
    apply_add(lz[id], lc);
    apply_add(lz[id], rc);
  }
  lz[id] = 0;
}
void upd(int s, int e, int x, int l=0, int r=N, int id=1) {
  push(l, r, id);
  if(s<=l && r<=e) {
    apply_add(x, id);
    return;
  }
  if(s<mid) upd(s, e, x, l, mid, lc);
  if(e>mid) upd(s, e, x, mid, r, rc);
  seg[id] = max(seg[lc], seg[rc]);
}

int h[MXN], stt[MXN], fnt[MXN], ver[MXN], timer;
void dfs(int v) {
  ver[stt[v] = timer++] = v;
  for(int u : g[v]) {
    h[u] = h[v]+1;
    dfs(u);
  }
  fnt[v] = timer;
  upd(stt[v], fnt[v], 1);
}

bool isdel[MXN];

void del(int v) {
  while(v!=-1 && !isdel[v]) {
    isdel[v] = 1;
    upd(stt[v], fnt[v], -1);
    v = par[v];
  }
}

int32_t main() {
  cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);
  cin >> n >> D >> T;
  for(int i=0; i<n; i++) cin >> t[i];
  vector<pii> vec;
  vector<int> stk;
  for(int i=0; i<n; i++) {
    while(!stk.empty() && t[stk.back()]+i-stk.back()>min(T, t[i]+1)) stk.pop_back();
    if(t[i]>T) {
      if(stk.empty()) ans++;
      else vec.pb(pii(stk.back(), i));
    }
    stk.pb(i);
  }
  if(vec.empty()) return cout << n-ans << '\n', 0;
  build_tree(vec);
  build();
  for(int i=0; i<N; i++)
    if(par[i]==-1)
      dfs(i);
  for(int i=0; i<D; i++) {
    if(seg[1].X) {
      ans += seg[1].X;
      del(ver[seg[1].Y]);
    }
  }
  cout << n-ans << '\n';
  return 0;
}

• Subtask 1: 15 / 15
• Subtask 2: 10 / 10
• Subtask 3: 20 / 20
• Subtask 4: 10 / 10
• Subtask 5: 25 / 25
• Subtask 6: 20 / 20