結果

問題 No.3129 Multiple of Twin Subarray
ユーザー 三価スニウム
提出日時 2025-06-25 03:00:32
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 2,650 bytes
コンパイル時間 583 ms
コンパイル使用メモリ 82,580 KB
実行使用メモリ 114,312 KB
最終ジャッジ日時 2025-06-25 03:00:48
合計ジャッジ時間 13,984 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 31 WA * 15
権限があれば一括ダウンロードができます

ソースコード

diff # 

class SegTree:
    def __init__(self, op, e, n: int, v=None):
        self.n = n
        self.e = e
        self._op = op
        self.depth = (n-1).bit_length()
        self.size = 1 << self.depth
        self._data = [self.e()] * (self.size<<1)
        if v:
            for i in range(self.n):
                self._data[i+self.size] = v[i]
            for i in range(self.size-1, 0, -1):
                self._data[i] = self._op(self._data[i<<1], self._data[i<<1|1])

    def __str__(self):
        return str(self._data[self.size:])

    def __iter__(self):
        return iter(self._data[self.size:])
    
    def __setitem__(self, i: int, value):
        i += self.size
        self._data[i] = value
        while i:
            self._data[i>>1] = self._op(self._data[i], self._data[i^1])
            i >>= 1
    
    def __getitem__(self, key: int|slice):
        if isinstance(key, slice):
            return [self._data[i+self.size] for i in key]
        return self._data[key+self.size]
    
    def prod(self, start: int, end: int):
        '''product of segtree[start:end]'''
        prodl, prodr = self.e(), self.e()
        l = start + self.size
        r = end + self.size
        while l < r:
            if l & 1:
                prodl = self._op(prodl, self._data[l])
                l += 1
            if r & 1:
                r -= 1
                prodr = self._op(prodr, self._data[r])
            l >>= 1
            r >>= 1
        return self._op(prodl, prodr)
    
    def allprod(self):
        return self._data[1]

N = int(input())
A = list(map(int, input().split()))
segtree = SegTree(lambda x, y: x+y, lambda: 0, N, A)

lmax = [(0, 0)] * N
lmin = [(0, 0)] * N
lmax[0] = lmin[0] = 0, A[0]
for i in range(1, N-1):
    if A[i] > 0:
        s = lmax[i-1][0], segtree.prod(lmax[i-1][0], i+1)
        lmax[i] = max(s, (i, A[i]), key=lambda x: x[1])
        lmin[i] = lmin[i-1]
    elif A[i] < 0:
        s = lmin[i-1][0], segtree.prod(lmin[i-1][0], i+1)
        lmin[i] = min(s, (i, A[i]), key=lambda x: x[1])
        lmax[i] = lmax[i-1]

rmax = [(0, 0)] * N
rmin = [(0, 0)] * N
rmax[N-1] = rmin[N-1] = N-1, A[N-1]
for i in range(N-2, 0, -1):
    if A[i] > 0:
        s = rmax[i+1][0], segtree.prod(i, rmax[i+1][0]+1)
        rmax[i] = max(s, (i, A[i]), key=lambda x: x[1])
        rmin[i] = rmin[i+1]
    elif A[i] < 0:
        s = rmin[i+1][0], segtree.prod(i, rmin[i+1][0]+1)
        rmin[i] = min(s, (i, A[i]), key=lambda x: x[1])
        rmax[i] = rmax[i+1]

ans = max(lmax[0][1]*rmax[1][1], lmin[0][1]*rmin[1][1])
for i in range(1, N-1):
    ans = max(ans, lmax[i][1]*rmax[i+1][1], lmin[i][1]*rmin[i+1][1])
print(ans)
0