#include <algorithm>
#include <cstdio>
#include <functional>
#include <limits>
using namespace std;
constexpr int MAXN = 2e5;
int n, m, a[MAXN + 1];
int dp[MAXN + 1];
int vals[MAXN + 1];
int tr[4 * MAXN + 1];
void build(int p, int l, int r) {
if (l == r) {
tr[p] = numeric_limits<int>::min();
return;
}
int mid = (l + r) / 2;
build(p * 2, l, mid);
build(p * 2 + 1, mid + 1, r);
tr[p] = max(tr[p * 2], tr[p * 2 + 1]);
}
int query(int s, int t, int p, int l, int r) {
if (s <= l && r <= t) {
return tr[p];
}
int mid = (l + r) / 2;
int ret = numeric_limits<int>::min();
if (s <= mid) {
ret = max(ret, query(s, t, p * 2, l, mid));
}
if (t > mid) {
ret = max(ret, query(s, t, p * 2 + 1, mid + 1, r));
}
return ret;
}
void update(int i, int x, int p, int l, int r) {
if (l == r) {
tr[p] = x;
return;
}
int mid = (l + r) / 2;
if (i <= mid) {
update(i, x, p * 2, l, mid);
} else {
update(i, x, p * 2 + 1, mid + 1, r);
}
tr[p] = max(tr[p * 2], tr[p * 2 + 1]);
}
int main() {
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; ++i) {
scanf("%d", &a[i]);
vals[i] = a[i] - i * m;
}
sort(vals, vals + n + 1, greater<>());
int p = unique(vals, vals + n + 1) - vals;
build(1, 0, p - 1);
update(lower_bound(vals, vals + p, 0, greater<>()) - vals, 0, 1, 0, p - 1);
for (int i = 1; i <= n; ++i) {
dp[i] = numeric_limits<int>::min();
int k = upper_bound(vals, vals + p, a[i] - i * m, greater<>()) - vals;
dp[i] = query(0, k - 1, 1, 0, p - 1) + 1;
update(k - 1, dp[i], 1, 0, p - 1);
}
printf("%d", n - *max_element(dp, dp + n + 1));
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
triusis.cpp: In function 'int main()':
triusis.cpp:54:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
54 | scanf("%d%d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~
triusis.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
56 | scanf("%d", &a[i]);
| ~~~~~^~~~~~~~~~~~~
# | 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... |