Submission #828920

#	Time	Username	Problem	Language	Result	Execution time	Memory
828920		QwertyPi	The short shank; Redemption (BOI21_prison)	C++14	70 / 100	2056 ms	92088 KiB

prison

#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("Ofast")
#define int long long

using namespace std;

const int N = 2e6 + 11;
int a[N];
int ps[N];
vector<int> rm[N];

struct range{
	int l, r;
};

struct SegTree{
	int t[1 << 22], lz[1 << 22];
	void push(int v){
		if(lz[v]){
			lz[v * 2 + 1] += lz[v];
			lz[v * 2 + 2] += lz[v];
			t[v * 2 + 1] += lz[v];
			t[v * 2 + 2] += lz[v];
			lz[v] = 0;
		}
	}
	void init(int v, int l, int r){
		if(l == r) t[v] = (1 << 30), lz[v] = 0;
		else {
			int m = (l + r) / 2;
			init(v * 2 + 1, l, m);
			init(v * 2 + 2, m + 1, r);
			t[v] = 1 << 30, lz[v] = 0;
		}
	}
	void range_add(int ql, int qr, int qv, int v, int l, int r){
		if(qr < l || r < ql) return;
		if(ql <= l && r <= qr) t[v] += qv, lz[v] += qv;
		else {
			push(v);
			int m = (l + r) / 2;
			range_add(ql, qr, qv, v * 2 + 1, l, m);
			range_add(ql, qr, qv, v * 2 + 2, m + 1, r);
			t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
		}
	}
	int range_min(){
		return t[0];
	}
	int arg_min(int v, int l, int r){
		if(l == r) return l;
		push(v);
		int m = (l + r) / 2;
		if(t[v * 2 + 1] == t[v]) return arg_min(v * 2 + 1, l, m);
		else return arg_min(v * 2 + 2, m + 1, r);
	}
	void point_update(int qi, int qv, int v, int l, int r){
		if(l == r) t[v] = qv;
		else {
			push(v);
			int m = (l + r) / 2;
			if(qi <= m) point_update(qi, qv, v * 2 + 1, l, m);
			else point_update(qi, qv, v * 2 + 2, m + 1, r);
			t[v] = min(t[v * 2 + 1], t[v * 2 + 2]);
		}
	}
} ST;

int dp[N], c[N];

int n, d, t; 
pair<int, int> calc(int pen, const vector<range>& R){
	fill(dp + 1, dp + n + 1, 1 << 30);
	int ri = 0; ST.init(0, 0, n);
	for(int j = 0; j < n; j++){
		ST.point_update(j, dp[j], 0, 0, n);
		while(ri < R.size() && R[ri].r < j) ST.range_add(0, R[ri].l, 1, 0, 0, n), ri++;
		dp[j + 1] = ST.range_min() + pen; c[j + 1] = c[ST.arg_min(0, 0, n)] + 1;
	}
	return {dp[n] - pen * c[n], c[n] - 1};
}

int32_t main(){
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	vector<range> R;
	int ans = 0;
	
#ifdef RANGE
	cin >> n >> d;
	for(int i = 0; i < n; i++){
		int l, r; cin >> l >> r; R.push_back({l, r});
	}
#else	
	cin >> n >> d >> t;
	for(int i = 0; i < n; i++){
		cin >> a[i]; a[i] = max(0LL, t - a[i] + 1);
	}

	for(int i = 0; i < n; i++){
		if(a[i] == 0) a[i] = -1;
		else a[i] = min(n, i + a[i]), rm[a[i]].push_back(i);
	}

	priority_queue<int> pq1, pq2;

	for(int i = 0; i < n; i++){
		for(auto j : rm[i]) pq2.push(j);
		while(pq1.size() && pq2.size() && pq1.top() == pq2.top()) pq1.pop(), pq2.pop();
		if(a[i] == -1){
			if(!pq1.empty()) R.push_back({pq1.top(), i - 1}), ans++;
		}else{
			pq1.push(i);
			ans++;
		}
	}
#endif

	for(auto [l, r] : R){
		ps[r]++;
	}
	for(int i = 0; i < n - 1; i++){
		ps[i + 1] += ps[i];
	}

	sort(R.begin(), R.end(), [](range a, range b){
		return a.r < b.r;
	});

	int lo = 0, hi = n;
	while(lo + 1 < hi){
		int mid = (lo + hi) / 2;
		pair<int, int> res = calc(mid, R);
		if(res.second > d) lo = mid;
		else hi = mid;
		// printf("calc(%d) = {%d, %d}\n", mid, res.first, res.second);
	}

	pair<int, int> r1 = calc(lo, R);
	pair<int, int> r2 = calc(hi, R);

	int mn;
	if(r1.second == r2.second){
		assert(r1.second == d);
		mn = r1.first;
	}else{
		mn = r1.first + (r2.first - r1.first) * (d - r1.second) / (r2.second - r1.second);
	}
	cout << ans - ps[n - 1] + mn << endl;
}

Compilation message (stderr)

prison.cpp: In function 'std::pair<long long int, long long int> calc(long long int, const std::vector<range>&)':
prison.cpp:78:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<range>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |   while(ri < R.size() && R[ri].r < j) ST.range_add(0, R[ri].l, 1, 0, 0, n), ri++;
      |         ~~~^~~~~~~~~~
prison.cpp: In function 'int32_t main()':
prison.cpp:119:11: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |  for(auto [l, r] : R){
      |           ^

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