#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
const int MAX_A = 5e3;
template<typename T>
struct segtree {
T size;
vector<T> val;
T id = 1e9;
segtree(T n) {
size = 1;
while (size < n) {
size *= 2;
}
val.assign(size * 2, id);
}
void update(T i, T v, T x, T lx, T rx) {
if (rx - lx == 1) {
val[x] = v;
return;
}
T mid = (lx + rx) / 2;
if (i < mid) {
update(i, v, 2 * x + 1, lx, mid);
} else {
update(i, v, 2 * x + 2, mid, rx);
}
val[x] = max(val[2 * x + 1], val[2 * x + 2]);
}
void update(T i, T v) {
update(i, v, 0, 0, size);
}
T query(T l, T r, T x, T lx, T rx) {
if (r <= lx || l >= rx) {
return id;
}
if (lx >= l && rx <= r) {
return val[x];
}
T mid = (lx + rx) / 2;
T calc1 = query(l, r, 2 * x + 1, lx, mid);
T calc2 = query(l, r, 2 * x + 2, mid, rx);
return max(calc1, calc2);
}
T query(T l, T r) {
if (l == r) {
return id;
}
return query(l, r, 0, 0, size);
}
};
int solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i] -= i * m;
}
vector<int> sorted(a);
sort(sorted.begin(), sorted.end());
int at = 0;
map<int, int> coord_comp;
for (int 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]]; };
segtree<int> dp(coord_comp.size());
dp.update(cmp(0), 1);
for (int i = 1; i < a.size(); i++) {
int max_prev = dp.query(cmp(i), coord_comp.size());
if (max_prev != 1e9) {
dp.update(cmp(i), max_prev + 1);
} else {
dp.update(cmp(i), 1);
}
}
cout << dp.query(0, coord_comp.size());
return 0;
}
#ifndef MY_UNIT_TEST
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
}
#endif
Compilation message
triusis.cpp: In function 'int solve()':
triusis.cpp:83:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
83 | for (int i = 1; i < a.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
344 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
