| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1288658 | herominhsteve | Rabbit Carrot (LMIO19_triusis) | C++20 | 0 ms | 0 KiB |
https://usaco.guide/gold/lis#problem-lmio-19-triusis#include <bits/stdc++.h>
#define el '\n'
#define FNAME "LMIO19_triusis"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}
void setup(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
if (fopen(FNAME".inp","r")){
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
template<typename T>
struct FenwickTree{
int n;
vector<T> bit;
FenwickTree(int N=0){
n=N;
if (n>0){
bit.resize(n+1,0);
}
}
void update(int node,T val){
while (node<=n){
maximize(bit[node],val);
node += (node & -node);
}
}
T getVal(int node){
T res=0;
while (node>0){
maximize(res,bit[node]);
node -= (node & -node);
}
return res;
}
};
int n,m;
vector<int> a;
void init(){
cin>>n>>m;
a.resize(n);
for (int &x : a) cin>>x;
}
void sol(){
vector<int> b;
vector<int> org;
org.reserve(n);
for (int i=0;i<n;i++)
if ((i+1) * m >= a[i]) org.push_back((i+1) * m - a[i]);
vector<int> compress(allof(org));
sort(allof(compress));
compress.resize(unique(allof(compress))-compress.begin());
int MAX = compress.size();
b.resize(org.size());
for (int i=0;i<(int)org.size();i++)
b[i] = lower_bound(allof(compress),org[i]) - compress.begin() + 1;
FenwickTree<int> bit(MAX);
for (int x : b){
bit.update(x,bit.getVal(x) + 1);
}
cout<< n - bit.getVal(MAX);
}
int main(){
setup();
init();
sol();
}