Submission #483326

#	Time	Username	Problem	Language	Result	Execution time	Memory
483326		benk	Rabbit Carrot (LMIO19_triusis)	C++17	0 / 100	1 ms	472 KiB

triusis

#include "bits/stdc++.h"
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define all(x)      x.begin(), x.end()
#define pb          push_back
#define sz(x)       (int)(x.size())
#define ll          long long
#define fi          first
#define se          second
#define lbd         lower_bound
#define ubd         upper_bound

template <typename T>
using ordered_set = tree<T, null_type,
      less<T>, rb_tree_tag,
      tree_order_statistics_node_update>;

const int MOD = 1e9 + 7;
const double eps = 1e-10;
const long long INF = 1e18;
const int N = 2e5 + 10;


struct node {
	int ans = -MOD;
	int lazy = 0;
	bool islazy = false;
	// only used to assign value to 'leaf' nodes in build and pupd
	void assign(int val) {
		ans = max(val, ans);
	}
	// used in build, rquery, pupd, rupd
	void merge(const node & l, const node & r) {
		ans = max(l.ans, r.ans);
	}
};

struct SegTree {
	int32_t len = 0;
	node zero;
	vector<node> tree;

	SegTree (int32_t _len = N) {
		len = _len;
		tree.resize((len << 2) + 10);
	}

	// if a node has lazy tag then its info is correct but its children's info
	// is old, so pushdown() before going into children
	inline void pushdown(int32_t v, int32_t cl, int32_t cr) {
		if (!tree[v].islazy) return;

		int32_t mid = (cl + cr) >> 1;
		apply((v << 1), cl, mid, tree[v].lazy);
		apply(((v << 1) | 1), mid + 1, cr, tree[v].lazy);

		tree[v].lazy = zero.lazy;
		tree[v].islazy = false;
		return;
	}
	// apply() is an auxillary function to apply range update and set lazy tag
	inline void apply(int32_t v, int32_t cl, int32_t cr, int val) {
		if (cl != cr) {
			tree[v].lazy;				// modify the lazy by val, eg. lazy += val
			tree[v].islazy = true;
		}
		// incorporate the change (=val) in node
		
		return;
	}
	void build(vector<int32_t> &a, int32_t v, int32_t cl, int32_t cr) {
		if (cl == cr) {
			tree[v].assign(a[cl]);
			return;
		}
		int32_t mid = (cl + cr) >> 1;
		build(a, (v << 1), cl, mid);
		build(a, ((v << 1) | 1), mid + 1, cr);
		tree[v].merge(tree[(v << 1)], tree[((v << 1) | 1)]);
		return;
	}
	void build(vector<int32_t> &a) {
		build(a, 1, 0, len - 1);
		return;
	}
	node pquery(int32_t v, int32_t cl, int32_t cr, int32_t pos) {
		if (cl == cr) return tree[v];
		pushdown(v, cl, cr);
		int32_t mid = (cl + cr) >> 1;
		if (pos <= mid) return pquery((v << 1), cl, mid, pos);
		return pquery(((v << 1) | 1), mid + 1, cr, pos);
	}
	node pquery(int32_t pos) {
		return pquery(1, 0, len - 1, pos);
	}
	node rquery(int32_t v, int32_t cl, int32_t cr, int32_t l, int32_t r) {
		if (l > cr || r < cl) return zero;
		if (l <= cl && cr <= r) return tree[v];
		pushdown(v, cl, cr);
		int32_t mid = (cl + cr) >> 1;
		node a, b, ans;
		a = rquery((v << 1), cl, mid, l, r);
		b = rquery(((v << 1) | 1), mid + 1, cr, l, r);
		ans.merge(a, b);
		return ans;
	}
	node rquery(int32_t l, int32_t r) {
		return rquery(1, 0, len - 1, l, r);
	}
	void pupd(int32_t v, int32_t cl, int32_t cr, int32_t pos, int val) {
		if (cl == cr) {
			tree[v].assign(val);
			return;
		}
		pushdown(v, cl, cr);
		int32_t mid = (cl + cr) >> 1;
		if (pos <= mid) {
			pupd((v << 1), cl, mid, pos, val);
		} else {
			pupd(((v << 1) | 1), mid + 1, cr, pos, val);
		}
		tree[v].merge(tree[(v << 1)], tree[((v << 1) | 1)]);
		return;
	}
	void pupd(int32_t pos, int val) {
		pupd(1, 0, len - 1, pos, val);
		return;
	}
	void rupd(int32_t v, int32_t cl, int32_t cr, int32_t l, int32_t r, int val) {
		if (l > cr || r < cl) return;
		if (l <= cl && cr <= r) {
			apply(v, cl, cr, val);
			return;
		}
		pushdown(v, cl, cr);
		int32_t mid = (cl + cr) >> 1;
		rupd((v << 1), cl, mid, l, r, val);
		rupd(((v << 1) | 1), mid + 1, cr, l, r, val);
		tree[v].merge(tree[(v << 1)], tree[((v << 1) | 1)]);
		return;
	}
	void rupd(int32_t l, int32_t r, int val) {
		rupd(1, 0, len - 1, l, r, val);
	}
	/*
	int right_descend(int32_t v, int32_t cl, int32_t cr, int32_t l, int32_t r, int val) {
		if (cl > r || cr < l) return -1;
		if (l <= cl && cr <= r) {
			if (tree[v]) return -1;
		}
		if (cl == cr) return cl;
		pushdown(v, cl, cr);
		int32_t mid = (cl + cr) >> 1;
		int res = right_descend((v << 1), cl, mid, l, r, val);
		if (res != -1) return res;
		return right_descend(((v << 1) | 1), mid + 1, cr, l, r, val);
	}
	int right_descend(int l, int r, int val) {
		return right_descend(1, 0, len - 1, l, r, val);
	}
	*/
};

void solve() {
	int n, m;
	cin >> n >> m;
	vector<int> v(n + 1);
	for (int i = 1; i <= n; i++) {
		cin >> v[i];
	}
	vector<int> a(v);
	a.pb(0);
	sort(all(a));
	a.erase(unique(all(a)), a.end());
	auto id = [&](int x) {return lbd(all(a), x) - a.begin();};
	SegTree st(5010);
	st.pupd(0, 0);
	for (int i = 1; i <= n; i++) {
		auto it = id(*lbd(all(a), max(0, v[i] - m)));
		st.pupd(id(v[i]), st.rquery(it, 5001).ans + 1);
	}
	cout << n - st.rquery(0, 5001).ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	int tt = 1;
	//cin >> tt;
	while (tt--) {
		solve();
		cout << '\n';
	}
	return 0;
}

• Subtask 1: 0 / 14
• Subtask 2: 0 / 21
• Subtask 3: 0 / 28
• Subtask 4: 0 / 37