oj.uz

Submission #996587

# Submission time Handle Problem Language Result Execution time Memory
996587 2024-06-10T21:09:59 Z vjudge1 Rabbit Carrot (LMIO19_triusis) C++17
100 / 100
 168 ms 21440 KB 
#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

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.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 2 ms 860 KB Output is correct
21 Correct 2 ms 856 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 3 ms 960 KB Output is correct
24 Correct 2 ms 860 KB Output is correct
25 Correct 3 ms 752 KB Output is correct
26 Correct 3 ms 860 KB Output is correct
27 Correct 1 ms 584 KB Output is correct
28 Correct 1 ms 604 KB Output is correct
29 Correct 3 ms 748 KB Output is correct
30 Correct 3 ms 860 KB Output is correct
31 Correct 2 ms 604 KB Output is correct
32 Correct 3 ms 860 KB Output is correct
33 Correct 3 ms 856 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 2 ms 860 KB Output is correct
5 Correct 2 ms 856 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 3 ms 960 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 3 ms 752 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 1 ms 584 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 3 ms 748 KB Output is correct
14 Correct 3 ms 860 KB Output is correct
15 Correct 2 ms 604 KB Output is correct
16 Correct 3 ms 860 KB Output is correct
17 Correct 3 ms 856 KB Output is correct
18 Correct 1 ms 344 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 348 KB Output is correct
29 Correct 1 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 2 ms 344 KB Output is correct
35 Correct 1 ms 448 KB Output is correct
36 Correct 2 ms 348 KB Output is correct
37 Correct 3 ms 860 KB Output is correct
38 Correct 1 ms 516 KB Output is correct
39 Correct 2 ms 604 KB Output is correct
40 Correct 2 ms 604 KB Output is correct
41 Correct 1 ms 348 KB Output is correct
42 Correct 2 ms 860 KB Output is correct
43 Correct 3 ms 860 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 344 KB Output is correct
2 Correct 1 ms 448 KB Output is correct
3 Correct 2 ms 348 KB Output is correct
4 Correct 3 ms 860 KB Output is correct
5 Correct 1 ms 516 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 3 ms 860 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 2 ms 860 KB Output is correct
15 Correct 2 ms 856 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 3 ms 960 KB Output is correct
18 Correct 2 ms 860 KB Output is correct
19 Correct 3 ms 752 KB Output is correct
20 Correct 3 ms 860 KB Output is correct
21 Correct 1 ms 584 KB Output is correct
22 Correct 1 ms 604 KB Output is correct
23 Correct 3 ms 748 KB Output is correct
24 Correct 3 ms 860 KB Output is correct
25 Correct 2 ms 604 KB Output is correct
26 Correct 3 ms 860 KB Output is correct
27 Correct 3 ms 856 KB Output is correct
28 Correct 1 ms 344 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 0 ms 348 KB Output is correct
35 Correct 1 ms 348 KB Output is correct
36 Correct 0 ms 348 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 1 ms 348 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 348 KB Output is correct
42 Correct 0 ms 348 KB Output is correct
43 Correct 0 ms 348 KB Output is correct
44 Correct 128 ms 20928 KB Output is correct
45 Correct 49 ms 3152 KB Output is correct
46 Correct 121 ms 12600 KB Output is correct
47 Correct 123 ms 12620 KB Output is correct
48 Correct 138 ms 21184 KB Output is correct
49 Correct 141 ms 21440 KB Output is correct
50 Correct 55 ms 6852 KB Output is correct
51 Correct 55 ms 7876 KB Output is correct
52 Correct 115 ms 14272 KB Output is correct
53 Correct 33 ms 2648 KB Output is correct
54 Correct 168 ms 21436 KB Output is correct
55 Correct 141 ms 21188 KB Output is correct