Submission #857176

#TimeUsernameProblemLanguageResultExecution timeMemory
857176smirichtoRabbit Carrot (LMIO19_triusis)C++17
0 / 100
0 ms500 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; #define pb push_back #define pi pair<ll,ll> #define F first #define S second #define all(x) (x).begin(), (x).end() #define alll(x) ((x).begin()+1), (x).end() #define clean(v) (v).resize(distance((v).begin(), unique(all(v)))); #define yes cout<<"Yes"<<endl; #define no cout<<"No"<<endl; #define mod mod #define endl '\n' mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll mod = 998244353; void io() { ios::sync_with_stdio(false); cin.tie(NULL); } template<class T> bool ckmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; } template<class T> bool ckmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; } void nop() { cout << -1 << endl; return; } template<class T> struct Seg { // comb(ID,b) = b const T ID = 0; T comb(T a, T b) { return max(a , b); } ll n; vector<T> seg; void init(ll _n) { n = _n; seg.assign(2*n,ID); } void pull(ll p) { seg[p] = comb(seg[2*p],seg[2*p+1]); } void upd(ll p, T val) { // set val at position p seg[p += n] = val; for (p /= 2; p; p /= 2) pull(p); } T query(ll l, ll r) { // sum on llerval [l, r] T ra = ID, rb = ID; for (l += n, r += n+1; l < r; l /= 2, r /= 2) { if (l&1) ra = comb(ra,seg[l++]); if (r&1) rb = comb(seg[--r],rb); } return comb(ra,rb); } }; vector<ll> v ; ll get(ll x){return lower_bound(all(v) , x) - v.begin() + 1; } void solve() { ll n , m ; cin>>n>>m ; vector<ll> a(n+1) , dp(n+1) ; for(ll i = 1 ; i<=n ; i++){ cin>>a[i] ; a[i] = i*m - a[i] ; v.pb(a[i]) ; } sort(all(v)) ; Seg<ll> st ; st.init(n+5) ; for(ll i = 1 ; i<=n ; i++){ if(a[i] < 0) continue; ll idx = get(a[i]) ; dp[i] = max(dp[i-1] , st.query(1 , idx) + 1) ; st.upd(idx , dp[i]) ; } cout<<n - dp[n]<<endl; } int main() { io(); ll tt = 1; //cin>>tt ; while (tt--) { solve(); } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...