Submission #1321034

#	Time	Username	Problem	Language	Result	Execution time	Memory
1321034		husseinjuanda	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	129 ms	9940 KiB

triusis

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

vector<int> id;
vector<int> t;

void update(int i, int l, int r, int i1, int v1){
    if(l == r){
        t[i] = min(t[i], v1);
        return;
    }
    int mid = (l+r)/2;
    if(i1 <= mid){
        update(i*2, l, mid, i1, v1);
    }else{
        update(i*2+1, mid+1, r, i1, v1);
    }
    t[i] = min(t[i*2], t[i*2+1]);
}

int query(int i, int l, int r, int l1, int r1){
    if(l1 > r || l > r1) return 1e18;
    if(l1 <= l && r1 >= r){
        return t[i];
    }
    int mid = (l+r)/2;
    return min(query(i*2, l, mid, l1, r1), query(i*2+1, mid+1, r, l1, r1));
}

int get_id(int k){
    auto it = lower_bound(id.begin(), id.end(), k);
    return it-id.begin();
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> x(n);
    for(int i = 0; i < n; i++){
        cin >> x[i];
        id.push_back(x[i] + (n-i-1) * m);
    }
    id.push_back(n * m);
    sort(id.begin(), id.end());
    t.resize(id.size()*4, 1e18);
    update(1, 0, id.size()-1, get_id(n*m), 0);
    int add = 0;
    for(int i = 0; i < n; i++){
        add++;
        auto it = lower_bound(id.begin(), id.end(), x[i] + (n-i-1) * m);
        int j = it - id.begin();
        int mn = query(1, 0, id.size()-1, j, id.size()-1);
        update(1, 0, id.size()-1, get_id(x[i] + (n-i-1) * m), mn-1);
    }
    cout << t[1]+add << "\n";
    return 0;
}

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