結果

問題 No.3129 Multiple of Twin Subarray
コンテスト
ユーザー nasutarou1341
提出日時 2025-04-25 22:24:58
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 555 ms / 2,000 ms
コード長 4,054 bytes
コンパイル時間 413 ms
コンパイル使用メモリ 82,732 KB
実行使用メモリ 116,400 KB
最終ジャッジ日時 2025-04-25 22:25:17
合計ジャッジ時間 17,324 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

class segtree:
  #セグメント木
  def __init__(s, v, op, e):
    s._n = len(v)
    s.log = s.ceil_pow2(s._n)
    s.size = 1 << s.log
    s.d = [e()] * (2 * s.size)
    s.e = e
    s.op = op
    for i in range(s._n): s.d[s.size + i] = v[i]
    for i in range(s.size - 1, 0, -1): s.update(i)
  
  # 1点更新
  def set(s, p, x):
    p += s.size
    s.d[p] = x
    for i in range(1, s.log + 1): s.update(p >> i)
 
  # 1点取得
  def get(s, p):
    return s.d[p + s.size]
 
  # 区間演算
  def prod(s, l, r):
    sml, smr = s.e(), s.e()
    l += s.size
    r += s.size
    while (l < r):
      if l & 1: 
        sml = s.op(sml, s.d[l])
        l += 1
      if r & 1:
        r -= 1
        smr = s.op(s.d[r], smr)
      l >>= 1
      r >>= 1
    return s.op(sml, smr)
 
  # 全体演算
  def all_prod(s): return s.d[1]
 
  # L固定時の最長区間のR
  def max_right(s, l, g):
    if l == s._n: return s._n
    l += s.size
    sm = s.e()
    while True:
      while (l % 2 == 0): l >>= 1
      if not g(s.op(sm, s.d[l])):
        while l < s.size:
          l = 2 * l
          if g(s.op(sm, s.d[l])):
            sm = s.op(sm, s.d[l])
            l += 1
        return l - s.size
      sm = s.op(sm, s.d[l])
      l += 1
      if (l & -l) == l: break
    return s._n
 
  # R固定時の最長区間のL
  def min_left(s, r, g):
    if r == 0: return 0
    r += s.size
    sm = s.e()
    while True:
      r -= 1
      while r > 1 and (r % 2): r >>= 1
      if not g(s.op(s.d[r], sm)):
        while r < s.size:
          r = 2 * r + 1
          if g(s.op(s.d[r], sm)):
            sm = s.op(s.d[r], sm)
            r -= 1
        return r + 1 - s.size
      sm = s.op(s.d[r], sm)
      if (r & - r) == r: break
    return 0
 
  def update(s, k): s.d[k] = s.op(s.d[2 * k], s.d[2 * k + 1])
  def ceil_pow2(s, n):
    x = 0
    while (1 << x) < n: x += 1
    return x
  def print(s): #デバッグ用
    ans = []
    for i in range(s._n):
      ans.append(s.get(i))
    print(*ans)
  
class segtreeFactory:
  MAX_INT = 10 ** 18
  MOD = 998244353
  # サイズNのmaxSegTree
  @staticmethod
  def makeMaxSegTree(N,  v = None):
    if v == None: v = [0] * N
    return segtree(v, segtreeFactory.opmax, segtreeFactory.emax)
  # サイズNのminSegTree
  @staticmethod
  def makeMinSegTree(N, v = None):
    if v == None: v = [segtreeFactory.MAX_INT] * N
    return segtree(v, segtreeFactory.opmin, segtreeFactory.emin)
  # サイズNのsumSegTree
  @staticmethod
  def makeSumSegTree(N, v = None):
    if v == None: v = [0] * N
    return segtree(v, segtreeFactory.opsum, segtreeFactory.emax)
  # サイズNのfuncSegTree (一次関数の結合)
  @staticmethod
  def makeFuncSegTree(N, v = None):
    if v == None: v = [[1, 0] for _ in range(N)]
    return segtree(v, segtreeFactory.opfunc, segtreeFactory.efunc)
  @staticmethod
  def emax(): return 0
  @staticmethod
  def opmax(s, t): return max(s, t)
  @staticmethod
  def emin(): return segtreeFactory.MAX_INT
  @staticmethod
  def opmin(s, t): return min(s, t)
  @staticmethod
  def opsum(s, t): return s + t
  @staticmethod
  def efunc(): return [1, 0]
  @staticmethod
  def opfunc(s, t): return [s[0] * t[0] % segtreeFactory.MOD, (t[0] * s[1] + t[1]) % segtreeFactory.MOD] # 左を内側にして結合

N = int(input())
A = list(map(int, input().split()))

def nasu(A):
  v = [0] * (N)
  v[0] = A[0]
  for i in range(1, N):
    v[i] = A[i] + v[i - 1]
  segLmin = segtreeFactory.makeMinSegTree(N, v)
  segLmax = segtreeFactory.makeMaxSegTree(N, v) 
  Lmin = [0] * N
  Lmax = [0] * N
  Lmin[0] = A[0]
  Lmax[0] = A[0]
  for i in range(1, N):
    lmin = v[i] - segLmax.prod(0, i)
    lmin = min(v[i], lmin)
    lmax = v[i] - segLmin.prod(0, i)
    lmax = max(v[i], lmax)
    Lmin[i] = min(Lmin[i - 1], lmin)
    Lmax[i] = max(Lmax[i - 1], lmax)
  return Lmin, Lmax

ans = A[0] * A[1]

Lmin, Lmax = nasu(A)
A = A[::-1]
Rmin, Rmax = nasu(A)
Rmin = Rmin[::-1]
Rmax = Rmax[::-1]

for i in range(N - 1):
  ans = max(ans, Lmin[i] * Rmin[i + 1])
  ans = max(ans, Lmax[i] * Rmax[i + 1])
print(ans)
0