#include<bits/stdc++.h>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define int long long
#define pb push_back
using namespace std;
typedef pair<int,int> ii;
typedef tuple<int,int,int> tp;
const int M = 1e6 + 10;
const int N = 1e3 + 10;
const int mod = 1e9 + 7;
int n, m, f[M], a[M];
int t[4 * M];
void upd(int s,int l,int r,int pos,int val)
{
if(l > pos || r < pos) return ;
if(l == r) {
t[s] = val;
return ;
}
int mid = (l + r)/2;
upd(s * 2, l, mid, pos, val);
upd(s * 2 + 1, mid + 1, r, pos, val);
t[s] = max(t[s * 2], t[s * 2 + 1]);
}
int get(int s,int l,int r,int u,int v)
{
if(l > v || r < u) return 0;
if(u <= l && r <= v) return t[s];
int mid = (l + r)/2;
return max(get(s * 2, l, mid, u, v), get(s * 2 + 1, mid + 1, r, u, v));
}
vector<int> rrh;
int32_t main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
if(fopen("1.inp","r")) {
freopen("1.inp","r",stdin);
freopen("1.out","w",stdout);
}
#define task ""
if(fopen(task".inp","r")) {
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
cin >> n >> m;
for(int i = 1;i <= n; i++) {
cin >> a[i];
rrh.pb(i * m - a[i]);
}
rrh.pb(0);
sort(rrh.begin(), rrh.end());
//for(int v : rrh) cout << v << " ";
for(int i = 0;i <= 4 * n; i++) t[i] = -1e9;
int idx = lower_bound(rrh.begin(), rrh.end(), 0) - rrh.begin();
upd(1, 0, n, idx, 0);
for(int i = 1; i<= n; i++) {
idx = lower_bound(rrh.begin(),rrh.end(),i * m - a[i]) - rrh.begin() - 1;
if(idx == -1) continue;
//cout << idx << " " << rrh[idx] << "\n";
f[i] = get(1, 0, n, 0, idx) + 1;
upd(1, 0, n, idx, f[i]);
}
int kq = n;
for(int i = 1;i <= n; i++) {
kq = min(kq, n - f[i]);
}
cout << kq;
}
Compilation message (stderr)
triusis.cpp: In function 'int32_t main()':
triusis.cpp:45:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
45 | freopen("1.inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~
triusis.cpp:46:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
46 | freopen("1.out","w",stdout);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~
triusis.cpp:51:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
51 | freopen(task".inp","r",stdin);
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
triusis.cpp:52:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
52 | freopen(task".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... |