AtCoderのABC134「Sequence Decomposing」がTLEになってしまう

Question

概要

AtCoderのABC134「Sequence Decomposing」で9/35件がTLEになってしまいます。（その他はACです。）
勉強不足で恐縮なのですが、計算量を減らす方法がわからず、ご教示いただけましたら幸いです。
何卒宜しくお願い致します。

問題

https://atcoder.jp/contests/abc134/submissions/6481452

コード

#include <iostream>
#include <tuple>

std::tuple<int, int> get_smaller_max(int a, int l[], int l_count) {
    int max = -1, index = -1;
    for (size_t i=0; i < l_count; i++) {
        if (l[i] < a && l[i] > max) {
            max = l[i];
            index = i;
        }
    }
    return std::forward_as_tuple(max, index);
}

int main() {
    int n; std::cin >> n;

    int l[n], l_count = 0, max, index;
    for (size_t i = 0; i < n; i++) {
        int a; std::cin >> a;
        std::tie(max, index) = get_smaller_max(a, l, l_count);
        if (max == -1) {
            l[l_count] = a;
            l_count++;
        } else {
            l[index] = a;
        }
    }

    std::cout << l_count << std::endl;
    return 0;
}

Answer 1

get_smaller_max 中で O(l_count) のループを回してますが、ここで二分探索を使って O(log(l_count)) に短縮するのがコツです。
これで全体でみると O(N*N) から O(N log N) に改善して想定解の計算量になります。

以下、変更例です。 vector 使っといたほうが見通し良くなる気はします。

#include <iostream>
#include <tuple>
#include <algorithm>

int get_smaller_max(int a, int l[], int l_count) {
    int* ptr = std::upper_bound(l, l + l_count, a, std::greater<int>());
    int index = ptr - l;
    if (index == l_count) return -1;
    return index;
}

int main() {
    int n; std::cin >> n;

    int l[n], l_count = 0, max, index;
    for (size_t i = 0; i < n; i++) {
        int a; std::cin >> a;
        int index = get_smaller_max(a, l, l_count);
        if (index == -1) {
            l[l_count] = a;
            l_count++;
        } else {
            l[index] = a;
        }
    }

    std::cout << l_count << std::endl;
    return 0;
}

Comments

[yotayokuto]

ありがとうございます！！
色々無駄な記述もありましたね、、
初c++での挑戦だったのですが、次回もっと上手くできるように頑張ります

[set0gut1]

ベストアンサーありがとうございます！自分は競プロはc++なんですが、競プロ以外では一切c++を使う機会がないタイプです。