結果

問題 No.3812 Max Min Sigma Problem
コンテスト
ユーザー sepa38
提出日時 2026-11-18 15:41:27
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,085 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 108 ms
コンパイル使用メモリ 64,480 KB
実行使用メモリ 162,100 KB
最終ジャッジ日時 2026-11-20 20:56:03
合計ジャッジ時間 23,458 ms
ジャッジサーバーID
(参考情報)
judge1_0 / judge5_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 13 WA * 9 TLE * 4 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

# 誤解法3: 途中で mod を取らず long long で計算し、最後に一度だけ mod(int64 オーバーフロー)
# Python では W() で C++ の 64bit 符号付き整数の wrap を再現している
import sys
MOD = 998244353
def W(x):
    return ((x + (1 << 63)) & ((1 << 64) - 1)) - (1 << 63)
def cmod(x):  # C++ の % (0方向切り捨て)
    return x % MOD if x >= 0 else -((-x) % MOD)
def main():
    d = sys.stdin.read().split()
    n = int(d[0]); A = list(map(int, d[1:1+n]))
    size = 1
    while size < n: size *= 2
    s1 = [0]*(2*size); s2 = [0]*(2*size); ln = [0]*(2*size); lz = [0]*size
    for i in range(size): ln[size+i] = 1
    for i in range(size-1, 0, -1): ln[i] = ln[2*i] + ln[2*i+1]
    def ap(k, x):
        s2[k] = W(s2[k] + W(W(2*x)*s1[k]) + W(W(x*x)*ln[k]))
        s1[k] = W(s1[k] + W(x*ln[k]))
        if k < size: lz[k] = W(lz[k] + x)
    def push(k):
        if lz[k]:
            ap(2*k, lz[k]); ap(2*k+1, lz[k]); lz[k] = 0
    def pull(k):
        s1[k] = W(s1[2*k] + s1[2*k+1])
        s2[k] = W(s2[2*k] + s2[2*k+1])
    LOG = size.bit_length() - 1
    def add(l, r, x):  # [l, r)
        if l >= r: return
        l += size; r += size
        for i in range(LOG, 0, -1):
            if ((l >> i) << i) != l: push(l >> i)
            if ((r >> i) << i) != r: push((r-1) >> i)
        l2, r2 = l, r
        while l2 < r2:
            if l2 & 1: ap(l2, x); l2 += 1
            if r2 & 1: r2 -= 1; ap(r2, x)
            l2 >>= 1; r2 >>= 1
        for i in range(1, LOG+1):
            if ((l >> i) << i) != l: pull(l >> i)
            if ((r >> i) << i) != r: pull((r-1) >> i)
    smax = []; smin = []; ans = 0
    for r in range(n):
        a = A[r]
        end = r-1; st = r
        while smax and smax[-1][0] <= a:
            v, s = smax.pop(); add(s, end+1, a - v); end = s-1; st = s
        smax.append((a, st))
        end = r-1; st = r
        while smin and smin[-1][0] >= a:
            v, s = smin.pop(); add(s, end+1, v - a); end = s-1; st = s
        smin.append((a, st))
        ans = W(ans + s2[1])
    print(cmod(ans))
main()
0