結果

問題 No.284 門松と魔法(2)
ユーザー Mi_SawaMi_Sawa
提出日時 2015-09-19 15:17:07
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 1,769 ms / 5,000 ms
コード長 5,523 bytes
コンパイル時間 1,648 ms
コンパイル使用メモリ 173,060 KB
実行使用メモリ 135,208 KB
最終ジャッジ日時 2024-07-19 07:57:13
合計ジャッジ時間 11,030 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
6,816 KB
testcase_01 AC 2 ms
6,940 KB
testcase_02 AC 1 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 1 ms
6,940 KB
testcase_06 AC 2 ms
6,940 KB
testcase_07 AC 2 ms
6,940 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 1 ms
6,940 KB
testcase_10 AC 5 ms
6,944 KB
testcase_11 AC 4 ms
6,940 KB
testcase_12 AC 4 ms
6,940 KB
testcase_13 AC 3 ms
6,944 KB
testcase_14 AC 3 ms
6,940 KB
testcase_15 AC 3 ms
6,944 KB
testcase_16 AC 5 ms
6,940 KB
testcase_17 AC 3 ms
6,940 KB
testcase_18 AC 4 ms
6,940 KB
testcase_19 AC 3 ms
6,944 KB
testcase_20 AC 68 ms
134,696 KB
testcase_21 AC 80 ms
134,656 KB
testcase_22 AC 70 ms
134,796 KB
testcase_23 AC 166 ms
134,736 KB
testcase_24 AC 1,322 ms
135,036 KB
testcase_25 AC 591 ms
134,808 KB
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 2 ms
6,944 KB
testcase_28 AC 1 ms
6,944 KB
testcase_29 AC 1,769 ms
135,204 KB
testcase_30 AC 1,218 ms
135,208 KB
testcase_31 AC 100 ms
6,940 KB
testcase_32 AC 1,703 ms
135,100 KB
testcase_33 AC 636 ms
19,940 KB
testcase_34 AC 605 ms
135,048 KB
testcase_35 AC 2 ms
6,944 KB
testcase_36 AC 1 ms
6,940 KB
testcase_37 AC 118 ms
6,940 KB
testcase_38 AC 76 ms
6,944 KB
testcase_39 AC 3 ms
6,944 KB
権限があれば一括ダウンロードができます

ソースコード

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