結果

問題 No.3530 「」
コンテスト
ユーザー aa36
提出日時 2026-02-28 10:30:57
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
RE  
実行時間 -
コード長 1,766 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 217 ms
コンパイル使用メモリ 85,068 KB
実行使用メモリ 67,964 KB
最終ジャッジ日時 2026-05-04 20:51:46
合計ジャッジ時間 3,941 ms
ジャッジサーバーID
（参考情報） 		judge2_1 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample RE * 2
other RE * 27
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

# うまく翻訳できなかったのでhttps://yukicoder.me/submissions/1149633 を愚直に人力翻訳
# ACLpyのModintの使い方分からなかった(´；ω；｀)
from atcoder.lazysegtree import LazySegTree
import bisect
from sys import stdin
input = stdin.readline

MOD = 998244353
def rev(x):
    return pow(x, MOD - 2, MOD)

def op(a, b) :
    return ((a[0] * (1 - a[1]) + b[0] * (1 - b[1])) % MOD, 0)
e = (1, 1)
def mapping(f, x) :
    return ((x[0] * f) % MOD, x[1])
def composition(f, g) :
    return f * g % MOD
_id = 1
f34 = 3 * rev(4) % MOD
f43 = rev(f34)
N = int(input().rstrip())
X = [0 for i in range(N)]
Y = [0 for i in range(N)]
for i in range(N): X[i], Y[i] = map(int, input().rstrip().split())
zX = sorted(set(X))
zY = sorted(set(Y))
if len(zX) == 1 or len(zY) == 1:
    print(0)
    exit()
rX = [bisect.bisect_left(zX, x) for x in X]
rY = [bisect.bisect_left(zY, y) for y in Y]
ans = 0
for _ in range(2):
    G = [[] for i in range(len(zX))]
    for i in range(N): G[rX[i]].append(rY[i])
    V = [e for i in range(len(zY))]
    for i in range(N):
        if rY[i] + 1 < len(zY):
            V[rY[i] + 1] = (V[rY[i] + 1][0] * f34 % MOD, 1)
    for i in range(1, len(zY)): V[i] = (V[i-1][0] * V[i][0] % MOD, 1)
    seg = LazySegTree(op, e, mapping, composition, _id, V)
    fs = 1
    for i in range(len(zX) - 1):
        for y in G[i]:
            seg.set(y, (seg.get(y)[0], seg.get(y)[1] * f34 % MOD))
            seg.apply(0, y, f34)
            seg.apply(y+1, len(zY), f43)
            fs = fs * f34 % MOD
        all_prd = seg.all_prod()
        ans += (1 - all_prd[0] - fs) * (zX[i + 1] - zX[i]) % MOD
        ans %= MOD
    rX, rY = rY, rX
    zX, zY = zY, zX

for i in range(N):
    ans = ans * 4 % MOD
ans = ans * 2 % MOD
print(ans)
0