제출 #894493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
894493		vjudge1	The short shank; Redemption (BOI21_prison)	C++17	0 / 100	274 ms	419576 KiB

prison

#include <bits/stdc++.h>
using namespace std;

#define all(x) x.begin(), x.end()

const int N = 75000;

int n, d, t, a[N], b[N], laz[N*4];
vector<int> add[N], rem[N];
deque<int> seg[N*4];

void build(int p=1, int l=0, int r=n-1) {
  if (l == r) {
    if (b[l] != n) seg[p].push_back(b[l]);
    return;
  }

  int mid = (l+r)/2;
  build(p*2, l, mid);
  build(p*2+1, mid+1, r);

  seg[p].resize(seg[p*2].size() + seg[p*2+1].size());
  merge(all(seg[p*2]), all(seg[p*2+1]), seg[p].begin());
}

void update(int x, int p=1, int l=0, int r=n-1) {
  if (l > x) {
    laz[p] = max(laz[p], x);
    return;
  }

  int mid = (l+r)/2;
  if (mid > x) update(x, p*2, l, mid);
  if (r > x) update(x, p*2+1, mid+1, r);
}

int query(int x, int p=1, int l=0, int r=n-1) {
  if (l > x) {
    while (!seg[p].empty() && seg[p].front() <= laz[p]) seg[p].pop_front();
    return upper_bound(all(seg[p]), x) - seg[p].begin();
  }

  int mid = (l+r)/2;
  int y = 0;
  if (mid > x) y += query(x, p*2, l, mid);
  if (r > x) y += query(x, p*2+1, mid+1, r);
  return y;
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> d >> t;
  memset(laz, -1, sizeof(laz));
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    if (a[i] > t) continue;
    
    add[i].push_back(i);
    rem[min(n, i + t-a[i] + 1)].push_back(i);
  }

  set<int> st;
  int ans = 0;
  for (int i = 0; i < n; i++) {
    for (int& j : add[i]) st.insert(j);
    for (int& j : rem[i]) st.erase(j);

    if (a[i] <= t) {
      b[i] = n;
      continue;
    }

    if (st.empty()) {
      b[i] = n;
      ans++;
    }
    else b[i] = *prev(st.end());
  }
  build(); // build con b[i]

  priority_queue<pair<int, int>> pq;
  for (int i = 0; i < n; i++) {
    int x = query(i); // numeros <= i a partir de i+1
    //cerr << b[i] << " " << x << "  ";
    pq.push(make_pair(x, -i));
  }//cerr << endl;

  while (d && !pq.empty()) {
    int x = pq.top().first;
    int i = -pq.top().second;
    pq.pop();
    
    int nwX = query(i); // numeros <= i a partir de i+1
    if (nwX != x) {
      pq.push(make_pair(nwX, -i));
      continue;
    }

    ans += x;
    d--;
    update(i); // eliminar numeros <= i a partir de i+1
  }

  cout << n - ans << "\n";
}

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