Submission #444233

#	Time	Username	Problem	Language	Result	Execution time	Memory
444233		8e7	The short shank; Redemption (BOI21_prison)	C++17	35 / 100	2086 ms	52072 KiB

prison

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
#include <set>
#include <stack>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
//using namespace __gnu_pbds;
void debug() {cout << endl;}
template<class T, class ... U> void debug(T a, U ... b) {cout << a << " ", debug(b ...);}
template<class T> void pary(T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 100005
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);
int dp[2][maxn];
int rig[maxn], suf[maxn];
struct node{
	int sum;
	bool tag;
	node * lc, * rc;
	node() {sum = 0, tag = 0, lc = NULL, rc = NULL;}
	node(node * x) {sum = x->sum, tag = x->tag, lc = x->lc, rc = x->rc;}
};
struct segtree{
	
	node * root = new node();
	void pull(node *cur, int l, int r) {
		if (cur->tag) {
			cur->sum = r - l;
			return;
		}
		cur->sum = cur->lc->sum + cur->rc->sum;
	}
	void modify(node * cur, int l, int r, int ql, int qr) {
		if (r <= l || ql >= r || qr <= l) return;
		if (ql <= l && qr >= r) {
			cur->tag = 1, cur->sum = r - l;
			return;
		}
		int mid = (l + r) / 2;
		if (!cur->lc) cur->lc = new node();
		else cur->lc = new node(cur->lc);
		if (!cur->rc) cur->rc = new node();
		else cur->rc = new node(cur->rc);
		modify(cur->lc, l, mid, ql, qr), modify(cur->rc, mid, r, ql, qr);
		pull(cur, l, r);	
	}
	int query(node * cur, int l, int r, int ql, int qr) {
		if (!cur) return 0;
		if (r <= l || ql >= r || qr <= l) return 0;
		if (ql <= l && qr >= r) return cur->sum;
		int mid = (l + r) / 2;
		if (cur->tag) return min(r, qr) - max(l, ql);
		return (cur->lc ? query(cur->lc, l, mid, ql, qr) : 0) + 
			(cur->rc ? query(cur->rc, mid, r, ql, qr) : 0);
	}	
} seg[maxn];
int n;
int f(int l, int r) {
	r++;
	return suf[l] - seg[l].query(seg[l].root, 1, n + 1, r, n + 1);
}
void solve(int l, int r, int ql, int qr) {
	if (l >= r) return;
	int mid = (l + r) / 2;
	int bind = mid - 1;
	for (int i = ql;i < min(qr, mid);i++) {
		int val = dp[0][i] + f(i + 1, mid);	
		//debug(i, val, dp[1][mid]);
		if (val < dp[1][mid]) {
			dp[1][mid] = val;
			bind = i;
		}
	}
	//debug(mid, bind, ql, qr);
	if (r - l > 1) {
		solve(l, mid, ql, bind + 1);
		solve(mid + 1, r, bind, qr);
	}
}
const int inf = 8e7;
int main() {
	io
	int k, t;
	cin >> n >> k >> t;
	for (int i = 1;i <= n;i++) {
		int ti;
		cin >> ti;
		if (ti <= t) {
			rig[i] = min(n, i + t - ti); //[i, a[i]]
		} 
	}
	for (int i = n;i > 0;i--) {
		seg[i].root = new node(seg[i + 1].root);
		if (rig[i]) {
			seg[i].modify(seg[i].root, 1, n + 1, i, rig[i] + 1);	
		}
		suf[i] = seg[i].query(seg[i].root, 1, n + 1, i, n + 1);
	}	
	for (int i = 1;i <= n;i++) dp[0][i] = f(1, i), dp[1][i] = inf;
	for (int i = 1;i <= k;i++) {
		solve(1, n + 1, 0, n + 1);	
		for (int j = 1;j <= n;j++) dp[0][j] = dp[1][j], dp[1][j] = inf;
	}
	cout << dp[0][n] << endl;
}
/*
5 1 42
13 37 47 11 42


5 1 5
4 7 4 7 9
  */

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