This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define ll long long
const ll I = 2e5 + 9;
using namespace std;
int tf = 0, n, M, dpm[I];
int main()
{
cin.tie(0)->sync_with_stdio(0);
cin >> n >> M;
dpm[1] = 0;
tf = 1;
for (int i = 1; i <= n; i++)
{
int x;
cin >> x;
if (x > i * M)
continue;
x = x - i * M;
if (x <= dpm[tf])
{
tf++;
dpm[tf] = x;
}
else
{
int l_ = 1, r_ = tf, sav = 0, tg;
while (l_ <= r_)
{
tg = (l_ + r_) / 2;
if (dpm[tg] >= x)
{
sav = tg;
l_ = tg + 1;
}
else
r_ = tg - 1;
}
dpm[sav + 1] = max(dpm[sav + 1], x);
}
}
cout << n - tf + 1;
return 0;
}
# | 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... |