Submission #55159358

---

Source Code Expand

// https://codeforces.com/blog/entry/96344
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>

using namespace std;

const int MOD = 998244353;

#define ATCODER_LIB 1
#ifdef ATCODER_LIB
#include <atcoder/segtree>
#include <atcoder/lazysegtree>
#include <atcoder/dsu>
#include <atcoder/math>
#include <atcoder/modint>
#include <atcoder/fenwicktree>

#define ATCODER_MODINT 1
#ifdef ATCODER_MODINT
using mint = atcoder::static_modint<MOD>;
ostream &operator<<(ostream &os, const mint &mi) { return os << mi.val(); }
#endif

using namespace atcoder;
#endif

#ifndef ONLINE_JUDGE
struct terminal_colors { terminal_colors() { system("color"); } } terminal_colors_;
#endif

struct fast_ios { fast_ios(){ cin.tie(nullptr), ios::sync_with_stdio(false), cout << fixed << setprecision(20); } } fast_ios_;

struct check_cin {
    check_cin() {
        atexit([]() {
            assert("error reading input" && !cin.fail() && !cin.bad() && !cin.eof());
#ifdef DEBUG
            string s;
            getline(cin, s, char(EOF));
            for (char& c : s) {
                assert("reading input unfinished" && isspace(c));
            }
#endif
        });
    };
} check_cin_;

using lint = long long;
using pint = std::pair<int,int>;
using plint = std::pair<long long, long long>;

#define mp make_pair
#define fi first
#define se second
#define si(x) int(x.size())
#define all(x) (x).begin(), (x).end()
#define ffor(i, begin, end) for(int i=(begin),i##_end_=(end);i<i##_end_;i++)
#define ifor(i, begin, end) for(int i=(end)-1,i##_begin_=(begin);i>=i##_begin_;i--)
#define rep(i, n) ffor(i,0,n)
#define irep(i, n) ifor(i,0,n)
#define bit(mask,i)((((mask)>>(i))&1) == 1)

template <typename T> bool chmax(T &m, const T q) { return m < q ? (m = q, true) : false; }
template <typename T> bool chmin(T &m, const T q) { return m > q ? (m = q, true) : false; }

const int INF=(1<<30)-1;
const long long LINF=(1ll<<62)-1;
const vector<int> dh={0,1,0,-1},dw={1,0,-1,0};

inline void mod_add(int& val, int addend, int M) {
    val = (int)(((int64_t)val+addend)%M);
    val = (val + M) % M;
}

inline int ceil_pow2(long long n) {
    int x = 0;
    while ((1ull << x) < (unsigned long long)(n)) x++;
    return x;
}

template <class T> std::vector<T> sort_unique(std::vector<T> vec) { sort(vec.begin(), vec.end()), vec.erase(unique(vec.begin(), vec.end()), vec.end()); return vec; }

template <class T1, class T2> std::pair<T1, T2> operator+(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first + r.first, l.second + r.second); }
template <class T1, class T2> std::pair<T1, T2> operator-(const std::pair<T1, T2> &l, const std::pair<T1, T2> &r) { return std::make_pair(l.first - r.first, l.second - r.second); }

template <class IStream, class T1, class T2> IStream &operator>>(IStream &is, std::pair<T1, T2> &p) { is >> p.first; is >> p.second; return is; }
template <class IStream, class T> IStream &operator>>(IStream &is, std::vector<T> &vec) { for (auto &v : vec) is >> v; return is; }
/************************FOR DEBUG OUTPUT**************************/
template <class OStream, class T1, class T2>
OStream &operator<<(OStream &os, const pair<T1, T2> &p) { return os << '(' << p.first << ", " << p.second << ')'; }

template <class OStream, class T1, class T2, class T3, class T4>
OStream &operator<<(OStream &os, const tuple<T1, T2, T3, T4> &t) { return os << '[' << get<0>(t) << ", " << get<1>(t) << ", " << get<2>(t) << ", " << get<3>(t) << ']'; }

template <class OStream, class T, class = decay_t<decltype(*begin(declval<T>()))>, class = enable_if_t<!is_same<T, string>::value>>
OStream &operator<<(OStream &os, const T &c) {
    os << '[';
    for (auto it = c.begin(); it != c.end(); ++it)
      os << &", "[2 * (it == c.begin())] << *it;
    return os << ']';
}

template <class OStream, class T>
OStream &operator<<(OStream &os, queue<T> q) {
    vector<T> v;
    while (!q.empty()) {
        v.push_back(q.front());
        q.pop();
    }
    return os << v;
}

template <class OStream, class T>
OStream &operator<<(OStream &os, stack<T> s) {
    vector<T> v;
    while (!s.empty()) {
        v.push_back(s.top());
        s.pop();
    }
    reverse(v.begin(),v.end());
    return os << v;
}

template <class T, class Container, class Comparator>
ostream &operator<<(ostream &os, priority_queue<T, Container, Comparator> q) {
    vector<T> v;
    while (!q.empty()) {
        v.push_back(q.top());
        q.pop();
    }
    return os << v;
}

