제출 #686651

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
686651		cig32	The short shank; Redemption (BOI21_prison)	C++14	100 / 100	1928 ms	106400 KiB

prison

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 2e6 + 5;
const int MOD = 1e9 + 7;
int stma[MAXN << 2], stupd[MAXN << 2], stidx[MAXN << 2];
void build(int l, int r, int idx) {
  if(l == r) {
    stidx[idx] = l; return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, (idx<<1)+1);
  build(mid+1, r, (idx<<1)+2);
  stma[idx] = max(stma[(idx<<1)+1], stma[(idx<<1)+2]);
  stidx[idx] = (stma[(idx<<1)+1] == stma[idx] ? stidx[(idx<<1)+1] : stidx[(idx<<1)+2]);
}
void u(int l, int r, int constl, int constr, int idx, int val) {
  if(l <= constl && constr <= r) {
    stma[idx] += val;
    stupd[idx] += val;
    return;
  }
  int mid = (constl + constr) >> 1;
  stma[(idx<<1)+1] += stupd[idx];
  stma[(idx<<1)+2] += stupd[idx];
  stupd[(idx<<1)+1] += stupd[idx];
  stupd[(idx<<1)+2] += stupd[idx];
  stupd[idx] = 0;
  if(mid >= l && r >= constl) u(l, r, constl, mid, (idx<<1)+1, val);
  if(constr >= l && r >= mid+1) u(l, r, mid+1, constr, (idx<<1)+2, val);
  stma[idx] = max(stma[(idx<<1)+1], stma[(idx<<1)+2]);
  stidx[idx] = (stma[(idx<<1)+1] == stma[idx] ? stidx[(idx<<1)+1] : stidx[(idx<<1)+2]);
}
int seg[MAXN << 2];
 
void u2(int l, int r, int tar, int idx, int val) {
  if(l == r) {
    seg[idx] = val; return;
  }
  int mid = (l + r) >> 1;
  if(tar <= mid) u2(l, mid, tar, (idx<<1)+1, val);
  else u2(mid+1, r, tar, (idx<<1)+2, val);
  seg[idx] = min(seg[(idx<<1)+1], seg[(idx<<1)+2]);
}
 
int qu2(int l, int r, int constl, int constr, int idx, int val) { // first <= v
  if(l <= constl && constr <= r) {
    if(seg[idx] > val) return -1;
    while(constl < constr) {
      int mid = (constl + constr) >> 1;
      if(seg[(idx<<1)+1] <= val) constr = mid, idx = (idx<<1)+1;
      else constl = mid+1, idx = (idx<<1)+2;
    }
    return constl;
  }
  int mid = (constl + constr) >> 1;
  if(mid < l || r < constl) return qu2(l, r, mid+1, constr, (idx<<1)+2, val);
  else if(constr < l || r < mid+1) return qu2(l, r, constl, mid, (idx<<1)+1, val);
  else {
    int lc = qu2(l, r, constl, mid, (idx<<1)+1, val);
    if(lc != -1) return lc;
    return qu2(l, r, mid+1, constr, (idx<<1)+2, val);
  }
}
inline int read() {
  int x = 0, c = getchar(), neg = false;
  while(('0' > c || c > '9') && c!='-' && c!=EOF) c = getchar();
  if(c == '-') neg = true, c = getchar();
  while('0' <= c && c <= '9') x = x*10 + (c^'0'), c = getchar();
  if(neg) x = -x;
  return x; // returns 0 if EOF
}
int32_t main() {
  ios::sync_with_stdio(0); cin.tie(0);
  int32_t n, d, t;
  n = read();
  d = read();
  t = read();
  pair<int, int> tri[n+1];
  for(int i=1; i<=n; i++) {
    int32_t x = read();
    tri[i] = {x-i, i};
  }
  sort(tri+1, tri+1+n);
  build(1, n-1, 0);
  int ans = 0;
  int pr = 0;
  priority_queue<int> ok;
  int sv[n+1];
  for(int i=n; i>=1; i--) {
    while(pr+1 <= n && tri[pr+1].first <= t-i) {
      pr++;
      if(tri[pr].second <= i) ok.push(tri[pr].second);
    }
    int bruh = (ok.size() ? ok.top() : -1);
    if(bruh == i) ok.pop();
    sv[i]= bruh;
    if(bruh != -1) {
      ans++;
      if(bruh < i) {
        u(bruh, i-1, 1, n-1, 0, 1);
      }
      u2(1, n, i, 0, bruh);
    }
    else {
      u2(1, n, i, 0, MOD);
    }
  }
  while(d--) {
    int ss = stidx[0];
    int prv=ans;
    while(1) {
      int idx = qu2(ss+1, n, 1, n, 0, ss); 
      if(idx == -1) break;
      u2(1, n, idx, 0, MOD); 
      u(sv[idx], idx-1, 1, n-1, 0, -1);
      ans--;
    }
    if(prv == ans) break;
  }
  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