Submission #895415

#	Time	Username	Problem	Language	Result	Execution time	Memory
895415		d4xn	The short shank; Redemption (BOI21_prison)	C++17	10 / 100	290 ms	243900 KiB

prison

#include <bits/stdc++.h>
using namespace std;
 
#define int long long
#define all(x) x.begin(), x.end()

const int N = 2e6+6;
 
int n, d, t, curr, a[N], b[N], p[N], dep[N], sz[N], seg[2][N*4], laz[N*4];
vector<int> r[N], add[N], rem[N];
bitset<N> vis;

void build(int P=1, int L=0, int R=curr-1) {
  if (L == R) {
    seg[0][P] = dep[L];
    seg[1][P] = L;
    return;
  }

  int mid = (L+R)/2;
  build(P*2, L, mid);
  build(P*2+1, mid+1, R);

  seg[0][P] = max(seg[0][P*2], seg[0][P*2+1]);
  seg[1][P] = (seg[0][P] == seg[0][P*2] ? seg[1][P*2] : seg[1][P*2+1]);
}

void pushDown(int P) {
  seg[0][P*2] += laz[P];
  seg[0][P*2+1] += laz[P];
  laz[P] = 0;
}

void update(int A, int B, int P=1, int L=0, int R=curr-1) {
  if (A <= L && R <= B) {
    seg[0][P]--;
    laz[P]--;
    return;
  }
  pushDown(P);

  int mid = (L+R)/2;
  if (A <= mid) update(A, B, P*2, L, mid);
  if (mid+1 <= B) update(A, B, P*2+1, mid+1, R);

  seg[0][P] = max(seg[0][P*2], seg[0][P*2+1]);
  seg[1][P] = (seg[0][P] == seg[0][P*2] ? seg[1][P*2] : seg[1][P*2+1]);
}

int dfs(int L, int R, int DEP, int PAR) {
  //cerr << L << " " << R << " " << DEP << " " << curr << " " << PAR << endl;
  int c = curr++;
  p[c] = PAR;
  dep[c] = DEP;
  sz[c] = 1;

  int x = L;
  while (x < R) {
    int y = upper_bound(all(r[x]), R) - r[x].begin() - 1;
    if (y >= 0 && x == L && r[x][y] == R) y--;

    if (y >= 0) {
      int nwSz = dfs(x, r[x][y], DEP+1, c);
      //cerr << "nwSz -> " << nwSz << endl;
      sz[c] += nwSz;
      x = r[x][y];
    }
    else x++;
  }
//cerr << c << " sz " << sz[c] << endl;
  return sz[c]; 
}

void dfs2(int x) {
  if (vis[x]) return;
  vis[x] = 1;

  update(x, x+sz[x]-1);
  //cerr << x << " " << x+sz[x]-1 << endl;
  if (p[x] == x) return;
  dfs2(p[x]);
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
 
  cin >> n >> d >> t;
  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);
  }
  
  int ans = 0;
  set<int> st;
  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] = -1;
      continue;
    }
 
    if (st.empty()) {
      b[i] = -1;
      ans++;
    }
    else {
      int x = *prev(st.end());
      b[i] = x;
      r[x].push_back(i);
    }
  }

  for (int i = 0; i < n; i++) {
    sort(all(r[i]));
  }
  curr = 0;//cerr << "a" << endl;
  dfs(0, n, 1, 0);
//cerr << "b" << endl;
  build();
  //cerr << "c" << endl;
  while (d > 0) {
    d--;//cerr << seg[0][1] << endl;
    ans += seg[0][1];//cerr << seg[0][1] << endl;
    int x = seg[1][1];//cerr << "d" << endl;
    dfs2(x);//cerr << "e" << endl;
  }
  cout << n-ans+1 << "\n";
}

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