Submission #686588

#	Time	Username	Problem	Language	Result	Execution time	Memory
686588		cig32	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2079 ms	138532 KiB

prison

#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
const int MAXN = 2e6 + 10;
const int MOD = 1e9 + 7;
struct node {
  int ma = 0, upd = 0, idx;
} st[MAXN << 2];
void build(int l, int r, int idx) {
  if(l == r) {
    st[idx].idx = l; return;
  }
  int mid = (l + r) >> 1;
  build(l, mid, (idx<<1)+1);
  build(mid+1, r, (idx<<1)+2);
  st[idx].ma = max(st[(idx<<1)+1].ma, st[(idx<<1)+2].ma);
  st[idx].idx = (st[(idx<<1)+1].ma == st[idx].ma ? st[(idx<<1)+1].idx : st[(idx<<1)+2].idx);
}
void u(int l, int r, int constl, int constr, int idx, int val) {
  if(l <= constl && constr <= r) {
    st[idx].ma += val;
    st[idx].upd += val;
    return;
  }
  int mid = (constl + constr) >> 1;
  st[(idx<<1)+1].ma += st[idx].upd;
  st[(idx<<1)+1].upd += st[idx].upd;
  st[(idx<<1)+2].ma += st[idx].upd;
  st[(idx<<1)+2].upd += st[idx].upd;
  st[idx].upd = 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);
  st[idx].ma = max(st[(idx<<1)+1].ma, st[(idx<<1)+2].ma);
  st[idx].idx = (st[(idx<<1)+1].ma == st[idx].ma ? st[(idx<<1)+1].idx : st[(idx<<1)+2].idx);
}
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] = max(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, MOD-bruh);
    }
  }
  while(d--) {
    int ss = st[0].idx;
    int pr = ans;
    while(1) {
      int idx = qu2(ss+1, n, 1, n, 0, MOD-ss); 
      if(idx == -1) break;
      u2(1, n, idx, 0, 0);
      u(sv[idx], idx-1, 1, n-1, 0, -1);
      ans--;
    }
    if(pr == 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: 0 / 20