제출 #1178986

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1178986		Godgift42	Rabbit Carrot (LMIO19_triusis)	C++20	14 / 100	3 ms	584 KiB

triusis

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

vector<int> st;

void upd(int v, int tl, int tr, int pos, int val){
    if(tl==tr)st[v]=max(val,st[v]);
    else{
        int tm=(tl+tr)/2;
        if(tm>=pos)upd(v*2,tl,tm,pos,val);
        else upd(v*2+1,tm+1,tr,pos,val);
        st[v]=max(st[v*2],st[v*2+1]);
    }
}

int ma(int v, int tl, int tr, int l, int r){
    if(l>r)return 0;
    if(tl==l and tr==r)return st[v];
    int tm=(tl+tr)/2;
    return max(ma(v*2,tl,tm,l,min(r,tm)),ma(v*2+1,tm+1,tr,max(l,tm+1),r));
}

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> a(n);
    vector<int> b(n);
    map<int,int> mp;
    for(int i=0;i<n;i++){
        cin >> a[i];
        b[i]=m*(i+1)-a[i];
        if(b[i]>=0)mp[b[i]]++;
    }
    int cnt=0;
    for(auto& i:mp){
        i.second=cnt;
        cnt++;
    }
    st.resize(4*cnt);
    int ans=0;
    for(int i=0;i<n;i++){
        if(b[i]>=0){
            int x=ma(1,0,n-1,0,mp[b[i]])+1;
            ans=max(ans,x);
            upd(1,0,n-1,mp[b[i]],x);
        }
    }
    cout << n-ans << "\n";
}

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