Problem:


Score : 600 points

Problem Statement

We have a set S of N points in a two-dimensional plane. The coordinates of the i-th point are (x_i, y_i). The N points have distinct x-coordinates and distinct y-coordinates.

For a non-empty subset T of S, let f(T) be the number of points contained in the smallest rectangle, whose sides are parallel to the coordinate axes, that contains all the points in T. More formally, we define f(T) as follows:

f(T) :=  (the number of integers i (1 \leq i \leq N) such that a \leq x_i \leq b and c \leq y_i \leq d, where a, b, c, and d are the minimum x-coordinate, the maximum x-coordinate, the minimum y-coordinate, and the maximum y-coordinate of the points in T)

Find the sum of f(T) over all non-empty subset T of S. Since it can be enormous, print the sum modulo 998244353.

Constraints

1 \leq N \leq 2 \times 10^5

-10^9 \leq x_i, y_i \leq 10^9

x_i \neq x_j (i \neq j)

y_i \neq y_j (i \neq j)

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
x_1 y_1
:
x_N y_N

Output

Print the sum of f(T) over all non-empty subset T of S, modulo 998244353.

Sample Input 1

3
-1 3
2 1
3 -2

Sample Output 1

13

Let the first, second, and third points be P_1, P_2, and P_3, respectively. S = \{P_1, P_2, P_3\} has seven non-empty subsets, and f has the following values for each of them:

f(\{P_1\}) = 1

f(\{P_2\}) = 1

f(\{P_3\}) = 1

f(\{P_1, P_2\}) = 2

f(\{P_2, P_3\}) = 2

f(\{P_3, P_1\}) = 3

f(\{P_1, P_2, P_3\}) = 3

The sum of these is 13.

Sample Input 2

4
1 4
2 1
3 3
4 2

Sample Output 2

34

Sample Input 3

10
19 -11
-3 -12
5 3
3 -15
8 -14
-9 -20
10 -9
0 2
-7 17
6 -6

Sample Output 3

7222

Be sure to print the sum modulo 998244353.



Sample input:
3
-1 3
2 1
3 -2


Sample output:
13

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


### BIT binary
def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)
#a1 ~ aiまでの和 O(logn)
def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res

#ai += x(logN)
def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return

n = int(input())
xy = [tuple(map(int, input().split())) for _ in range(n)]
from bisect import bisect_left
def press(l):
    # xs[inds[i]]==l[i]となる
    xs = sorted(set(l))
    inds = [None] * len(l)
    for i,item in enumerate(l):
        inds[i] = bisect_left(xs, item)
    return xs, inds
_, indx = press([item[0] for item in xy])
_, indy = press([item[1] for item in xy])
xy = []
for i in range(n):
    xy.append(indy[i]+indx[i]*n)
xy.sort()
M = 998244353
# ans = (pow(2, n, M) * n) % M
pows = [0]*(n+1)
v = 1
for i in range(n+1):
    pows[i] = v-1
    v *= 2
    v %= M
ans = (pows[n]*n) % M
bit = [0]*(n+1)
for i in range(n):
    x,y = divmod(xy[i],n)
    ans -= pows[i] + pows[n-i-1]
    ans += pows[query(bit, y+1)] + pows[i - query(bit, y+1)]
    add(bit, y+1, 1)
    ans %= M
from operator import itemgetter
xy.sort(key=lambda item: item%n)
bit = [0]*(n+1)
for i in range(n):
    x,y = divmod(xy[i],n)
    ans -= pows[i] + pows[n-i-1]
    ans += pows[i - query(bit, x+1)]
    add(bit, x+1, 1)
    ans %= M
bit = [0]*(n+1)
for i in range(n-1, -1, -1):
    x,y = divmod(xy[i], n)
    ans += pows[(n-1-i) - query(bit, x+1)]
    add(bit, x+1, 1)
    ans %= M
print(ans%M)

Submission status: Accepted

Solution code:
import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

mod = 998244353

