# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1228756 | kokokai | Rabbit Carrot (LMIO19_triusis) | C++20 | 167 ms | 17664 KiB |
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
struct fenwick{
vector<ll> fw;
int n;
fenwick(int _n){
n=_n;
fw.resize(n+2,0);
}
void update(int idx,ll val){
for(;idx<=n;idx+=idx&(-idx)){
fw[idx] = max(fw[idx],val);
}
}
ll get(int idx){
ll res=0;
for(;idx>0;idx -= idx&(-idx)){
res=max(res,fw[idx]);
}
return res;
}
};
void solve(){
ll n,m;
cin>>n>>m;
vector<ll> a(n+1);
vector<ll> tmp;
tmp.push_back(0);
for(int i=1;i<=n;i++){
cin>>a[i];
a[i]=a[i]-(ll)(i*m);
tmp.push_back(a[i]);
}
map<ll,ll> nen;
sort(tmp.begin(),tmp.end());
tmp.erase(unique(tmp.begin(),tmp.end()),tmp.end());
int cnt=0;
for(auto v:tmp){
nen[v]=++cnt;
}
fenwick fw(n+2);
ll ans=0;
for(int i=n;i>=0;i--){
int idx=nen[a[i]];
//cerr<<a[i]<<'\n';
if(i == 0){
ans=fw.get(idx)+1;
}
fw.update(idx,fw.get(idx)+1);
}
cout<<n+1-ans<<'\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
if(fopen("task.inp", "r")) {
freopen("task.inp", "r", stdin);
//freopen("orzdevinwang.out", "w", stdout);
}
int tt=1;
//cin>>tt;
while(tt--){
solve();
}
}
Compilation message (stderr)
# | 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... |