Submission #1187814

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187814		liangjeremy	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	53 ms	18788 KiB

triusis

#include<bits/stdc++.h>
#include<random>
using namespace std;
using db=double;
using ll=long long;
using sll=__int128;//super long long
using lb=long double;//lb is slow
//numbers for hashing: b(19260817),mod(998244353)
//another number for hashing:b(137) only
// freopen("deleg.in", "r", stdin);
// freopen("deleg.out", "w", stdout);

class BinaryIndexedTree{
    private:
        vector<ll>bits;
    public:
        BinaryIndexedTree(ll n){
            bits.resize(n);
        }
        void update(ll index, ll delta){
            while(index<bits.size()){
                bits[index]=max(bits[index],delta);
                index+=index&-index;
            }
        }
        ll query(ll index){
            ll ans=0;
            while(index>0){
                ans=max(ans,bits[index]);
                index-=index&-index;
            }
            return ans;
        }
};

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    ll n,m; cin>>n>>m; vector<ll>a(n);
    for(ll i=0; i<n; i++){
        cin>>a[i];
    }
    vector<ll>v; vector<ll>v2; 
    for(ll i=0; i<n; i++){
        if((i+1)*m-a[i]>=0){
            v.push_back((i+1)*m-a[i]);
            v2.push_back(v.back());
        }
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());
    unordered_map<ll,ll>mp;
    for(ll i=0; i<v.size(); i++){
        mp[v[i]]=i+1;
    }
    vector<ll>cur(v2.size(),0); BinaryIndexedTree BIT(v2.size()+10);
    for(ll i=0; i<v2.size(); i++){
        cur[i]=mp[v2[i]];
    }
    vector<ll>dp(v2.size()+10,0);
    for(ll i=0; i<v2.size(); i++){
        dp[i]=BIT.query(cur[i])+1;
        BIT.update(cur[i],dp[i]);
    }
    cout<<n-*max_element(dp.begin(),dp.end())<<endl;
}

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