Submission #6264485

---

Source Code Expand

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath> // 変数名にy1が使えなくなるかも…。
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <string>

typedef __int128_t int128_t;
std::istream &operator>>(std::istream& input, int128_t& value) { // int128_tの入力。入力が64bitに収まる前提。
    long long tmp; input >> tmp; value = tmp;
    return input;
}
std::ostream &operator<<(std::ostream& output, const int128_t value) { // int128_tの出力。出力が64bitに収まる前提。
    output << (long long)value;
    return output;
}

std::vector<int> LIS(const std::vector<int>& vec) {
    const int INF = std::numeric_limits<int>::max();
    std::vector<int> dp; dp.resize(vec.size(), INF); // 長さがi+1であるような増加部分列における最終要素の最小値（存在しない場合INF)
    std::vector<int> id; id.resize(vec.size()); // i番目の要素を最終要素としたときの、増加部分列の長さ-1。
    for (int i = 0; i < vec.size(); i++) {
        auto itr = std::lower_bound(dp.begin(), dp.end(), vec[i]);
        *itr = vec[i];
        id[i] = std::distance(dp.begin(), itr);
    }
    int m = *std::max_element(id.begin(), id.end());
    std::vector<int> ret; ret.resize(m+1);
    for (int i = vec.size() - 1; 0 <= i; i--) {
        if (id[i] == m) {
            ret[m] = vec[i];
            m--;
        }
    }
    return ret;
}

int N;
std::vector<int> vec;
 
int main(void) {
    std::cin >> N;

    for (int i = 1; i <= N; i++) {
        int c;
        std::cin >> c;
        vec.push_back(c);
    }

    auto ret = LIS(vec);
    std::cout << N - ret.size() << std::endl;

    return 0;
}

Submission Info

Judge Result