def main():
    n = int(input())
    XY = []
    X = set()
    Y = set()
    for i in range(n):
        x,y = map(int, input().split())
        XY.append((x, y))
        X.add(x)
        Y.add(y)

    X = list(X)
    Y = list(Y)
    X.sort()
    Y.sort()
    dx = {}
    for i, x in enumerate(X):
        dx[x] = i
    dy = {}
    for i, y in enumerate(Y):
        dy[y] = i

    XY.sort()
    XY = [(dx[x], dy[y]) for x, y in XY]

    class BIT:
        def __init__(self, n):
            self.n = n
            self.bit = [0]*(self.n+1) # 1-indexed

        def init(self, init_val):
            for i, v in enumerate(init_val):
                self.add(i, v)

        def add(self, i, x):
            # i: 0-indexed
            i += 1 # to 1-indexed
            while i <= self.n:
                self.bit[i] += x
                i += (i & -i)

        def sum(self, i, j):
            # return sum of [i, j)
            # i, j: 0-indexed
            return self._sum(j) - self._sum(i)

        def _sum(self, i):
            # return sum of [0, i)
            # i: 0-indexed
            res = 0
            while i > 0:
                res += self.bit[i]
                i -= i & (-i)
            return res

        def lower_bound(self, x):
            s = 0
            pos = 0
            depth = self.n.bit_length()
            v = 1 << depth
            for i in range(depth, -1, -1):
                k = pos + v
                if k <= self.n and s + self.bit[k] < x:
                        s += self.bit[k]
                        pos += v
                v >>= 1
            return pos

    UL = [0]*n
    UR = [0]*n
    LL = [0]*n
    LR = [0]*n

    bit = BIT(2*10**5+5)
    for i in range(n):
        x, y = XY[i]
        LL[i] = bit.sum(0, y+1)
        UL[i] = i-LL[i]
        bit.add(y, 1)

    bit = BIT(2*10**5+5)
    for i in reversed(range(n)):
        x, y = XY[i]
        LR[i] = bit.sum(0, y+1)
        UR[i] = (n-1-i)-LR[i]
        bit.add(y, 1)

    #print(LL)
    #print(UL)
    #print(LR)
    #print(UR)

    ans = 0
    for i in range(n):
        ans += (pow(2, UL[i], mod)-1)*(pow(2, LR[i], mod)-1)*pow(2, UR[i], mod)*pow(2, LL[i], mod)
        ans += pow(2, UL[i], mod)*pow(2, LR[i], mod)*(pow(2, UR[i], mod)-1)*(pow(2, LL[i], mod)-1)
        ans -= (pow(2, UL[i], mod)-1)*(pow(2, LR[i], mod)-1)*(pow(2, UR[i], mod)-1)*(pow(2, LL[i], mod)-1)
        ans += pow(2, UL[i], mod)*pow(2, LR[i], mod)*pow(2, UR[i], mod)*pow(2, LL[i], mod)
        ans %= mod
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import math

input = sys.stdin.readline

class BIT:
    def __init__(self, len_A):
        self.N = len_A + 10
        self.bit = [0]*(len_A+10)

    def query(self, i):
        res = 0
        idx = i+1
        while idx:
            res += self.bit[idx]
            idx -= idx & (-idx)
        return res

    def update(self, i, x):
        idx = i+1
        while idx < self.N:
            self.bit[idx] += x
            idx += idx & (-idx)

    def lower_left(self, w):
        if (w < 0):
            return -1
        x = 0
        k = 1 << (self.N.bit_length()-1)
        while k > 0:
            if x+k < self.N and self.bit[x+k] < w:
                w -= self.bit[x+k]
                x += k
            k //= 2
        return x


N = int(input())
xy = sorted([list(map(int, input().split())) for _ in range(N)], key=lambda x: x[1])
P = 998244353

# 頂点上の圧縮
for i in range(N):
    xy[i][1] = i
xy = sorted(xy)
for i in range(N):
    xy[i][0] = i

# 各領域の点の数数える
ld, lu, rd, ru = [-1] * N, [-1] * N, [-1] * N, [-1] * N

bit = BIT(N)

for i in range(N):
    ld[i] = bit.query(xy[i][1])
    lu[i] = bit.query(N) - ld[i]
    bit.update(xy[i][1], 1)

bit = BIT(N)

for i in range(N-1, -1, -1):
    rd[i] = bit.query(xy[i][1])
    ru[i] = bit.query(N) - rd[i]
    bit.update(xy[i][1], 1)

ans = 0  #(pow(2, N, P)-1) * N % P
for i in range(N):
    ans = (ans + pow(2, N, P) - 1) % P
    ans = (ans - (pow(2, rd[i] + ru[i], P)-1 )) % P
    ans = (ans - (pow(2, ld[i] + lu[i], P) - 1)) % P
    ans = (ans - (pow(2, rd[i] + ld[i], P) - 1)) % P
    ans = (ans - (pow(2, ru[i] + lu[i], P) - 1)) % P
    ans = (ans + (pow(2, ru[i], P) - 1)) % P
    ans = (ans + (pow(2, rd[i], P) - 1)) % P
    ans = (ans + (pow(2, lu[i], P) - 1)) % P
    ans = (ans + (pow(2, ld[i], P) - 1)) % P
print(ans)

Submission status: Accepted

Solution code:
# 解説放送の方針
# 平面走査をし、各点について、左上、左下、右上、右下にある点を数え、計算する。
# 解説放送ではBITを2本使っていたが、座標圧縮の結果を利用してBIT１本で済むようにした

