제출 #952907

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
952907		SirCovidThe19th	The short shank; Redemption (BOI21_prison)	C++17	80 / 100	2029 ms	77272 KiB

prison

/*
*       ___
*   _ /    _\_
*  / |    |___|
*  | |       |
*  \_|   __  |
*     \_/  \_/
*   uwu amogus
*/
#pragma GCC optimize("O3,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;
};
 
signed main() {
  ios_base::sync_with_stdio(false); cin.tie(NULL);
	int N, D, T; cin >> N >> D >> T;
	vector<int> t(N); for (auto& x : t) cin >> 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