제출 #1324073

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1324073		sh_qaxxorov_571	Rabbit Carrot (LMIO19_triusis)	C++20	100 / 100	20 ms	5076 KiB

triusis

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * LIOI 2019 - Trusis (Quyon)
 * Vaqt murakkabligi: O(N log N)
 */
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    long long M;
    if (!(cin >> N >> M)) return 0;

    vector<long long> b;
    for (int i = 1; i <= N; i++) {
        long long a_i;
        cin >> a_i;
        
        // Quyon i-chi ustunga chiqa olishi uchun a_i <= i * M bo'lishi shart
        if (a_i <= i * M) {
            // b_i = i * M - a_i shartini o'zgartirmasdan saqlash mumkin bo'lganlar uchun qo'llaymiz
            b.push_back(i * M - a_i);
        }
    }

    // b massivida eng uzun kamaymaydigan qism ketma-ketlikni (LIS) topamiz
    // Buning uchun O(N log N) algoritmidan foydalanamiz
    vector<long long> lis;
    for (long long x : b) {
        auto it = upper_bound(lis.begin(), lis.end(), x);
        if (it == lis.end()) {
            lis.push_back(x);
        } else {
            *it = x;
        }
    }

    // O'zgartirilishi kerak bo'lgan ustunlar soni = Jami - Saqlab qolinganlar
    cout << N - (int)lis.size() << endl;

    return 0;
}

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