// Author: 4uckd3v - Nguyen Cao Duc
#include <bits/stdc++.h>
using namespace std;
#define all(x) (x).begin(), (x).end()
typedef long long ll;
typedef pair<int, int> ii;
const int MAX_N = 3e5;
const int MOD = 1e9 + 7;
template <class X, class Y>
bool maximize(X &x, const Y &y) {
if (x >= y) return false;
x = y;
return true;
};
struct FenwickTree {
int n;
vector<int> bit;
void update(int pos, int val) {
for (; pos > 0; pos -= pos & (-pos))
bit[pos] += val;
};
int get(int pos) {
int ret = 0;
for (; pos <= n; pos += pos & (-pos))
ret += bit[pos];
return ret;
};
FenwickTree(int n) : n(n) {
bit.assign(n + 5, 0);
};
};
int n, d;
int a[MAX_N + 5];
namespace SUBTASK_12 {
const int N = 400;
int dp[N + 5][N + 5];
void Solve() {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 0;
};
};
for (int i = 1; i <= n; i++) {
dp[i][a[i]] = 1;
for (int j = i - 1; j >= max(1, i - d); j--) {
for (int mx = a[j]; mx <= n; mx++) {
maximize(dp[i][max(mx, a[i])], dp[j][mx] + (a[i] > mx));
};
};
};
int res = 0;
for (int mx = a[n]; mx <= n; mx++) maximize(res, dp[n][mx]);
cout << res << '\n';
};
}; // namespace SUBTASK_12
namespace SUBTASK_3 {
const int N = 7000;
int dp[N + 5][N + 5], best[N + 5];
deque<int> dq[N + 5];
void Solve() {
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 0;
};
};
for (int i = 1; i <= n; i++) {
dp[i][a[i]] = 1;
for (int mx = 0; mx <= n; mx++) best[mx] = 0;
for (int mx = 0; mx <= n; mx++) {
while (!dq[mx].empty() && dq[mx].front() < max(i - d, 1)) dq[mx].pop_front();
if (!dq[mx].empty()) best[mx] = dp[dq[mx].front()][mx];
};
for (int mx = 0; mx <= n; mx++) {
maximize(dp[i][max(mx, a[i])], best[mx] + (a[i] > mx));
};
for (int mx = a[i]; mx <= n; mx++) {
while (!dq[mx].empty()) {
int j = dq[mx].back();
if (dp[j][mx] <= dp[i][mx])
dq[mx].pop_back();
else
break;
};
dq[mx].push_back(i);
};
};
int res = 0;
for (int mx = a[n]; mx <= n; mx++) maximize(res, dp[n][mx]);
cout << res << '\n';
};
}; // namespace SUBTASK_3
namespace SUBTASK_4 {
const int N = MAX_N;
const int D = 1;
bool mark[N + 5];
void Solve() {
FenwickTree bit(n);
int res = 0, curRank;
for (int i = n; i >= 1; i--) {
curRank = min(bit.get(a[i] + 1), curRank) + 1;
maximize(res, curRank);
if (!mark[a[i]]) bit.update(a[i], 1);
mark[a[i]] = true;
};
cout << res << '\n';
};
}; // namespace SUBTASK_4
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
if (fopen("MAIN.INP", "r")) {
freopen("MAIN.INP", "r", stdin);
freopen("MAIN.OUT", "w", stdout);
};
cin >> n >> d;
vector<ii> v(n);
for (int i = 1; i <= n; i++) {
cin >> a[i];
v[i - 1] = make_pair(a[i], i);
};
sort(all(v));
int cur = 0;
for (int i = 0; i < n; i++) {
cur += (i == 0 || v[i - 1].first != v[i].first);
a[v[i].second] = cur;
};
if (n <= 400)
return SUBTASK_12::Solve(), 0;
if (n <= 7000)
return SUBTASK_3::Solve(), 0;
if (d == 1)
return SUBTASK_4::Solve(), 0;
};
Compilation message (stderr)
Main.cpp: In function 'int main()':
Main.cpp:145:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
145 | freopen("MAIN.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:146:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
146 | freopen("MAIN.OUT", "w", stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |