Submission #1229589

#TimeUsernameProblemLanguageResultExecution timeMemory
1229589free_de_la_zenithRabbit Carrot (LMIO19_triusis)C++20
100 / 100
57 ms9916 KiB
/** * author: MINHTPC * **/ #include <bits/stdc++.h> #define ll long long #define fi first #define se second #define pb push_back #define all(a) a.begin() , a.end() #define FOR(i ,a , b) for(int i = a ; i <= b ; ++i) #define bit(mask,i) ((mask>>i)&1) #define name "task" #define lo lower_bound #define up upper_bound #define count_bit1(x) __builtin_popcountll(x) #define count_bit01(x) __builtin_clzll(x) #define count_bit10(x) __builtin_ctzll(x) using namespace std; const int N=2e5+5; long long a[N],n,k; namespace sub_full { long long t[N],b[N],dp[N],g[N],m; void update(int x,ll v) { for(;x<=m;x+=x&-x) t[x]=max(t[x],v); } long long get(int x) { ll res=0; for(;x;x-=x&-x) res=max(res,t[x]); return res; } void solve() { vector<ll>v; for(int i=1;i<=n;i++) { cin >> a[i]; b[i]=a[i]-1LL*k*i; g[i]=b[i]; v.push_back(b[i]); } sort(v.begin(),v.end(),greater<ll>()); v.erase(unique(all(v)),v.end()); m=v.size(); for(int i=1;i<=n;i++) g[i]=lower_bound(v.begin(),v.end(),b[i],greater<ll>())-v.begin()+1; ll ans=0; for(int i=1;i<=n;i++) { if(b[i]<=0) dp[i]=1; ll cur=get(g[i]); if(cur) dp[i]=max(dp[i],cur+1); ans=max(ans,dp[i]); update(g[i],dp[i]); } cout << n-ans; } } int main() { ios_base::sync_with_stdio(false); cin.tie(0);cout.tie(0); cin >> n >> k; // if(n<=20) sub1::solve(); // else sub23::solve(); sub_full::solve(); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...