Submission #1256289

#	Time	Username	Problem	Language	Result	Execution time	Memory
1256289		_filya_	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	216 ms	20204 KiB

triusis

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

struct segtree {

	vector<ll> tree;
	int size;

	void init(int n) {
		size = 1;
		while (size < n)
			size *= 2;
		tree.assign(2 * size - 1, 0);
	}

	void build(vector<int>& a, int x, int lx, int rx) {
		if (rx - lx == 1) {
			if (lx < a.size())
				tree[x] = a[lx];
		}
		else {
			int m = (lx + rx) / 2;
			build(a, 2 * x + 1, lx, m);
			build(a, 2 * x + 2, m, rx);
			tree[x] = max(tree[2 * x + 1], tree[2 * x + 2]);
		}
	}

	void build(vector<int>& a) {
		init(a.size());
		build(a, 0, 0, size);
	}

	void set(int i, int v, int x, int lx, int rx) {
		if (rx - lx == 1) {
			tree[x] = v;
			return;
		}
		int m = (lx + rx) / 2;
		if (i < m) {
			set(i, v, 2 * x + 1, lx, m);
		}
		else {
			set(i, v, 2 * x + 2, m, rx);
		}
		tree[x] = max(tree[2 * x + 1], tree[2 * x + 2]);
	}

	void set(int i, int v) {
		set(i, v, 0, 0, size);
	}

	ll query(int l, int r, int x, int lx, int rx) {
		if (l >= rx || r <= lx) {
			return 0;
		}
		if (lx >= l && rx <= r) {
			return tree[x];
		}
		int m = (lx + rx) / 2;
		ll mi1 = query(l, r, 2 * x + 1, lx, m);
		ll mi2 = query(l, r, 2 * x + 2, m, rx);
		return max(mi1, mi2);
	}

	ll query(int l, int r) {
		return query(l, r, 0, 0, size);
	}
};

void compress(vector<ll>& a) {
    int n = a.size();
    vector<ll> b = a;
    map<ll, ll> mp;
    sort(b.begin(), b.end());
    for (int i = 0; i < n; i++) {
        mp[b[i]] = i + 1;
    }
    for (int i = 0; i < n; i++) {
        a[i] = mp[a[i]];
    }
}

int main()
{
// 	ifstream cin("input.txt");
//     ofstream cout("output.txt");
	ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
	ll n, m; cin >> n >> m;
    vector<ll> a(n + 1);
    segtree dp;
    dp.init(n + 10);
    auto f = [&](ll x) -> ll {
        return x * m - a[x];
    };
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        a[i] = f(i);
    }
    compress(a);
    ll ans = 0;
    for (int i = n; i >= 0; i--) {
        ll nw = max(dp.query(a[i], n + 10) + 1, dp.query(a[i], a[i + 1]));
        dp.set(a[i], nw);
        if (!i) ans = nw;
    }
    cout << a.size() - ans << '\n';
}

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