提出 #55077176

---

ソースコード 拡げる

#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;
using pl = pair<ll, ll>;
constexpr ll INF = 1e9 + 7;
constexpr ll mod = 1e9 + 7;
constexpr ld eps = 1e-9;
const ld PI = acos(-1);

struct node {
    int mx;
    node *l{nullptr}, *r{nullptr};
};

node *build(int l, int r) {
    if (l + 1 == r) {
        return new node(0);
    }
    int m = (r + l) / 2;
    node *v = new node;
    v->l = build(l, m);
    v->r = build(m, r);
    v->mx = max(v->l->mx, v->r->mx);
    return v;
}

node *upd(node *v, int l, int r, int k, int x) {
    if (l + 1 == r) {
        return new node(x);
    }
    int m = (r + l) / 2;
    node *nd = new node(*v);
    if (k < m) nd->l = upd(v->l, l, m, k, x);
    else nd->r = upd(v->r, m, r, k, x);
    nd->mx = max(nd->l->mx, nd->r->mx);
    return nd;
}

int get(node *v, int l, int r, int lq, int rq) {
    if (l >= rq || lq >= r)return 0;
    if (l >= lq && r <= rq)return v->mx;
    int m = (r + l) / 2;
    return max(get(v->l, l, m, lq, rq), get(v->r, m, r, lq, rq));
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int n;
    cin >> n;
    vector<int> all;
    vector<int> a(n);
    for (auto &i: a) {
        cin >> i;
        all.push_back(i - 1);
        all.push_back(i - 2);
        all.push_back(i);
        all.push_back(i + 1);
        all.push_back(i + 2);
    }
    all.push_back(-INF);
    all.push_back(INF);
    sort(all.begin(), all.end());
    all.resize(unique(all.begin(), all.end()) - all.begin());
    int K = all.size();
    for (auto &i: a) {
        i = lower_bound(all.begin(), all.end(), i) - all.begin();
    }
    vector<node *> t(n + 1);
    t[n] = build(0, K);
    for (int i = n - 1; ~i; --i) {
        int val = get(t[i + 1], 0, K, a[i] + 1, K);
        t[i] = upd(t[i + 1], 0, K, a[i], val + 1);
    }
    int res = 0;
    node *tree = build(0, K);
    pair<int, int> last = {0, 0};
    for (int i = 0; i < n; ++i) {
        int val = get(t[i + 1], 0, K, last.second + 2, K);
        res = max(res, last.first + 1 + val);
        int best = get(tree, 0, K, 0, a[i]);
        tree = upd(tree, 0, K, a[i], best + 1);
        last = {best + 1, a[i]};
    }
    cout << res;
    return 0;
}

提出情報

ジャッジ結果