N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]

mod = 998244353

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

# 平面走査のためのソート（高速化のため１次元にしてソート）
# ソート後の復元+座標圧縮用の辞書作成
# 座標圧縮: 小さいyから順に1,2,3...と値を割り振る。
xy2 = []
Y = []
for i in range(N):
  x,y = xy[i]
  Y.append(y)
  x += 10**9
  y += 10**9
  xy2.append(x<<80 | y << 40 | i)

Y = sorted(Y)
y_compress = {Y[i]:i+1 for i in range(N)}
  
xy2 = sorted(xy2)
mask = (1<<40)-1
bit=BIT(N)

# いちいち2^nを計算していると遅いのでテーブル作成
pow2 = [1]*(N+1)
for i in range(1,N+1):
  pow2[i] = pow2[i-1]*2 %mod

ans = 0
for x in xy2:
  i = x & mask
  x >>= 40
  y = x & mask
  y -= 10**9
  x >>= 40
  x -= 10**9
  
  y = y_compress[y]
  bit.add(y,1)
  '''
  今現在みている点より左上と左下にある点の個数（今の点は含まない。以下同じ）。
  BITを使って求める。
  '''
  n1 = bit.query(y-1,N)-1
  n2 = bit.query(0,y)-1 
  '''
  右上と右下。座標圧縮の結果を利用。(N-y(座標圧縮済))はある点より上にある点の総数。
  そこからn1（走査済みの点の個数)を引くことで、まだ走査していない点の個数を求めることができる。
  '''
  n3 = N-y-n1 
  n4 = y-n2-1
  
  prod14 = (pow2[n1]-1)*(pow2[n4]-1)*pow2[n2+n3] %mod
  prod23 = (pow2[n2]-1)*(pow2[n3]-1)*pow2[n1+n4] %mod
  prod1234 = (pow2[n1]-1)*(pow2[n4]-1)*(pow2[n2]-1)*(pow2[n3]-1) %mod
  ans += pow2[N-1]+prod14+prod23-prod1234
  ans %= mod
  
print(ans)

Submission status: Accepted

Solution code:
# 解説放送の方針
# 平面走査をし、各点について、左上、左下、右上、右下にある点を数え、計算する。
# 解説放送ではBITを2本使っていたが、座標圧縮の結果を利用してBIT１本で済むようにした

N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]

mod = 998244353

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

# 平面走査のためのソート（高速化のため１次元にしてソート）
xy2 = []
for i in range(N):
  x,y = xy[i]
  x += 10**9
  y += 10**9
  xy2.append(y<<80 | x << 40 | i)

# ソート後の復元+座標圧縮用の辞書作成
# 座標圧縮: 小さいyから順に1,2,3...と値を割り振る。
xy2 = sorted(xy2)
mask = (1<<40)-1
y_order=[0]*N
y_compress={}
for j,y in enumerate(xy2):
  i = y & mask
  y >>= 40
  x = y & mask
  x -= 10**9
  y >>= 40
  y -= 10**9
  y_order[i] = j
  y_compress[y] = j+1

xy2 = []
for i in range(N):
  x,y = xy[i]
  x += 10**9
  y += 10**9
  xy2.append(x<<80 | y << 40 | i)
  
xy2 = sorted(xy2)
mask = (1<<40)-1
bit=BIT(N)
ans = 0
memo=[0]*N

# いちいち2^nを計算していると遅いのでテーブル作成
pow2 = [1]*(N+1)
for i in range(1,N+1):
  pow2[i] = pow2[i-1]*2 %mod

for x in xy2:
  i = x & mask
  x >>= 40
  y = x & mask
  y -= 10**9
  x >>= 40
  x -= 10**9
  
  y = y_compress[y]
  bit.add(y,1)
  '''
  今現在みている点より左上と左下にある点の個数（今の点は含まない。以下同じ）。
  BITを使って求める。
  '''
  n1 = bit.query(y-1,N)-1
  n2 = bit.query(0,y)-1 
  '''
  右上と右下。座標圧縮の結果を利用。(N-y(座標圧縮済))はある点より上にある点の総数。
  そこからn1（走査済みの点の個数)を引くことで、まだ走査していない点の個数を求めることができる。
  '''
  n3 = N-y-n1 
  n4 = y-n2-1
  
  prod14 = (pow2[n1]-1)*(pow2[n4]-1)*pow2[n2+n3] %mod
  prod23 = (pow2[n2]-1)*(pow2[n3]-1)*pow2[n1+n4] %mod
  prod1234 = (pow2[n1]-1)*(pow2[n4]-1)*(pow2[n2]-1)*(pow2[n3]-1) %mod
  ans += pow2[N-1]+prod14+prod23-prod1234
  ans %= mod
  
