#50143 (C++11) No.284 門松と魔法(2)

• 問題: No.284 門松と魔法(2)
• ユーザー: Mi_Sawa
• 提出日時: 2015-09-19 15:17:07
• 言語: C++11 (gcc 11.4.0)
• 結果: AC
• 実行時間: 1,450 ms / 5,000 ms
• コード長: 5,523 bytes
• コンパイル時間: 2,158 ms
• コンパイル使用メモリ: 173,236 KB
• 実行使用メモリ: 135,020 KB
• 最終ジャッジ日時: 2023-09-26 13:38:07
• 合計ジャッジ時間: 11,213 ms
• ジャッジサーバーID （参考情報）: judge12 / judge13

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 4,376 KB
testcase_01	AC	2 ms; 4,380 KB
testcase_02	AC	1 ms; 4,380 KB
testcase_03	AC	2 ms; 4,384 KB
testcase_04	AC	1 ms; 4,376 KB
testcase_05	AC	2 ms; 4,380 KB
testcase_06	AC	2 ms; 4,384 KB
testcase_07	AC	2 ms; 4,380 KB
testcase_08	AC	2 ms; 4,380 KB
testcase_09	AC	1 ms; 4,384 KB
testcase_10	AC	5 ms; 5,256 KB
testcase_11	AC	4 ms; 5,104 KB
testcase_12	AC	5 ms; 5,164 KB
testcase_13	AC	3 ms; 5,104 KB
testcase_14	AC	4 ms; 5,096 KB
testcase_15	AC	4 ms; 5,084 KB
testcase_16	AC	4 ms; 5,232 KB
testcase_17	AC	3 ms; 5,256 KB
testcase_18	AC	4 ms; 5,096 KB
testcase_19	AC	4 ms; 5,152 KB
testcase_20	AC	59 ms; 134,664 KB
testcase_21	AC	61 ms; 134,804 KB
testcase_22	AC	61 ms; 134,692 KB
testcase_23	AC	141 ms; 134,788 KB
testcase_24	AC	1,190 ms; 135,020 KB
testcase_25	AC	490 ms; 134,808 KB
testcase_26	AC	2 ms; 4,380 KB
testcase_27	AC	2 ms; 4,380 KB
testcase_28	AC	1 ms; 4,380 KB
testcase_29	AC	1,450 ms; 134,944 KB
testcase_30	AC	983 ms; 134,932 KB
testcase_31	AC	70 ms; 4,376 KB
testcase_32	AC	1,434 ms; 134,980 KB
testcase_33	AC	456 ms; 19,876 KB
testcase_34	AC	442 ms; 134,912 KB
testcase_35	AC	2 ms; 4,384 KB
testcase_36	AC	2 ms; 4,376 KB
testcase_37	AC	82 ms; 4,376 KB
testcase_38	AC	56 ms; 4,380 KB
testcase_39	AC	2 ms; 4,380 KB

ソースコード

#include <bits/stdc++.h>
#define all(x) begin(x),end(x)
#define rall(x) (x).rbegin(),(x).rend()
#define REP(i,b,n) for(int i=(int)(b);i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define repsz(i,v) rep(i,(v).size())
#define aur auto&
#define bit(n) (1LL<<(n))
#define eb emplace_back
#define mt make_tuple
#define fst first
#define snd second
using namespace std;
typedef long long ll;
//#define int long long
template<class C>int size(const C &c){ return c.size(); }
template<class T>bool chmin(T&a,const T&b){if(a<=b)return false;a=b;return true;}
template<class T>bool chmax(T&a,const T&b){if(a>=b)return false;a=b;return true;}

struct Data{//{{{
    int v1, v2, n1, n2;
    Data() : n1(-1E7), n2(-1E7){}
    Data(const int &v, const int &n) : v1(v), n1(n), n2(-1E7) {}
    void update(const int &v, const int &n){
        if(n2 >= n) return;
        if(v == v1 or v == v2){
            if(v == v1) n1 = max(n1, n);
            if(v == v2) n2 = max(n2, n);
        }else{
            n2 = n;
            v2 = v;
        }
        if(n1 > n2) return;
        swap(n1, n2);
        swap(v1, v2);
    }
    void update(const Data &d){
        update(d.v1, d.n1);
        update(d.v2, d.n2);
    }
    static Data combine(const Data &a, const Data &b){
        Data d = a;
        d.update(b);
        return d;
    }
};//}}}

template<typename Val, typename Lazy>
struct SegTree{//{{{
    const Val zero;
    vector<Val>  values;
    vector<Lazy> lazys;
    vector<bool> has_lazy;
    const int n;
    int offset, N;

