Submission #828916

#	Time	Username	Problem	Language	Result	Execution time	Memory
828916		QwertyPi	The short shank; Redemption (BOI21_prison)	C++14	10 / 100	296 ms	139532 KiB

prison

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

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];
	}
	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[17][75011];

int32_t main(){
	cin.tie(0); cout.tie(0)->sync_with_stdio(false);
	int n, d, t; 
	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(0, 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;
	});

	fill(dp[0] + 1, dp[0] + n + 1, 1 << 30);
	for(int i = 0; i <= d; i++){
		int ri = 0; ST.init(0, 0, n);
		for(int j = 0; j < n; j++){
			ST.point_update(j, dp[i][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[i + 1][j + 1] = ST.range_min();
		}
	}

	for(int i = 0; i < d; i++){
		assert(dp[i + 1][n] - dp[i][n] <= dp[i + 2][n] - dp[i + 1][n]);
	}
	int mx = ps[n - 1] - dp[d + 1][n];
	cout << ans - mx << endl;
}

Compilation message (stderr)

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

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