#1149700 (PyPy3) No.3530 「」

• 問題: No.3530 「」
• ユーザー: aa36
• 提出日時: 2026-02-27 23:31:13
• 言語: PyPy3 (7.3.17)
• 結果: WA
• 実行時間: -
• コード長: 4,454 bytes
• コンパイル時間: 488 ms
• コンパイル使用メモリ: 85,824 KB
• 実行使用メモリ: 150,096 KB
• 最終ジャッジ日時: 2026-05-04 20:52:12
• 合計ジャッジ時間: 22,643 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 1 WA * 1
other	AC * 1 WA * 14 TLE * 1 -- * 11

ソースコード

import sys
from math import ceil, log2

MOD = 998244353

def modinv(x):
    return pow(x, MOD-2, MOD)

# lazy segment tree specialized to the problem
class LazySegTree:
    # op : combine two S = (a,b)
    # mapping : apply factor f to S (only multiplies a)
    # composition : multiply factors
    def __init__(self, init):
        # init: list of pairs (a,b) modulo MOD
        n = len(init)
        if n == 0:
            self.n0 = 1
        else:
            self.n0 = 1 << (n-1).bit_length()
        self.size = n
        self.d = [(1,1)] * (2 * self.n0)
        self.lz = [1] * self.n0  # lazy stored at internal nodes 1..n0-1
        # build leaves
        for i in range(n):
            self.d[self.n0 + i] = init[i]
        for i in range(self.n0 - 1, 0, -1):
            self._update(i)
        self.h = (self.n0).bit_length() - 1

    def _op(self, L, R):
        # L, R are tuples (a,b)
        aL, bL = L
        aR, bR = R
        # (aL * (1 - bL) + aR * (1 - bR), 0)
        t = (aL * ((1 - bL) % MOD) + aR * ((1 - bR) % MOD)) % MOD
        return (t, 0)

    def _mapping(self, f, x):
        a, b = x
        return (a * f % MOD, b)

    def _all_apply(self, k, f):
        self.d[k] = self._mapping(f, self.d[k])
        if k < self.n0:
            self.lz[k] = f * self.lz[k] % MOD

    def _push(self, k):
        f = self.lz[k]
        if f != 1:
            self._all_apply(2*k, f)
            self._all_apply(2*k+1, f)
            self.lz[k] = 1

    def _update(self, k):
        self.d[k] = self._op(self.d[2*k], self.d[2*k+1])

    def apply(self, l, r, f):
        # apply f to range [l, r)
        if l >= r:
            return
        l += self.n0
        r += self.n0
        l0, r0 = l, r
        for i in range(self.h, 0, -1):
            self._push(l >> i)
            self._push((r-1) >> i)
        while l < r:
            if l & 1:
                self._all_apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._all_apply(r, f)
            l >>= 1
            r >>= 1
        # rebuild
        for i in range(1, self.h + 1):
            self._update(l0 >> i)
            self._update((r0 - 1) >> i)

    def set(self, p, val):
        # push path, set leaf, rebuild
        p += self.n0
        for i in range(self.h, 0, -1):
            self._push(p >> i)
        self.d[p] = val
        p >>= 1
        while p:
            self._update(p)
            p >>= 1

    def get(self, p):
        p += self.n0
        for i in range(self.h, 0, -1):
            self._push(p >> i)
        return self.d[p]

    def all_prod(self):
        return self.d[1]

# read input fast
data = list(map(int, sys.stdin.buffer.read().split()))
it = iter(data)
N = next(it)
X = [0]*N
Y = [0]*N
for i in range(N):
    X[i] = next(it)
    Y[i] = next(it)

# coordinate compress
zX = sorted(set(X))
zY = sorted(set(Y))
if len(zX) == 1 or len(zY) == 1:
    print(0)
    sys.exit(0)

rX = [zX.index(x) for x in X]
rY = [zY.index(y) for y in Y]

# fractions in mod
inv4 = modinv(4)
f34 = 3 * inv4 % MOD   # 3/4 mod
f43 = modinv(f34)      # inverse of f34

ans = 0
# two passes (swap axes)
for _ in range(2):
    # build G: for each x-index, list of y-indices
    m = len(zY)
    G = [[] for _ in range(len(zX))]
    for i in range(N):
        G[rX[i]].append(rY[i])

    # initialize V
    V = [(1,1) for _ in range(m)]
    # for each point, if rY+1 < m, multiply V[rY+1].a by f34
    for i in range(N):
        ry = rY[i]
        if ry + 1 < m:
            a, b = V[ry+1]
            V[ry+1] = (a * f34 % MOD, b)
    # prefix multiply
    for i in range(1, m):
        a_prev, _ = V[i-1]
        a, b = V[i]
        V[i] = (a * a_prev % MOD, b)

    seg = LazySegTree(V)
    fs = 1
    for i in range(len(zX)-1):
        for y in G[i]:
            cur = seg.get(y)
            # set second component multiplied by f34
            seg.set(y, (cur[0], cur[1] * f34 % MOD))
            # apply multipliers
            if 0 < y:
                seg.apply(0, y, f34)
            seg.apply(y+1, m, f43)
            fs = fs * f34 % MOD
        all_prd = seg.all_prod()
        a_all, b_all = all_prd
        term = (1 - (a_all * ((1 - b_all) % MOD) % MOD) - fs) % MOD
        width = zX[i+1] - zX[i]
        ans = (ans + term * (width % MOD)) % MOD

    # swap axes
    rX, rY = rY, rX
    zX, zY = zY, zX

# multiply ans by 4^N then by 2
ans = ans * pow(4, N, MOD) % MOD
ans = ans * 2 % MOD
print(ans)