Submission #1164781

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164781		Sir_Ahmed_Imran	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	123 ms	10400 KiB

triusis

            //    01001100 01001111 01010100 01000001    \\
            //                                           \\
            //                ╦  ╔═╗╔╦╗╔═╗               \\
            //                ║  ║ ║ ║ ╠═╣               \\
            //                ╩═╝╚═╝ ╩ ╩ ╩               \\
            //                                           \\
            //    01001100 01001111 01010100 01000001    \\

#include <bits/stdc++.h>
using namespace std;
#define N 200001
#define nl '\n'
#define ff first
#define ss second
#define add insert
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define L0TA ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

ll a[N];
int n, dp[N], idx[N], seg[N << 2];

void built(int v = 1, int s = 0, int e = n){
    if(e - s == 1){
        seg[v] = dp[s];
        return;
    }
    int mid, rc, lc;
    mid = (s + e) / 2;
    rc = 2 * v + 1;
    lc = 2 * v;
    built(lc, s, mid);
    built(rc, mid, e);
    seg[v] = max(seg[lc], seg[rc]);
}

void update(int p, int v = 1, int s = 0, int e = n){
    if(e - s == 1){
        seg[v] = dp[s];
        return;
    }
    int mid, rc, lc;
    mid = (s + e) / 2;
    rc = 2 * v + 1;
    lc = 2 * v;
    if(p < mid) update(p, lc, s, mid);
    else update(p, rc, mid, e);
    seg[v] = max(seg[lc], seg[rc]);
}

int get(int l, int r, int v = 1, int s = 0, int e = n){
    if(r <= s || e <= l || l >= r) return -N;
    if(l <= s && e <= r) return seg[v];
    int mid, rc, lc;
    mid = (s + e) / 2;
    rc = 2 * v + 1;
    lc = 2 * v;
    return max(get(l, r, lc, s, mid), get(l, r, rc, mid, e));
}

void solve(){
    int ans, p;
    ll m;
    cin >> n >> m;
    ans = n;
    n++;
    for(int i = 1; i < n; i++)
        cin >> a[i];
    vector<pll> v; 
    vector<ll> u;
    for(ll i = 0; i < n; i++){
        u.append(a[i] - i * m);
        v.append({u[i], i});
        dp[i] = -N;
    }
    sort(all(u));
    sort(all(v));
    for(int i = 0; i < n; i++){
        idx[v[i].ss] = i;
        //cout << v[i].ss << ' ' << v[i].ff << nl;
    }
    dp[idx[0]] = 0;
    built();
    for(ll i = 1; i < n; i++){
        p = lower_bound(all(u), a[i] - i * m) - u.begin();
        dp[idx[i]] = get(p, n) + 1;
        //cout << get(p, n) << nl;
        ans = min(ans, n - dp[idx[i]] - 1);
        update(idx[i]);
    }
    cout << ans;
}

int terminator(){
    L0TA;
    solve();
    return 0;
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37