はまやんはまやんはまやん

hamayanhamayan's blog

Multiplication Is Interesting [ACPC2017 Day3 F]

http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=ACPC2017Day3&pid=F

解説

http://judge.u-aizu.ac.jp/onlinejudge/creview.jsp?rid=2540062&cid=ACPC2017Day3

全ての数で対数を取って、積ではなく和で考えるようにする。

右を固定しながら全探索する。
セグメント木をst[R] := [R,L]での総和として更新する。
ここで、[0,L]の中でK以下で最も右の要素を探すために、二分探索を使う。
最も右の要素をokとすると、答えとなりうる(L - ok + 1)の最大値が答え。
誤差に注意。

typedef double ld;
#define INF INT_MAX/2
template<class V, int NV> struct LazySegTree { // [L,R)
    vector<V> dat, lazy; LazySegTree() { dat.resize(NV * 2, def); lazy.resize(NV * 2, ldef); }
    void update(int a, int b, V v, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return;
        if (a <= l && r <= b) { setLazy(k, v); push(k, l, r); } else {
        update(a, b, v, k * 2 + 1, l, (l + r) / 2); update(a, b, v, k * 2 + 2, (l + r) / 2, r);
        dat[k] = comp(dat[k * 2 + 1], dat[k * 2 + 2]);}}
    V get(int a, int b, int k, int l, int r) { push(k, l, r); if (r <= a || b <= l) return INF;
        if (a <= l && r <= b) return dat[k]; auto x = get(a, b, k * 2 + 1, l, (l + r) / 2);
        auto y = get(a, b, k * 2 + 2, (l + r) / 2, r); return comp(x, y);}
    void update(int a, int b, V v) { update(a, b, v, 0, 0, NV); }
    V get(int a, int b) { return get(a, b, 0, 0, NV); }
    // ---- Template ---------------------------------------------------------------------------------
    // 区間add, 区間min
    const V def = 0, ldef = 0;
    V comp(V l, V r) { return min(l, r); }
    void setLazy(int i, V v) { lazy[i] += v; }
    void push(int k, int l, int r) {
        dat[k] += lazy[k];
        if (r - l > 1) { setLazy(k * 2 + 1, lazy[k]); setLazy(k * 2 + 2, lazy[k]); }
        lazy[k] = ldef;
    }
 
    void dump(int L, int R) { // [L,R)
        cout << "[";
        rep(i, L, R) cout << " " << get(i, i + 1);
        cout << "]\n";
    }
};


#define EPS 1e-10
int N; ld K, S[101010];
LazySegTree<ld, 1 << 17> st;
//--------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> K;
    rep(i, 0, N) cin >> S[i];
 
    K = log10(K);
    rep(i, 0, N) S[i] = log10(S[i]);
 
    int ans = 0;
    rep(i, 0, N) {
        st.update(0, i + 1, S[i]);
        int ng = -1, ok = i + 1;
        while (ng + 1 != ok) {
            int x = (ng + ok) / 2;
            if (st.get(0, x + 1) <= K + EPS) ok = x;
            else ng = x;
        }
 
        if(ok != i + 1) ans = max(ans, i - ok + 1);
    }
    cout << ans << endl;
}