結果

問題 No.3530 「」
コンテスト
ユーザー aa36
提出日時 2026-02-27 12:35:56
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 4,975 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 413 ms
コンパイル使用メモリ 85,248 KB
実行使用メモリ 392,232 KB
最終ジャッジ日時 2026-05-04 20:52:08
合計ジャッジ時間 26,596 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 15 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline

MOD = 998244353

class mint:
    __slots__ = ("v",)

    def __init__(self, v=0):
        if isinstance(v, mint):
            self.v = v.v
        else:
            self.v = v % MOD

    def _to_mint(self, other):
        return other if isinstance(other, mint) else mint(other)

    def __add__(self, other):
        other = self._to_mint(other)
        return mint(self.v + other.v)

    def __sub__(self, other):
        other = self._to_mint(other)
        return mint(self.v - other.v)

    def __mul__(self, other):
        other = self._to_mint(other)
        return mint(self.v * other.v)

    def __truediv__(self, other):
        other = self._to_mint(other)
        return self * other.inv()

    def __radd__(self, other):
        return self + other

    def __rsub__(self, other):
        return mint(other) - self

    def __rmul__(self, other):
        return self * other

    def inv(self):
        return mint(pow(self.v, MOD - 2, MOD))

    def val(self):
        return self.v

class LazySegTree:
    def __init__(self, n, op, e, mapping, composition, id_):
        self.n = n
        self.op = op
        self.e = e
        self.mapping = mapping
        self.composition = composition
        self.id = id_

        self.size = 1
        while self.size < n:
            self.size <<= 1

        self.d = [e() for _ in range(2 * self.size)]
        self.lz = [id_() for _ in range(self.size)]

    def build(self, arr):
        for i in range(len(arr)):
            self.d[self.size + i] = arr[i]
        for i in reversed(range(1, self.size)):
            self.d[i] = self.op(self.d[i << 1], self.d[i << 1 | 1])

    def _apply(self, k, f):
        self.d[k] = self.mapping(f, self.d[k])
        if k < self.size:
            self.lz[k] = self.composition(f, self.lz[k])

    def _push(self, k):
        if self.lz[k].v != 1:
            self._apply(k << 1, self.lz[k])
            self._apply(k << 1 | 1, self.lz[k])
            self.lz[k] = self.id()

    def set(self, p, x):
        p += self.size
        for i in range(self.size.bit_length(), 0, -1):
            self._push(p >> i)
        self.d[p] = x
        while p > 1:
            p >>= 1
            self.d[p] = self.op(self.d[p << 1], self.d[p << 1 | 1])

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

    def apply(self, l, r, f):
        if l >= r:
            return
        l += self.size
        r += self.size
        l0, r0 = l, r

        for i in range(self.size.bit_length(), 0, -1):
            if ((l0 >> i) << i) != l0:
                self._push(l0 >> i)
            if ((r0 >> i) << i) != r0:
                self._push((r0 - 1) >> i)

        while l < r:
            if l & 1:
                self._apply(l, f)
                l += 1
            if r & 1:
                r -= 1
                self._apply(r, f)
            l >>= 1
            r >>= 1

        for i in range(1, self.size.bit_length() + 1):
            if ((l0 >> i) << i) != l0:
                k = l0 >> i
                self.d[k] = self.op(self.d[k << 1], self.d[k << 1 | 1])
            if ((r0 >> i) << i) != r0:
                k = (r0 - 1) >> i
                self.d[k] = self.op(self.d[k << 1], self.d[k << 1 | 1])

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

def op(a, b):
    return (a[0] * (mint(1) - a[1]) + b[0] * (mint(1) - b[1]), mint(0))

def e():
    return (mint(1), mint(1))

def mapping(f, x):
    return (x[0] * f, x[1])

def composition(f, g):
    return f * g

def id_():
    return mint(1)

N = int(input())
X = []
Y = []
for _ in range(N):
    x, y = map(int, input().split())
    X.append(x)
    Y.append(y)

zX = sorted(set(X))
zY = sorted(set(Y))

if len(zX) == 1 or len(zY) == 1:
    print(0)
    exit()

zx_id = {x: i for i, x in enumerate(zX)}
zy_id = {y: i for i, y in enumerate(zY)}

rX = [zx_id[x] for x in X]
rY = [zy_id[y] for y in Y]

f34 = mint(3) / mint(4)
f43 = mint(1) / f34

ans = mint(0)

for _ in range(2):
    G = [[] for _ in range(len(zX))]
    for i in range(N):
        G[rX[i]].append(rY[i])

    V = [e() for _ 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, V[rY[i] + 1][1])

    for i in range(1, len(zY)):
        V[i] = (V[i][0] * V[i - 1][0], V[i][1])

    seg = LazySegTree(len(zY), op, e, mapping, composition, id_)
    seg.build(V)

    fs = mint(1)

    for i in range(len(zX) - 1):
        for y in G[i]:
            cur0, cur1 = seg.get(y)
            seg.set(y, (cur0, cur1 * f34))
            seg.apply(0, y, f34)
            seg.apply(y + 1, len(zY), f43)
            fs *= f34

        all0, all1 = seg.all_prod()
        ans += (mint(1) - all0 * (mint(1) - all1) - fs) * (zX[i + 1] - zX[i])

    rX, rY = rY, rX
    zX, zY = zY, zX

for _ in range(N):
    ans *= mint(4)

print((ans * mint(2)).val())
0