print(ans)

Submission status: Accepted

Solution code:
# 解説放送の方針
# 平面走査をし、各点について、左上、左下、右上、右下にある点を数え、計算する。
# 解説放送ではBITを2本使っていたが、座標圧縮の結果を利用してBIT１本で済むようにした

N = int(input())
xy = [tuple(map(int,input().split())) for _ in range(N)]

mod = 998244353

class BIT:
    '''https://tjkendev.github.io/procon-library/python/range_query/bit.html'''
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def query(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)

# 平面走査のためのソート（高速化のため１次元にしてソート）
xy2 = []
for i in range(N):
  x,y = xy[i]
  x += 10**9
  y += 10**9
  xy2.append(y<<80 | x << 40 | i)

# ソート後の復元+座標圧縮用の辞書作成
# 座標圧縮: 小さいyから順に1,2,3...と値を割り振る。
xy2 = sorted(xy2)
mask = (1<<40)-1
y_order=[0]*N
y_compress={}
for j,y in enumerate(xy2):
  i = y & mask
  y >>= 40
  x = y & mask
  x -= 10**9
  y >>= 40
  y -= 10**9
  y_order[i] = j
  y_compress[y] = j+1

xy2 = []
for i in range(N):
  x,y = xy[i]
  x += 10**9
  y += 10**9
  xy2.append(x<<80 | y << 40 | i)
  
xy2 = sorted(xy2)
mask = (1<<40)-1
bit=BIT(N)
ans = 0
memo=[0]*N

# いちいち2^nを計算していると遅いのでメモ化
def pow2(x):
  if memo[x-1]:return memo[x-1]
  out = pow(2,x,mod)
  memo[x-1] = out
  return out

for x in xy2:
  i = x & mask
  x >>= 40
  y = x & mask
  y -= 10**9
  x >>= 40
  x -= 10**9
  
  y = y_compress[y]
  bit.add(y,1)
  '''
  今現在みている点より左上と左下にある点の個数（今の点は含まない。以下同じ）。
  BITを使って求める。
  '''
  n1 = bit.query(y-1,N)-1
  n2 = bit.query(0,y)-1 
  '''
  右上と右下。座標圧縮の結果を利用。(N-y(座標圧縮済))はある点より上にある点の総数。
  そこからn1（走査済みの点の個数)を引くことで、まだ走査していない点の個数を求めることができる。
  '''
  n3 = N-y-n1 
  n4 = y-n2-1
  
  prod14 = (pow2(n1)-1)*(pow2(n4)-1)*pow2(n2+n3) %mod
  prod23 = (pow2(n2)-1)*(pow2(n3)-1)*pow2(n1+n4) %mod
  prod1234 = (pow2(n1)-1)*(pow2(n4)-1)*(pow2(n2)-1)*(pow2(n3)-1) %mod
  ans += pow2(N-1)+prod14+prod23-prod1234
  ans %= mod
  
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))


