Submission #1016022

#	Time	Username	Problem	Language	Result	Execution time	Memory
1016022		vjudge1	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	105 ms	8396 KiB

triusis

#include <bits/stdc++.h>
using namespace std;

const int inf = 1109200169;

vector<long long> tbc{0};

void compress() {sort(tbc.begin(), tbc.end()); tbc.resize(unique(tbc.begin(), tbc.end()) - tbc.begin());}
int order(long long key) {return lower_bound(tbc.begin(), tbc.end(), key) - tbc.begin() + 1;}

long long a[200008];
struct Segment_Tree {
	int n;
	int node[(1 << 19) + 8];
	
	Segment_Tree() {fill(node + 1, node + (1 << 19) + 8, -inf);};
	
	void update(int id, int l, int r, int i, int val) {
		if (l == r) {node[id] = max(node[id], val); return;}
		int mid = (l + r) / 2;
		if (i <= mid) update(id * 2, l, mid, i, val);
		else update(id * 2 + 1, mid + 1, r, i, val);
		node[id] = max(node[id * 2], node[id * 2 + 1]);
	}
	
	int query(int id, int l, int r, int u, int v) {
		if (r < u || v < l) return -inf;
		if (u <= l && r <= v) return node[id];
		int mid = (l + r) / 2;
		int opt1 = query(id * 2, l, mid, u, v);
		int opt2 = query(id * 2 + 1, mid + 1, r, u, v);
		return max(opt1, opt2);
	}
	
	void update(int i, int val) {update(1, 1, n, i, val);}
	int query(int l, int r) {return query(1, 1, n, l, r);}
} tree;

int dp[200008];

signed main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m, ans = 1; cin >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> a[i], a[i] = -(a[i] - 1LL * i * m), tbc.push_back(a[i]);
	compress(); tree.n = tbc.size();
	for (int i = 0; i <= n; ++i) a[i] = order(a[i]);
	dp[0] = 1; tree.update(a[0], dp[0]);
	for (int i = 1; i <= n; ++i) {
		dp[i] = tree.query(1, a[i]) + 1;
		tree.update(a[i], dp[i]); ans = max(ans, dp[i]);
	}
	cout << n + 1 - ans;
}

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