Submission #996587

#	Time	Username	Problem	Language	Result	Execution time	Memory
996587		vjudge1	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	168 ms	21440 KiB

triusis

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <algorithm>
#include <cstring>

// miracle transformation: decrease each item by m*idx

#define ll long long
#define fst first
#define snd second
#define REP(i, n) for(long long i = 0; i < n; i++)

using namespace std;

ll n, m;

class MaxSegTree {
private:
	int len;
	vector<int> segtree;

public:
	MaxSegTree(int len) : len(len), segtree(2 * len) {}

	void set(int ind, int val) {
		for (segtree[ind += len] = val; ind > 1; ind >>= 1) {
			segtree[ind >> 1] = max(segtree[ind], segtree[ind ^ 1]);
		}
	}

	// maximum of the range [from, to)
	int range_max(int from, int to) {
		int max_ = INT32_MIN;
		for (from += len, to += len; from < to; from >>= 1, to >>= 1) {
			if ((from & 1) != 0) { max_ = max(max_, segtree[from++]); }
			if ((to & 1) != 0) { max_ = max(max_, segtree[--to]); }
		}
		return max_;
	}
};

int find_lis(vector<ll> a) {
	// apply coordinate compression to all elements of the array
	vector<ll> sorted(a);
	sort(sorted.begin(), sorted.end());
	int at = 0;
	map<ll, int> coord_comp;
	for (ll i : sorted) {
		if (!coord_comp.count(i)) { coord_comp[i] = at++; }
	}
	// cmp(i) gives the compressed version of index i
	auto cmp = [&](int i) -> int { return coord_comp[a[i]]; };

	MaxSegTree dp(coord_comp.size());
	dp.set(cmp(0), 1);
	for (int i = 1; i < a.size(); i++) {
		int max_prev = dp.range_max(0, cmp(i) + 1);
		if (max_prev != INT32_MIN) {
			dp.set(cmp(i), max_prev + 1);
		}
		else {
			dp.set(cmp(i), 1);
		}
	}

	return dp.range_max(0, coord_comp.size());
}

signed main() {
	cin >> n >> m; // size of arr, jump dist

	vector<ll> arr(n + 1); arr[0] = 0; // this is key... need to account for the fact that we START at the ground
	REP(i,n) {
		ll t; cin >> t;
		arr[i+1] = t - m*(i+1); // MIRACLE TRANSFORMATION!!!! now, the question becomes: min # of indices to remove so the array is non-increasing
		// equivalent to finding the backwards LIS!
	}
	//cout << "original arr: \n"; for (int i = 0; i <= n; i++) cout << arr[i] << " "; cout << "\n";

	reverse(arr.begin(), arr.end()); // NOW, trying to find least # of indices needed to be removed so the array is non-decreasing

	//cout << "reversed arr: \n"; for (int i = 0; i <= n; i++) cout << arr[i] << " "; cout << "\n";

	vector<ll> withoutPos; // this is tricky -- positive values are obviously impossible to reach from 0 while only going down, so they always add +1
						// after we +1, we can guarentee that it doesn't influence others
	int positives = 0;
	for (int i = 0; i <= n; i++) {
		if (arr[i] > 0) positives++;
		else withoutPos.push_back(arr[i]);
	}

	//cout << "without positives: \n"; for (int i = 0; i < withoutPos.size(); i++) cout << withoutPos[i] << " "; cout << "\n";


	cout << positives + withoutPos.size() - find_lis(withoutPos) << endl; // since positives + withoutPos.size() always equals n+1, we could've just done that too
}

Compilation message (stderr)

triusis.cpp: In function 'int find_lis(std::vector<long long int>)':
triusis.cpp:59:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |  for (int i = 1; i < a.size(); i++) {
      |                  ~~^~~~~~~~~~

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