"""
f(T)=iなるTの通り数を数えるか，
f(T)=1がN通り，f(T)=Nはいっぱい．上下左右それぞれのmaxを選び，中のものがm個であるとき2^m通り
x座標，y座標が全て相異なるのが嬉しいかも，でも，これめんどくさすぎる

ある1つの点が与える寄与を考える，

その頂点をTに含む場合＝＞必ず+1 * 2^(N-1)通り

その頂点をTに含まない場合
（右上から1つ以上，左下から1つ以上），（右下から1つ以上，左上から1つ以上）の組なら加算
これらの組みは重複しそうなので，うまく被らないように選ぶ必要あり
（右上，左下，左上0，右下0），（右上，左下，左上，右下0），（右上，左下，左上0，右下）みたいに分けて考える．

でも，各頂点ごとに４つの方向それぞれの頂点数を持つのがまず難しい．
頂点を左から順に走査．左にある頂点の個数を上下別に見ていく．
(左上，左下)を考える．
一番左なら(0,0)，次のものは(0,1) or (1,0)みたいな．見た頂点のy座標(座圧したもの)をsegTreeで管理すれば，上下の個数がそれぞれわかる．

終わったら右からもやれば4方向それぞれの個数が分かりそう．
"""
def main():
    mod=998244353
    class SegTree:
        def __init__(self,N,ide,segfunc=min):
            self.ide_ele = ide
            """
            ex)
             最小値のセグ木 → +inf
              和のセグ木 → 0
              積のセグ木 → 1
              gcdのセグ木 → 0
            """
            
            self.segfunc=segfunc
            
            #num:N以上の最小の2のべき乗
            self.num =2**(N-1).bit_length()
            self.seg=[self.ide_ele]*2*self.num

        #リストで初期化する
        def setL(self,init_val):
            #init_valは操作する数列
            for i in range(self.num):
                self.seg[i+self.num-1]=init_val[i]    
            #built
            for i in range(self.num-2,-1,-1) :
                self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 


        #k番目の値をxに更新
        def update(self,k,x):
            k += self.num-1
            self.seg[k] = x
            while k:
                k = (k-1)//2
                self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])


        #[p,q)の区間に対するクエリへの応答
        def query(self,p,q):
            if q<=p:
                return self.ide_ele
            p += self.num-1
            q += self.num-2
            res=self.ide_ele
            while q-p>1:
                if p&1 == 0:
                    res = self.segfunc(res,self.seg[p])
                if q&1 == 1:
                    res = self.segfunc(res,self.seg[q])
                    q -= 1
                p = p//2
                q = (q-1)//2
            if p == q:
                res = self.segfunc(res,self.seg[p])
            else:
                res = self.segfunc(self.segfunc(res,self.seg[p]),self.seg[q])
            return res
    N=I()
    Y=[0]*N
    from collections import defaultdict
    ddy = defaultdict(int)
    
    L=[[0,0,0]for _ in range(N)]#x,y,i
    for i in range(N):
        x,y=MI()
        Y[i]=y
        L[i]=[x,y,i]
        
    #座圧
    Y.sort()
    for i in range(N):
        ddy[Y[i]]=i
    
    #2べき持っておく
    POW=[1]
    for i in range(N+5):
        p=(POW[-1]*2)%mod
        POW.append(p)
    
    cnt=[[0,0,0,0]for _ in range(N)]# lu,ld,ru,rd
    
    #左から見る
    L.sort()
    # print(L)
    seg=SegTree(N,0,lambda a,b: a+b)
    for j in range(N):#j個すでに見た
        i=L[j][2]#番号iの頂点
        y=L[j][1]
        yy=ddy[y]
        temp=seg.query(yy,N)#上側の個数
        cnt[i][0]=temp
        cnt[i][1]=j-temp
        # print(j,i,yy,temp)
        seg.update(yy,1)
        
    #右から見る
    seg=SegTree(N,0,lambda a,b: a+b)
    for j in range(N):#j個すでに見た
        i=L[-1-j][2]#番号iの頂点
        y=L[-1-j][1]
        yy=ddy[y]
        temp=seg.query(yy,N)#上側の個数
        cnt[i][2]=temp
        cnt[i][3]=j-temp
        seg.update(yy,1)
        
    def calc(cnt_item):
        # 引数：lu,ld,ru,rdの個数
        lu,ld,ru,rd=cnt_item
        
        temp=POW[N-1]#自身がTにある場合，周りはなんでもOK
        
        #自身がTにない場合
        
        #oxxo
        temp+=((POW[lu]-1) * (POW[rd]-1))%mod
        #xoox
        temp+=((POW[ld]-1) * (POW[ru]-1))%mod
        
        #ooox
        temp+=((POW[lu]-1) * (POW[ld]-1) *  (POW[ru]-1))%mod
        #ooxo
        temp+=((POW[lu]-1) * (POW[ld]-1) * (POW[rd]-1))%mod
        #oxoo
        temp+=((POW[lu]-1) *  (POW[ru]-1) * (POW[rd]-1))%mod
        #xooo
        temp+=((POW[ld]-1) *  (POW[ru]-1) * (POW[rd]-1))%mod
        
        #oooo
        temp+=((POW[lu]-1) * (POW[ld]-1) *  (POW[ru]-1) * (POW[rd]-1))%mod
        
        temp%=mod
        
        # print(cnt_item,temp)
        return temp
    
    ans=0
    for i in range(N):
        # print(i)
        ans=(ans+calc(cnt[i]))%mod
        
    print(ans)




main()

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

