Submission #894259

#	Time	Username	Problem	Language	Result	Execution time	Memory
894259		box	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	515 ms	258376 KiB

prison

#include <bits/stdc++.h>
using namespace std;
 
#define ar array
#define sz(v) static_cast<int>(v.size())
#define all(v) (v).begin(), (v).end()
typedef long long ll;
typedef pair<ll, int> pi;
typedef vector<int> vi;
 
const int N = 2e6;
 
int n, d, t, a[N], p[N], q[N];
 
vi g[N];
int c[N], dp[N];
 
void dfs(int i) {
  c[i] = -1;
  dp[i] = 1;
  for (int j : g[i]) {
    dfs(j);
    if (dp[j] + 1 > dp[i]) {
      dp[i] = dp[j] + 1;
      c[i] = j;
    }
  }
}
 
int main() {
  cin.tie(0)->sync_with_stdio(0);
 
  cin >> n >> d >> t, d++;
  for (int i = 0; i < n; i++) cin >> a[i];
 
  vi stk;
  auto f = [&](int i) { return a[i] - i; };
  for (int i = 0; i < n; i++) {
    while (sz(stk) && f(stk.back()) >= f(i)) stk.pop_back();
    stk.push_back(i);
    if (f(stk[0]) > t - i)
      p[i] = -1;
    else {
      int low = 0, hi = sz(stk) - 1;
      while (low < hi) {
        int m = (low + hi) / 2 + 1;
        if (f(stk[m]) <= t - i)
          low = m;
        else
          hi = m - 1;
      }
      assert(f(stk[low]) <= t - i);
      p[i] = stk[low];
    }
  }
 
  vi imp;
 
  int ans = n;
 
  for (int i = 0; i < n; i++) {
    if (p[i] != -1 && p[i] < i) {
      imp.push_back(i);
    }
    if (p[i] == -1) ans--;
  }
  vi rev = imp;
  reverse(all(rev));
  stk = vi();
 
  vi all;
 
  for (int i : rev) {
    if (!sz(stk) || p[stk[0]] >= i)
      q[i] = -1;
    else {
      int low = 0, hi = sz(stk) - 1;
      while (low < hi) {
        int m = (low + hi) / 2 + 1;
        if (p[stk[m]] < i)
          low = m;
        else
          hi = m - 1;
      }
      q[i] = stk[low];
    }
    while (sz(stk) && p[stk.back()] >= p[i]) stk.pop_back();
    stk.push_back(i);
    all.push_back(i);
  }
  for (int i : imp)
    if (~q[i]) g[q[i]].push_back(i);
  priority_queue<pair<int, int>> pq;
  for (int i : imp)
    if (q[i] == -1) {
      dfs(i);
      pq.push({dp[i], i});
    }
  while (d > 1 && sz(pq)) {
    d--;
    auto [x, i] = pq.top();
    pq.pop();
    ans -= x;
    while (~i) {
      for (int j : g[i])
        if (j != c[i]) pq.push({dp[j], j});
      i = c[i];
    }
  }
  cout << ans << '\n';
}

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