結果
| 問題 | No.3812 Max Min Sigma Problem |
| コンテスト | |
| ユーザー |
sepa38
|
| 提出日時 | 2026-11-18 15:42:01 |
| 言語 | PyPy3 (8.0.1 + ACL) |
| 結果 |
WA
不安定
|
| 実行時間 | - |
| コード長 | 1,869 bytes |
| 記録 | |
| コンパイル時間 | 78 ms |
| コンパイル使用メモリ | 63,720 KB |
| 実行使用メモリ | 154,744 KB |
| 最終ジャッジ日時 | 2026-11-20 20:55:54 |
| 合計ジャッジ時間 | 7,931 ms |
|
ジャッジサーバーID (参考情報) |
judge4_0 / judge2_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 10 WA * 18 |
ソースコード
# 誤解法4: min 側の更新で D に足す量の符号を間違える(a - v)
# 区間 add d で ΣD^2 += 2dΣD + d^2·len 。O(N log N)
import sys
MOD = 998244353
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] = (s2[k] + 2*x*s1[k] + x*x % MOD * ln[k]) % MOD
s1[k] = (s1[k] + x*ln[k]) % MOD
if k < size: lz[k] = (lz[k] + x) % MOD
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] = (s1[2*k] + s1[2*k+1]) % MOD
s2[k] = (s2[2*k] + s2[2*k+1]) % MOD
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, a - v); end = s-1; st = s
smin.append((a, st))
ans = (ans + s2[1]) % MOD
print(ans)
main()
sepa38