class BIT:
    #1-indexed
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        self.p = 2**(n.bit_length() - 1)
        self.dep = n.bit_length()
    def get(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
    
    def bl(self, v):
        if v <= 0:
            return -1
        s = 0
        k = self.p
        for _ in range(self.dep):
            if s + k <= self.size and self.tree[s+k] < v:
                s += k
                v -= self.tree[s+k]
            k //= 2
        return s + 1

def compress(L):
    L2 = list(set(L))
    L2.sort()
    C = {v : k for k, v in enumerate(L2)}
    return L2, C


MOD = 998244353
N = int(readline())
XY = [list(map(int, readline().split())) for _ in range(N)]
XY.sort()

Z = [-10**10]
for x, y in XY:
    Z.append(y)

_, CC = compress(Z)
XY = [(x, CC[y]) for x, y in XY] 

SS, SB, BS, BB = [None]*N, [None]*N, [None]*N, [None]*N

T = BIT(N)
for i in range(N):
    k = i
    y = XY[i][1]
    l = T.get(y)
    SS[i] = l
    SB[i] = k-l
    T.add(y, 1)
T = BIT(N)
for i in range(N-1, -1, -1):
    k = N-1-i
    y = XY[i][1]
    l = T.get(y)
    BS[i] = l
    BB[i] = k-l
    T.add(y, 1)

P2 = [1]*1341398
for i in range(1, len(P2)):
    P2[i] = P2[i-1]*2%MOD

ans = 0
for i in range(N):
    ss = SS[i]
    sb = SB[i]
    bs = BS[i]
    bb = BB[i]
    ans = (ans + P2[N-1])%MOD
    ans = (ans + P2[N-1-ss-bb]*(P2[ss]-1)*(P2[bb]-1))%MOD
    ans = (ans + P2[N-1-sb-bs]*(P2[sb]-1)*(P2[bs]-1))%MOD
    ans = (ans - (P2[sb]-1)*(P2[bs]-1)*(P2[ss]-1)*(P2[bb]-1))%MOD
    
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 998244353
n = int(input())
XY = sorted(tuple(map(int, input().split())) for _ in range(n))
X, Y = zip(*XY)
L = {y:i+1 for i, y in enumerate(sorted(Y))}
Y = tuple(L[y] for y in Y)
BIT = [0]*(n+1)
def add(i):
  while i<=n:
    BIT[i] += 1
    i += i&-i
def acc(i):
  res = 0
  while i:
    res += BIT[i]
    i -= i&-i
  return res
A = [0]*n
B = [0]*n
C = [0]*n
D = [0]*n
for i, y in enumerate(Y):
  A[i] = acc(y)
  B[i] = i - A[i]
  add(y)
BIT = [0]*(n+1)
for i in range(n-1, -1, -1):
  y = Y[i]
  C[i] = acc(y)
  D[i] = n-1-i - C[i]
  add(y)
T = [1]*n
for i in range(n-1):
  T[i+1] = T[i]*2%mod
ans = T[n-1] * n % mod
for a, b, c, d in zip(A, B, C, D):
  a = T[a]
  b = T[b]
  c = T[c]
  d = T[d]
  temp = (a-1)*b*c*(d-1) + a*(b-1)*(c-1)*d - (a-1)*(b-1)*(c-1)*(d-1)
  ans += temp
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
mod = 998244353
n = int(input())
XY = sorted(tuple(map(int, input().split())) for _ in range(n))
X, Y = zip(*XY)
L = {y:i+1 for i, y in enumerate(sorted(Y))}
Y = tuple(L[y] for y in Y)
BIT = [0]*(n+1)
def add(i):
  while i<=n:
    BIT[i] += 1
    i += i&-i
def acc(i):
  res = 0
  while i:
    res += BIT[i]
    i -= i&-i
  return res
A = [0]*n
B = [0]*n
C = [0]*n
D = [0]*n
for i, y in enumerate(Y):
  A[i] = acc(y)
  B[i] = i - A[i]
  add(y)
BIT = [0]*(n+1)
for i in range(n-1, -1, -1):
  y = Y[i]
  C[i] = acc(y)
  D[i] = n-1-i - C[i]
  add(y)
ans = pow(2, n-1, mod) * n % mod
for a, b, c, d in zip(A, B, C, D):
  a = pow(2, a, mod)
  b = pow(2, b, mod)
  c = pow(2, c, mod)
  d = pow(2, d, mod)
  temp = (a-1)*b*c*(d-1) + a*(b-1)*(c-1)*d - (a-1)*(b-1)*(c-1)*(d-1)
  ans += temp
  ans %= mod
print(ans)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

class Seg_sum():
    def __init__(self,x):
        #####単位元######
        self.ide_ele_min = 0
        self.func = lambda a,b : a+b

        self.n = len(x)

        #num_max:n以上の最小の2のべき乗
        self.num_max =2**(self.n-1).bit_length()
        self.x = [self.ide_ele_min]*2*self.num_max

        for i,num in enumerate(x, self.num_max):
            self.x[i] = num
        for i in range(self.num_max-1,0,-1):
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def update(self,i,x):
        i += self.num_max
        self.x[i] = x
        while(i>0):
            i = i//2
            self.x[i] = self.func(self.x[i<<1],self.x[(i<<1) + 1])

    def query(self,i,j):
        res = self.ide_ele_min
        if i>=j:
            return res
        i += self.num_max
        j += self.num_max -1
        while(i<=j):
            if(i==j):
                res = self.func(res,self.x[i])
                break
            if(i&1):
                res = self.func(res,self.x[i])
                i += 1
            if(not j&1):
                res = self.func(res,self.x[j])
                j -= 1
            i = i>>1
            j = j>>1
        return res

n = int(readline())
xy = [ list(map(int,i.split()))  for i in readlines()]
mod = 998244353

xy.sort()
ys = [i[1] for i in xy]
ys.sort()
y_rank = {}
for i,y in enumerate(ys):
    y_rank[y] = i


point = [[0,0] for _ in range(n)]
for i,(x,y) in enumerate(xy):
    point[i][0] = i
    point[i][1] = y_rank[y]

seg = Seg_sum([0] * (n+10))

cnt = [[0,0,0,0] for _ in range(n)]
for x,y in point:
    cnt[x][2] = seg.query(0,y)
    cnt[x][1] = seg.query(y,n)
    cnt[x][0] = n-y-1 - cnt[x][1]
    cnt[x][3] = y - cnt[x][2]
    seg.update(y,1)

ex2 = [1] * (n)
for i in range(1,n):
    ex2[i] = (ex2[i-1]*2)%mod

ans = (ex2[n-1] * n) % mod
for n1,n2,n3,n4 in cnt:
    ans += (ex2[n1]-1)*(ex2[n3]-1)*ex2[n2+n4]
    ans %= mod
    ans += (ex2[n2]-1)*(ex2[n4]-1)*ex2[n1+n3]
    ans %= mod
    ans -= (ex2[n1]-1)*(ex2[n2]-1)*(ex2[n3]-1)*(ex2[n4]-1)
    ans %= mod

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)

    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
