Submission #516149

#	Time	Username	Problem	Language	Result	Execution time	Memory
516149		Wayne_Yan	The short shank; Redemption (BOI21_prison)	C++17	100 / 100	545 ms	362016 KiB

prison

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

typedef int64_t ll;
typedef long double ld;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define pb emplace_back
#define mp make_pair
#define mt make_tuple
#define pii pair<int,int>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
#define RF(n) RFi(i,n)
#define RFi(i,n) RFl(i,0,n)
#define RFl(i,l,n) for(int i=n-1;i>=l;i--)
#define all(v) begin(v),end(v)
#define siz(v) (ll(v.size()))
#define get_pos(v,x) (lower_bound(all(v),x)-begin(v))
#define sort_uni(v) sort(begin(v),end(v)),v.erase(unique(begin(v),end(v)),end(v))
#define mem(v,x) memset(v,x,sizeof v)
#define ff first
#define ss second
#define mid ((l+r)>>1)
#define RAN(a,b) uniform_int_distribution<int> (a, b)(rng)
#define debug(x) (cerr << (#x) << " = " << x << "\n")
#define cmax(a,b) (a = max(a,b))
#define cmin(a,b) (a = min(a,b))

template <typename T> using max_heap = __gnu_pbds::priority_queue<T,less<T> >;
template <typename T> using min_heap = __gnu_pbds::priority_queue<T,greater<T> >;
template <typename T> using rbt = tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int maxN = 2e6+10;
int arr[maxN];
int fa[maxN];
int actual[maxN];
int previ[maxN];
vector<int> edge[maxN];
vector<int> cnt[maxN];
bool deleted[maxN];

int height[maxN], pointer[maxN];

void dfs(int c){
  bool leaf = true;
  for(int i : edge[c]){
    if(i == fa[c]) continue;
    leaf = false;
    dfs(i);
    if(height[i] + 1 > height[c]){
      height[c] = height[i] + 1;
      pointer[c] = pointer[i];
    }
  }
  if(leaf){
    height[c] = 1;
    pointer[c] = c;
  }
}

signed main(){
  
  fill(fa, fa+maxN, -1);
  fill(previ, previ+maxN, -1);
  fill(height, height+maxN, -1);


  cin.tie(0);
  ios_base::sync_with_stdio(false);

  int N,D,T;
  cin >> N >> D >> T;
  
  F(N) cin >> arr[i];
  
  
  actual[0] = arr[0];

  Fl(i, 1, N){
    actual[i] = min(arr[i], actual[i-1]+1);
  }
  
  stack<int> st;
  stack<int> q;
  RF(N){
    if(actual[i] <= T && arr[i] > T){
      q.push(i);
    }
    if(arr[i] < T){
      while(!q.empty() && arr[i] + q.top() - i <= T){
        previ[q.top()] = i;
        q.pop();
      }
    }
  }

  F(N){
    if(actual[i] <= T && arr[i] > T){
      while(!st.empty() && st.top() > previ[i]){
        fa[st.top()] = i;
        edge[i].pb(st.top());
        edge[st.top()].pb(i);
        st.pop();
      }
      st.push(i);
    }
  }

  /* 
  F(N) printf("%d ", actual[i]);
  printf("\n");
  F(N) printf("%d ", previ[i]);
  printf("\n");
  F(N) printf("%d ", fa[i]);
  printf("\n");
  */

  F(N) if(actual[i] <= T && arr[i] > T && fa[i] == -1) dfs(i);
  F(N) if(actual[i] <= T && arr[i] > T) cnt[height[i]].pb(i);

  int suppressed = 0;

  RF(N){
    for(int j : cnt[i]){
      if(deleted[j] || D <= 0) continue;

      int cursor = pointer[j];
      while(cursor != j){
        deleted[cursor] = true;
        suppressed++;
        cursor = fa[cursor];
      }
      deleted[j] = true;
      suppressed++;
      D--;
    }
  }

  F(N) if(actual[i] > T) suppressed++;

  printf("%d", N - suppressed);

  return 0;
}

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