結果

問題 No.284 門松と魔法(2)
コンテスト
ユーザー Mi_Sawa
提出日時 2015-09-19 14:15:25
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 5,358 bytes
コンパイル時間 1,721 ms
コンパイル使用メモリ 171,336 KB
実行使用メモリ 135,296 KB
最終ジャッジ日時 2024-07-19 07:56:27
合計ジャッジ時間 12,982 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 31 WA * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
        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));
    }
};//}}}

constexpr int H = 1E6 + 10;
bool solve(){
    int n; cin >> n;
    vector<int> a(n); for(auto &x : a) cin >> x;

    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:
0