Submission #988428

#	Time	Username	Problem	Language	Result	Execution time	Memory
988428		HUYHDUVE	Rabbit Carrot (LMIO19_triusis)	C++14	100 / 100	81 ms	6996 KiB

triusis

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

int main(){
//    freopen("A.IN", "r", stdin);
//    freopen("A.OUT", "w", stdout);
    ll n, m; cin >> n >> m;
    vector<ll> a(n);

    for(auto &it : a) cin >> it;

    vector<ll> b(n);
    int cnt = 0;
    if(a[0] > m) {
        cnt ++;
        a[0] = m;
    }


    for(int i = 0; i < n; i++){
        b[i] = (i + 1)*m - a[i];
    }

    vector<ll> min_e(n, 0);


    int max_l = 0;
    function<int(ll)> bi_s = [&](ll targ) -> int{
        int l = 0, r = max_l, ans = 0;
        while(l <= r){
            int mid = l + (r - l)/2;
            if(min_e[mid] <= targ){
                ans = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }

        return ans;
    };

    for(int i = 0; i < n; i++){
        if(b[i] < 0) continue;
        int j = bi_s(b[i]);

        max_l = max(max_l, j + 1);
        min_e[j + 1] = b[i];
    }

//    for(auto &it : b) cout << it << " ";

    cout << n - max_l + cnt;

    return 0;
}

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