#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);
REP(i,n) {
ll t; cin >> t;
arr[i] = t - m*i; // MIRACLE TRANSFORMATION!!!! now, the question becomes: min # of indices to remove so the array is non-increasing
// equivalent to finding the backwards LIS!
}
reverse(arr.begin(), arr.end()); // NOW, trying to find least # of indices needed to be removed so the array is non-decreasing
cout << n - find_lis(arr) << endl;
}
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++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
344 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
348 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