xy.sort(key=lambda t: t[0])
idx = compress([xy_i[1] for xy_i in xy])
lbit = BIT(N)
rbit = BIT(N)

for i in range(N):
    rbit.add(i, 1)
    
ans = 0
MOD = 998244353

for i in range(N):
    y = xy[i][1]
    rbit.add(idx[y], -1)
    a = i-lbit.acc(idx[y])
    b = lbit.acc(idx[y])
    c = rbit.acc(idx[y])
    d = N-1-i-rbit.acc(idx[y])
    add = 2*pow(2, N-1, MOD)-1
    pa = pow(2, a, MOD)
    pb = pow(2, b, MOD)
    pc = pow(2, c, MOD)
    pd = pow(2, d, MOD)
    add = (add-(pa-1))%MOD
    add = (add-(pb-1))%MOD
    add = (add-(pc-1))%MOD
    add = (add-(pd-1))%MOD
    add = (add-(pa*pb-pa-pb+1))%MOD
    add = (add-(pb*pc-pb-pc+1))%MOD
    add = (add-(pc*pd-pc-pd+1))%MOD
    add = (add-(pd*pa-pd-pa+1))%MOD
    ans += add
    ans %= MOD
    lbit.add(idx[y], 1)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from collections import *

def compress(l):
    l = list(set(l))
    l.sort()
    idx = defaultdict(int)

    for i in range(len(l)):
        idx[l[i]] = i
    
    return idx
    
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(n+1)
    
    def add(self, i, x):
        i += 1
        
        while i<=self.n:
            self.bit[i] += x
            i += i&(-i)

    def acc(self, i):
        s = 0
        
        while i>0:
            s += self.bit[i]
            i -= i&(-i)
        
        return s

N = int(input())
xy = [tuple(map(int, input().split())) for _ in range(N)]
xy.sort(key=lambda t: t[0])
idx = compress([xy_i[1] for xy_i in xy])
lbit = BIT(N)
rbit = BIT(N)

for i in range(N):
    rbit.add(i, 1)
    
ans = 0
MOD = 998244353

for i in range(N):
    y = xy[i][1]
    rbit.add(idx[y], -1)
    a = i-lbit.acc(idx[y])
    b = lbit.acc(idx[y])
    c = rbit.acc(idx[y])
    d = N-1-i-rbit.acc(idx[y])
    add = 2*pow(2, N-1, MOD)-1
    add = (add-(pow(2, a, MOD)-1))%MOD
    add = (add-(pow(2, b, MOD)-1))%MOD
    add = (add-(pow(2, c, MOD)-1))%MOD
    add = (add-(pow(2, d, MOD)-1))%MOD
    add = (add-(pow(2, a+b, MOD)-pow(2, a, MOD)-pow(2, b, MOD)+1))%MOD
    add = (add-(pow(2, b+c, MOD)-pow(2, b, MOD)-pow(2, c, MOD)+1))%MOD
    add = (add-(pow(2, c+d, MOD)-pow(2, c, MOD)-pow(2, d, MOD)+1))%MOD
    add = (add-(pow(2, d+a, MOD)-pow(2, d, MOD)-pow(2, a, MOD)+1))%MOD
    ans += add
    ans %= MOD
    lbit.add(idx[y], 1)

