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; }