제출 #686610

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
686610		cig32	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2068 ms	138400 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 + 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);
}
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
}
 
int t[MAXN << 2];
 
int get(int v, int tl, int tr, int x, int l) {
	if (t[v] > x) return -1;
	if (tr <= l) return -1;
	if (tl + 1 == tr) return tl;
	int tm = (tl + tr) / 2;
	int res = get(v + v + 1, tl, tm, x, l);
	if (res == -1) res = get(v + v + 2, tm, tr, x, l);
	return res;
}
 
void update(int v, int tl, int tr, int pos, int x) {
	if (tl + 1 == tr) {
		t[v] = x;
		return;
	}
	int tm = (tl + tr) / 2;
	if (pos < tm) update(v + v + 1, tl, tm, pos, x);
	else update(v + v + 2, tm, tr, pos, x);
	t[v] = min(t[v + v + 1], t[v + v + 2]);
}
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);
      }
      update(0, 0, n, i-1, bruh);
    }
    else {
      update(0, 0, n, i-1, MOD);
    }
  }
  while(d--) {
    int ss = st[0].idx;
    int prv=ans;
    while(1) {
      int idx = get(0, 0, n, ss, ss); 
      if(idx == -1) break;
      update(0, 0, n, idx, MOD);
      idx++;
      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: 0 / 20