print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    dat = [LI() for _ in range(N)]
    dat.sort()
    yo = [y for _,y in dat]
    yo.sort()

    up = [0] * N
    dw = [0] * N

    bit = [0] * (N+1)

    def bit_add(i):
        while i <= N:
            bit[i] += 1
            i += i & -i

    def bit_sum(i):
        ret = 0
        while i > 0:
            ret += bit[i]
            i -= i & -i
        return ret

    for i in range(N):
        x,y = dat[i]
        y = bisect.bisect_left(yo,y) + 1
        up[i] = bit_sum(y)
        bit_add(y)

    bit = [0] * (N+1)
    for i in range(N-1,-1,-1):
        x,y = dat[i]
        y = bisect.bisect_left(yo,y) + 1
        dw[i] = bit_sum(y)
        bit_add(y)

    ans = N * pow(2,N-1,MOD)
    for i in range(N):
        a = i - up[i]
        b = up[i]
        c = N-(i+1) - dw[i]
        d = dw[i]
        pa = pow(2,a,MOD)
        pb = pow(2,b,MOD)
        pc = pow(2,c,MOD)
        pd = pow(2,d,MOD)
        pad = pow(2,a+d,MOD)
        pbc = pow(2,b+c,MOD)
        p = (pad-1) - (pa-1) - (pd-1)
        q = (pbc-1) - (pb-1) - (pc-1)
        x = p * pbc
        y = q * pad
        z = p * q
        ans = (ans + x + y - z) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    dat = [LI() for _ in range(N)]
    dat.sort()
    yo = [y for _,y in dat]
    yo.sort()

    up = [0] * N
    dw = [0] * N

    bit = [0] * (N+1)

    def bit_add(i):
        while i <= N:
            bit[i] += 1
            i += i & -i

    def bit_sum(i):
        ret = 0
        while i > 0:
            ret += bit[i]
            i -= i & -i
        return ret

    for i in range(N):
        x,y = dat[i]
        y = bisect.bisect_left(yo,y) + 1
        up[i] = bit_sum(y)
        bit_add(y)

    bit = [0] * (N+1)
    for i in range(N-1,-1,-1):
        x,y = dat[i]
        y = bisect.bisect_left(yo,y) + 1
        dw[i] = bit_sum(y)
        bit_add(y)

    ans = N * pow(2,N-1,MOD)
    for i in range(N):
        a = i - up[i]
        b = up[i]
        c = N-(i+1) - dw[i]
        d = dw[i]
        pa = pow(2,a,MOD)
        pb = pow(2,b,MOD)
        pc = pow(2,c,MOD)
        pd = pow(2,d,MOD)
        p = (pow(2,a+d,MOD)-1) - (pa-1) - (pd-1)
        q = (pow(2,b+c,MOD)-1) - (pb-1) - (pc-1)
        x = p * (pb + pc - 1)
        y = q * (pa + pd - 1)
        z = p * q
        ans = (ans + x + y + z) % MOD
    print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    MOD = 998244353
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    dat = [LI() for _ in range(N)]
    dat.sort()
    yo = [y for _,y in dat]
    yo.sort()

    up = [0] * N
    dw = [0] * N

    bit = [0] * (N+1)

    def bit_add(i):
        while i <= N:
            bit[i] += 1
            i += i & -i

    def bit_sum(i):
        ret = 0
        while i > 0:
            ret += bit[i]
            i -= i & -i
        return ret

    for i in range(N):
        x,y = dat[i]
        y = bisect.bisect_left(yo,y) + 1
        up[i] = bit_sum(y)
        bit_add(y)

    bit = [0] * (N+1)
    for i in range(N-1,-1,-1):
        x,y = dat[i]
        y = bisect.bisect_left(yo,y) + 1
        dw[i] = bit_sum(y)
        bit_add(y)

    ans = N * pow(2,N-1,MOD)
    for i in range(N):
        a = i - up[i]
        b = up[i]
        c = N-(i+1) - dw[i]
        d = dw[i]
        p = (pow(2,a+d,MOD)-1) - (pow(2,a,MOD)-1) - (pow(2,d,MOD)-1)
        q = (pow(2,b+c,MOD)-1) - (pow(2,b,MOD)-1) - (pow(2,c,MOD)-1)
        x = p * (pow(2,b,MOD) + pow(2,c,MOD)-1)
        y = q * (pow(2,a,MOD) + pow(2,d,MOD)-1)
        z = p * q
        ans = (ans + x + y + z) % MOD
    print(ans)

if __name__ == '__main__':
    main()