Submission #952931

#	Time	Username	Problem	Language	Result	Execution time	Memory
952931		lunchbox	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2080 ms	70984 KiB

prison

/*
*       ___
*   _ /    _\_
*  / |    |___|
*  | |       |
*  \_|   __  |
*     \_/  \_/
*   uwu amogus
*/
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define inf 0x7FFFFFFF
#define llinf 0x7FFFFFFFFFFFFFFF
#define ff first
#define ss second
#define FOR(i, a, b) for(int i = a; i < b; i++)
#define ROF(i, a, b) for(int i = a - 1; i >= b; i--)
//#define assert void
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
//#define int ll
struct dsu {
	dsu(int n) {
		p.resize(n, -1);
		pp.resize(n); for (int i = 0; i < n; i++) pp[i] = i;
		r.resize(n, 0);
	}
	inline int par(int x) {
		return pp[_par(x)];
	}
	inline int _par(int x) {
		return p[x] == -1 ? x : p[x] = _par(p[x]);
	}
	inline void merge(int a, int b) {
		a = _par(a); b = _par(b);
		if (a == b)return;
		if (r[a] < r[b]) {
			swap(a, b);
			swap(pp[a], pp[b]);
		}
		if (r[a] == r[b]) r[a]++;
		p[b] = a;
	}
	vector<int> p, r, pp;
};

namespace fastio {
static constexpr int SZ = 1 << 17;
char ibuf[SZ], obuf[SZ];
int pil = 0, pir = 0, por = 0;

struct Pre {
  char num[40000];
  constexpr Pre() : num() {
    for (int i = 0; i < 10000; i++) {
      int n = i;
      for (int j = 3; j >= 0; j--) {
        num[i * 4 + j] = n % 10 + '0';
        n /= 10;
      }
    }
  }
} constexpr pre;

inline void load() {
  memcpy(ibuf, ibuf + pil, pir - pil);
  pir = pir - pil + fread(ibuf + pir - pil, 1, SZ - pir + pil, stdin);
  pil = 0;
}
inline void flush() {
  fwrite(obuf, 1, por, stdout);
  por = 0;
}

inline void rd(char& c) { c = ibuf[pil++]; }
template <typename T>
inline void rd(T& x) {
  if (pil + 32 > pir) load();
  char c;
  do
    c = ibuf[pil++];
  while (c < '-');
  bool minus = 0;
  if (c == '-') {
    minus = 1;
    c = ibuf[pil++];
  }
  x = 0;
  while (c >= '0') {
    x = x * 10 + (c & 15);
    c = ibuf[pil++];
  }
  if (minus) x = -x;
}
inline void rd() {}
template <typename Head, typename... Tail>
inline void rd(Head& head, Tail&... tail) {
  rd(head);
  rd(tail...);
}

inline void wt(char c) { obuf[por++] = c; }
template <typename T>
inline void wt(T x) {
  if (por > SZ - 32) flush();
  if (!x) {
    obuf[por++] = '0';
    return;
  }
  if (x < 0) {
    obuf[por++] = '-';
    x = -x;
  }
  int i = 12;
  char buf[16];
  while (x >= 10000) {
    memcpy(buf + i, pre.num + (x % 10000) * 4, 4);
    x /= 10000;
    i -= 4;
  }
  if (x < 100) {
    if (x < 10) {
      wt(char('0' + char(x)));
    } else {
      uint32_t q = (uint32_t(x) * 205) >> 11;
      uint32_t r = uint32_t(x) - q * 10;
      obuf[por + 0] = '0' + q;
      obuf[por + 1] = '0' + r;
      por += 2;
    }
  } else {
    if (x < 1000) {
      memcpy(obuf + por, pre.num + (x << 2) + 1, 3);
      por += 3;
    } else {
      memcpy(obuf + por, pre.num + (x << 2), 4);
      por += 4;
    }
  }
  memcpy(obuf + por, buf + i + 4, 12 - i);
  por += 12 - i;
}

inline void wt() {}
template <typename Head, typename... Tail>
inline void wt(Head head, Tail... tail) {
  wt(head);
  wt(tail...);
}
template <typename T>
inline void wtn(T x) {
  wt(x, '\n');
}

struct Dummy {
  Dummy() { atexit(flush); }
} dummy;

}  // namespace fastio
using fastio::rd;
using fastio::wt;
using fastio::wtn;
 
signed main() {
//   ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, D, T; rd(N,D,T);
	vector<int> t(N); for (auto& x : t) rd(x);
	int l = 0, r = 2e6, m = 0;
	int ans = 0;
	while (l < r) {//aliens HAHAHAhaha ha ha :sob:
		m = (l + r) / 2;
		vector<pair<int,int>> st; st.reserve(N);
		struct node {
			int p = -1;//prev
			int n = -1;//next
			int lz = 0;
			int v = 0;
			int c = 0; // count owo!!!
			node() {};
			node(int v, int c) : v(v), c(c) {};
		};
		vector<node> st2; st2.reserve(N);
		dsu pls(N);
		int start = 0; 
		int amt = 0;//amount added
		function<void(int)> kill = [&](int i) {
			int n = st2[i].n;
			//assert(n != -1); 
			if (n == -1) return;
			if ((st2[i].v + (int)st2[i].lz > st2[n].v)) {
				int p = st2[i].p;
				st2[n].p = p;
				if (p != -1) {
					st2[p].lz += st2[i].lz;
					st2[p].n = n;
					pls.merge(p, i); //merge i to p
					kill(p);
				}
				else {
					// DEAD
					amt -= st2[i].lz; //recycle owo
					start = n;
				}
			}
		};
		for (int i = 0; i < N; i++) {
			//create and then upd
			if (st2.size()) {
				st2.push_back(node(st2[start].v + (int)amt + m, st2[start].c+1));
				st2[i - 1].n = i; st2[i].p = i - 1;
				kill(i - 1);
			}
			else {
				st2.push_back(node());
			}
 
			int o = i;
			if (t[i] <= T) {
				while (st.size() && st.back().ff >= t[i] - i) {
					st.pop_back();
				}
				st.push_back({ t[i] - i, i});
			}
			else {
				while (st.size() && st.back().ff > T - i) st.pop_back();
				if (st.size()) {
					o = st.back().ss;
				}
				else o = -1;
			}
			//cout << o << ",";
			if(o >= start){
				int t = pls.par(o);
				st2[t].lz++; amt++;
				kill(t);
			}
			//cout << amt << ",";
		}
		//cout << endl;
		int c = st2[start].c;
		//cout << c << endl;
		if (c <= D) {
			r = m;
			ans = round((int)st2[start].v + (int)amt - (int)D * m);
		}
		else {
			//cout << "fuck" << endl;
			l = m + 1;
		}
	}
	cout << ans << endl;
	// n log n inverse ackermann n please pass i swear to god
}

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