// 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;
};
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;
void Solve() {
int res = 0;
stack<int> st;
for (int i = n; i >= 1; i--) {
while (!st.empty() && a[st.top()] <= a[i]) st.pop();
st.push(i);
maximize(res, st.size());
};
cout << res << '\n';
};
}; // namespace SUBTASK_4
namespace SUBTASK_5 {
const int N = MAX_N;
const int D = N;
int bit[N + 5];
void update(int pos, int val) {
for (; pos <= n; pos += pos & (-pos)) maximize(bit[pos], val);
};
int get(int pos) {
int ret = 0;
for (; pos > 0; pos -= pos & (-pos)) maximize(ret, bit[pos]);
return ret;
};
void Solve() {
int res = 0;
for (int i = 1; i <= n; i++) {
int lis = get(a[i] - 1) + 1;
maximize(res, lis);
update(a[i], lis);
};
cout << res << '\n';
};
}; // namespace SUBTASK_5
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;
if (d == n)
return SUBTASK_5::Solve(), 0;
};
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:144:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
144 | freopen("MAIN.INP", "r", stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
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.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... |