//support up to 6 args
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, _7, N, ...) N
#define _FE_0(_CALL, ...)
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define _FE_6(_CALL, x, ...) _CALL(x) _FE_5(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
    _NTH_ARG(dummy, ##__VA_ARGS__, _FE_6, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0)     \
    (MACRO, ##__VA_ARGS__)

const string COLOR_RESET = "\033[0m", BRIGHT_GREEN = "\033[1;32m", BRIGHT_RED = "\033[1;31m", BRIGHT_CYAN = "\033[1;36m", NORMAL_CROSSED = "\033[0;9;37m", RED_BACKGROUND = "\033[1;41m", NORMAL_FAINT = "\033[0;2m";

//Change output format here
#define meta __func__ << ":" << __LINE__ << ": "
#define out(x) "" << BRIGHT_CYAN << #x << COLOR_RESET << " = " << x << ", "

#ifdef DEBUG
#define dbg(...)                                                              \
    cerr << meta << FOR_EACH_MACRO(out, __VA_ARGS__) << "\n"
#define dbgif(cond, ...) ((cond) ? cerr << meta << FOR_EACH_MACRO(out, __VA_ARGS__) << "\n" : cerr)
#define dbgseg(seg, n) { auto& seg_global{seg}; vector<decltype(seg.all_prod())> seg; for(auto i{0}; i<n; i++) seg.push_back(seg_global.get(i)); dbg(seg); }
#else
#define dbg(x...)
#define dbgif(cond, x...)
#define dbgseg(seg, n)
#endif

template <typename T> vector<vector<T>> vec2(int n,int m,const T t=T()) {
    return vector<vector<T>>(n,vector<T>(m, t));
}

template <typename T> vector<vector<vector<T>>> vec3(int n,int m,int l,const T t=T()) {
    return vector<vector<vector<T>>>(n,vec2<T>(m,l,t));
}

template <typename T> vector<vector<vector<vector<T>>>> vec4(int n,int m,int l,int l2,const T t=T()) {
    return vector<vector<vector<vector<T>>>>(n,vec3<T>(m,l,l2,t));
}

template <typename Iter>
inline void write_range(Iter start, Iter end, string delim=" ") {
    if (start != end) cout << *start;
    auto cur{++start};
    while (cur != end) {
        cout << delim << *cur++;
    }
    cout << endl;
}

int op(int a,int b){return max(a,b);}
int e(){return 0;}
bool f(int x){return (x>0);}


int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    cin >> a;
    if (n == 1) {
        cout << 1 << endl;
        exit(0);
    }

    vector<int> prev(n,-1);

    auto lis = [&](const vector<int>& a) {
        int n{int(a.size())};
        vector<int> by_len{{-INF}};
        vector<int> len(n);
        map<int, int> val_to_index;
        val_to_index[-INF] = -1;
        for (int i{0}; i < int(a.size()); i++) {
            if (a[i] > by_len.back()) {
                prev[i] = val_to_index[by_len.back()];
                by_len.push_back(a[i]);
                len[i] = int(by_len.size()) - 1;
            } else {
                auto index{int(lower_bound(by_len.begin(), by_len.end(), a[i]) - by_len.begin())};
                by_len[index] = a[i];
                len[i] = index;
                prev[i] = val_to_index[by_len[index-1]];
            }
            val_to_index[a[i]] = i;
        }
        return len;
    };

    int ans{0};
    {
        auto tmp{a[0]};
        a[0] = 0;
        auto len{lis(a)};
        chmax(ans, *max_element(all(len)));
        a[0] = tmp;
    }
    {
        auto tmp{a.back()};
        a.back() = 1'000'000'001;
        auto len{lis(a)};
        chmax(ans, *max_element(all(len)));
        a.back() = tmp;
    }


    set<int> b_set;
    rep(i,n) {
        b_set.insert(a[i]);
        b_set.insert(a[i]+1);
    }

    vector<int> b{all(b_set)};

    auto compress = [&](auto val) {
        return int(upper_bound(all(b), val) - b.begin());
    };

    dbg(b);

    segtree<int, op, e> seg0(si(b)+2);
    segtree<int, op, e> seg1(si(b)+2);

    vector<pint> pending;
    rep(i,n) {
        if (i >= 2) {
            seg1.set(pending[i-2].fi, pending[i-2].se);
        }
        auto prv_index{compress(a[i]-1)};
        auto index{compress(a[i])};
        auto lt0{seg0.prod(0, prv_index+1)};
        auto lt1{seg1.prod(0, prv_index+1)};
        dbg(lt0,lt1,i,a[i]);

        auto nxt_index{compress(a[i]+1)};
        seg0.set(index, lt0+1);
        seg1.set(index, lt1+1);
        auto eq0{seg0.get(index)};
        pending.push_back(mp(nxt_index, eq0+1));
        dbgseg(seg0, n);
        dbgseg(seg1, n);
        dbg(seg0.all_prod());
        dbg(seg1.all_prod());
    }

    dbg(seg0.all_prod());
    dbg(seg1.all_prod());

    ans = max({ans, seg0.all_prod(), seg1.all_prod()});

    cout << ans << endl;
    
    return 0;
}

Submission Info

Judge Result