    inline Val propagate(const Val &l, const Val &r){
        return Data::combine(l, r);
    }
    inline void apply(Val &val, const Lazy &lazy, const int &l, const int &r){
        val.update(lazy);
    }
    inline void push(Lazy &old, const Lazy &add){
        old.update(add);
    }

    inline void push_down(const int &k, const int &ll, const int &rr){
        if(!has_lazy[k]) return;
        if(k < offset){
            if(has_lazy[k*2 + 1]) push(lazys[k*2 + 1], lazys[k]);
            else                  lazys[k*2 + 1] = lazys[k];
            if(has_lazy[k*2 + 2]) push(lazys[k*2 + 2], lazys[k]);
            else                  lazys[k*2 + 2] = lazys[k];
            has_lazy[k*2 + 1] = has_lazy[k*2 + 2] = true;
        }
        apply(values[k], lazys[k], ll, min(rr, n));
        has_lazy[k] = false;
    }

    explicit SegTree(int n, const Val zero = Val()) : n(n), zero(zero){
        N = 1;
        while(N < n) N <<= 1;
        offset = N-1;
        values.assign(N*2, zero);
        lazys.resize(N*2);
        has_lazy.assign(N*2, false);
    }
    explicit SegTree(const vector<Val> &xs, const Val zero = Val()) : SegTree(xs.size(), zero){
        rep(i, n) values[i + offset] = xs[i];
        build(0, n, 0, 0, N);
    }
    const Val &build(const int &l, const int &r, const int &k, const int &ll, const int &rr){
        if(r <= ll || rr <= l) return zero;
        if(rr - ll == 1) return values[k];
        const int mm = (ll + rr) >> 1;
        if(r <= mm) return values[k] = build(l, r, k*2+1, ll, mm);
        if(l >= mm) return values[k] = build(l, r, k*2+2, mm, rr);
        return values[k] = propagate(build(l, r, k*2+1, ll, mm), build(l, r, k*2+2, mm, rr));
    }
    void update(const int &l, const int &r, const Lazy &v){
        update(l, r, v, 0, 0, N);
    }
    void update(const int &l, const int &r, const Lazy &v,
            const int &k, const int &ll, const int &rr){
        push_down(k, ll, rr);
        if(r <= ll || rr <= l) return;
        if(l <= ll && rr <= r){
            if(has_lazy[k]) push(lazys[k], v);
            else            lazys[k] = v;
            has_lazy[k] = true;
            push_down(k, ll, rr);
            return;
        }
        const int mm = (ll + rr) >> 1;
        update(l, r, v, k*2+1, ll, mm);
        update(l, r, v, k*2+2, mm, rr);
        values[k] = propagate(values[k*2+1], values[k*2+2]);
    }

    Val get(const int &l, const int &r){ return get(l, r, 0, 0, N); }
    Val get(const int &l, const int &r,
            const int &k, const int &ll, const int &rr){
        if(r <= ll || rr <= l) return zero;
        push_down(k, ll, rr);
        if(l <= ll && rr <= r) return values[k];
        const int mm = (ll + rr) >> 1;
        if(r <= mm) return get(l, r, k*2+1, ll, mm);
        if(l >= mm) return get(l, r, k*2+2, mm, rr);
        return propagate(get(l, r, k*2+1, ll, mm), get(l, r, k*2+2, mm, rr));
    }
};//}}}

bool solve(){
    int n; cin >> n;
    vector<int> a(n); for(auto &x : a) cin >> x;
    const int H = *max_element(all(a)) + 10;

    SegTree<Data, Data> u(H), d(H);
    u.update(0, H, Data(-1, 0));
    d.update(0, H, Data(H, 0));

    for(int i = 0; i < n; ++i){
        Data x = u.get(a[i], a[i]+1);
        Data y = d.get(a[i], a[i]+1);

        u.update(a[i]+1, y.v1, Data(a[i], y.n1+1));
        u.update(y.v1+1,    H, Data(a[i], y.n1+1));
        u.update(a[i]+1, y.v2, Data(a[i], y.n2+1));
        u.update(y.v2+1,    H, Data(a[i], y.n2+1));

        d.update(     0, x.v1, Data(a[i], x.n1+1));
        d.update(x.v1+1, a[i], Data(a[i], x.n1+1));
        d.update(     0, x.v2, Data(a[i], x.n2+1));
        d.update(x.v2+1, a[i], Data(a[i], x.n2+1));
    }

    int res = max(u.get(0, H).n1, d.get(0, H).n1);
    if(res < 3) res = 0;
    cout << res << endl;
    return true;
}
signed main(){
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    cout << std::fixed << std::setprecision(10);
    solve();
    return 0;
}
// vim:set foldmethod=marker commentstring=//%s: