提出 #53566773

---

ソースコード 拡げる

#include <bits/stdc++.h>

#include "atcoder/segtree"

using namespace std;

constexpr int inf = 1 << 30; // inf > 10^9

int op(int a, int b) {
    return max(a, b);
}
int e() {
    return -inf;
}

vector<int> calc_lis(vector<int> x) {
    const int n = (int)x.size();
    // 座標圧縮
    vector<int> ps;
    for (const auto e : x) {
        ps.push_back(e);
    }
    sort(ps.begin(), ps.end());
    ps.erase(unique(ps.begin(), ps.end()), ps.end());
    for (auto &e : x) {
        e = lower_bound(ps.begin(), ps.end(), e) - ps.begin();
    }
    
    // 動的計画法
    vector<int> ret(n);
    atcoder::segtree<int, op, e> dp(n);
    // ret[i]: 最後の要素が x[i] である条件下の LIS の長さ
    for (int i = 0; i < n; ++i) {
        const int mx = max(0, dp.prod(0, x[i]));
        ret[i] = mx + 1;
        dp.set(x[i], mx + 1);
    }
    return ret;
}

void solve() {
    // 入力
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto &e : a) {
        cin >> e;
    }

    // l_lis[i]: 最後の要素が a[i] である条件下の LIS の長さ
    // r_lis[i]: 最初の要素が a[i] である条件下の LIS の長さ
    auto l_lis = calc_lis(a);
    reverse(a.begin(), a.end());
    for (auto &e : a) {
        e = inf - e;
    }
    auto r_lis = calc_lis(a);
    reverse(a.begin(), a.end());
    for (auto &e : a) {
        e = inf - e;
    }
    reverse(r_lis.begin(), r_lis.end());

    const int L = *max_element(l_lis.begin(), l_lis.end());
    vector<int> ans;
    for (int i = 0; i < n; ++i) {
        if (l_lis[i] + r_lis[i] - 1 == L) {
            ans.push_back(i);
        }
    }

    // 出力
    const int m = (int)ans.size();
    cout << m << '\n';
    for (int i = 0; i < m; ++i){
        cout << ans[i] + 1 << (i == m - 1 ? '\n' : ' ');
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
}

提出情報

ジャッジ結果