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: Wrong Answer

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=10**9+7
    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にない場合
        
        #oxxx
        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: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
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
T =  np.array(T, dtype=np.int64)
ans = T[n-1] * n % mod
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)
temp %= mod
cnt = temp.sum()%mod
ans += cnt
ans %= mod
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
def main():
  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
  A = np.array(tuple(T[a] for a in A), dtype=np.int64)
  B = np.array(tuple(T[b] for b in B), dtype=np.int64)
  C = np.array(tuple(T[c] for c in C), dtype=np.int64)
  D = np.array(tuple(T[d] for d in D), dtype=np.int64)
  temp = (A-1)*B*C*(D-1) + A*(B-1)*(C-1)*D - (A-1)*(B-1)*(C-1)*(D-1)
  temp %= mod
  cnt = temp.sum()%mod
  ans += cnt
  ans %= mod
  print(ans)
if __name__ == "__main__":
  main()

Submission status: Wrong Answer

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) - 1
    for i in range(N):
        a = i - up[i]
        b = up[i]
        c = N-(i+1) - dw[i]
        d = dw[i]
        x = ((pow(2,a+d,MOD)-1) - (pow(2,a,MOD)-1) - (pow(2,d,MOD)-1)) * (pow(2,b,MOD) + pow(2,c,MOD))
        y = ((pow(2,b+c,MOD)-1) - (pow(2,b,MOD)-1) - (pow(2,c,MOD)-1)) * (pow(2,a,MOD) + pow(2,d,MOD))
        ans = (ans + x + y) % MOD
    print(ans)




if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
I = [int(_) for _ in open(0).read().split()]
N, X, Y = I[0], I[1::2], I[2::2]
mod = 998244353


def compress_coord(raw):
    #i_v = {}
    v_i = {}
    for i, v in enumerate(sorted(set(raw))):
        #i_v[i] = v
        v_i[v] = i
    return v_i  #, i_v


class BinaryIndexedTree():
    def __init__(self, n):
        """
        constructs binary indexed tree

        Parameters
        ----------
        n : int
            maximum index value
        """
        self.n = n
        self.dat = [0] * (n + 1)

    def sum(self, i):
        """
        returns the sum of [1, i]

        Parameters
        ----------
        i : int
            right end of the interval
        """
        s = 0
        while i:
            s += self.dat[i]
            i -= i & -i
        return s

    def add(self, i, x):
        """
        adds x to i-th element

        Parameters
        ----------
        i : int
            index
        x : int
            additional value
        """
        while i <= self.n:
            self.dat[i] += x
            i += i & -i


xi = compress_coord(X)
yj = compress_coord(Y)
X = [xi[x] for x in X]
Y = [yj[y] for y in Y]
LL = {}
LR = {}
RL = {}
RR = {}
sortXY = sorted(zip(X, Y))
bit = BinaryIndexedTree(N + 10)
for x, y in sortXY:
    LL[(x, y)] = bit.sum(y + 1)
    LR[(x, y)] = bit.sum(N + 1) - bit.sum(y + 1)
    bit.add(y + 1, 1)
bit = BinaryIndexedTree(N + 10)
for x, y in sortXY[::-1]:
    RL[(x, y)] = bit.sum(y + 1)
    RR[(x, y)] = bit.sum(N + 1) - bit.sum(y + 1)
    bit.add(y + 1, 1)

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np
import numba
from numba import njit
i8 = numba.int64

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

@njit((i8[:], ), cache=True)
def build(raw_data):
    bit = raw_data.copy()
    for i in range(len(bit)):
        j = i + (i & (-i))
        if j < len(bit):
            bit[j] += bit[i]
    return bit


@njit((i8[:], i8), cache=True)
def get_sum(bit, i):
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


@njit((i8[:], i8, i8), cache=True)
def add(bit, i, x):
    while i < len(bit):
        bit[i] += x
        i += i & -i


@njit((i8[:], i8), cache=True)
def find_kth_element(bit, k):
    N = len(bit)
    x, sx = 0, 0
    dx = 1
    while 2 * dx < N:
        dx *= 2
    while dx:
        y = x + dx
        if y < N:
            sy = sx + bit[y]
            if sy < k:
                x, sx = y, sy
        dx //= 2
    return x + 1

@njit((i8[:], ), cache=True)
def main(XY):
    X, Y = XY[::2], XY[1::2]
    N = len(Y)
    ind = X.argsort()
    X, Y = X[ind], Y[ind]
    # 座圧
    Y_sort = Y.copy()
    Y_sort.sort()
    Y = np.searchsorted(Y_sort, Y, 'right')
    bit = np.zeros(N + 10, np.int64)

    pow2 = np.ones(N + 10, np.int64)
    for n in range(1, N + 10):
        pow2[n] = 2 * pow2[n - 1] % MOD

    ret = 0
    for i in range(N):
        y = Y[i]
        L = i
        R = N - 1 - i
        LD = get_sum(bit, y)
        add(bit, y, 1)
        LU = L - LD
        D = y - 1
        U = N - 1 - D
        RD = D - LD
        RU = R - RD

        x = pow2[N] - 1
        x -= pow2[L] + pow2[R] + pow2[D] + pow2[U]
        x += pow2[LD] + pow2[LU] + pow2[RD] + pow2[RU]
        ret += x
    return ret % MOD

N = int(readline())
XY = np.array(read().split(), np.int64)

print(main(XY))

Submission status: Wrong Answer

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(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
input = sys.stdin.readline
from collections import defaultdict
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
dcy = defaultdict(int)
xy = [list(map(int,input().split())) for i in range(n)]
xy.sort()
yls = list(zip(*xy))[1]
yls = list(yls)
for i in range(n):
  dcy[yls[i]] = i
yls.sort()
yind = [0 for i in range(n)]
for i in range(n):
  ind = dcy[yls[i]]
  yind[ind] = i
xyd = []
for i in range(n):
  xyd.append((i,yind[i]))
ans = 0
bit = Bit(n+1)
"""
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)
"""

Submission status: Wrong Answer

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(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
input = sys.stdin.readline
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
xy = [list(map(int,input().split())) for i in range(n)]
xy.sort()
yls = list(zip(*xy))[1]
yd = [(yls[i],i) for i in range(n)]
yd.sort()
yind = [0 for i in range(n)]
for i in range(n):
  y = yd[i][1]
  yind[y] = i
xyd = []
for i in range(n):
  xyd.append((i,yind[i]))
ans = 0
bit = Bit(n+1)
"""
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)
"""

Submission status: Wrong Answer

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(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
input = sys.stdin.readline
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
xy = [list(map(int,input().split())) for i in range(n)]
xy.sort()
yls = list(zip(*xy))[1]
yd = [(yls[i],i) for i in range(n)]
yd.sort()
yind = [0 for i in range(n)]
for i in range(n):
  y = yd[i][1]
  yind[y] = i
xyd = []
for i in range(n):
  xyd.append((i,yind[i]))
ans = 0
bit = Bit(n+1)
xyd.sort()
"""
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)
"""

Submission status: Wrong Answer

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(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
input = sys.stdin.readline
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
xi,yi = [],[]
for i in range(n):
  x,y = map(int,input().split())
  xi.append((x,i))
  yi.append((y,i))
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
"""
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)
"""

Submission status: Wrong Answer

Solution code:
import sys
class Bit:
  def __init__(self,n):
    self.size = n
    self.tree = [0]*(n+1)
 
  def sum(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
input = sys.stdin.readline
mod = 998244353
n = int(input())
p2t = [1]
for i in range(n):
  p2t.append(p2t[-1]*2%mod)
xy = [list(map(int,input().split())) for i in range(n)]
xls,yls = list(zip(*xy))
xi = [(xls[i],i) for i in range(n)]
yi = [(yls[i],i) for i in range(n)]
xi.sort()
yi.sort()
xd = [0 for i in range(n)]
yd = [0 for i in range(n)]
for i in range(n):
  x,ix = xi[i]
  y,iy = yi[i]
  xd[ix] = i
  yd[iy] = i
ans = 0
bit = Bit(n+1)
xyd = list(zip(xd,yd))
xyd.sort()
"""
for i in range(n):
  x,y = xyd[i]
  upper = n-y-1
  right = n-x-1
  ld = bit.sum(y+1)
  ru = upper+right+ld-n+1
  rd = right-ru
  lu = upper-ru
  p2lu = p2t[lu]
  p2rd = p2t[rd]
  p2ru = p2t[ru]
  p2ld = p2t[ld]
  ans += ((p2lu-1)*(p2rd-1)*(p2t[ld+ru])%mod+(p2ld-1)*(p2ru-1)*(p2t[lu+rd])%mod+
  p2t[n-1]-(p2lu-1)*(p2rd-1)*(p2ld-1)*(p2ru-1)%mod)
  ans %= mod
  bit.add(y+1,1)
print(ans)

"""

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 998244353
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	lus[i] = st.Get(pnt, n)
	lds[i] = i - lus[i]
	st.Add(pnt, 1)

st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	rus[i] = st.Get(pnt, n)
	rds[i] = n-1-i - rus[i]
	st.Add(pnt, 1)

pws = [1]
for _ in range(n-1):
	pws.append((pws[-1] * 2) % MOD)

ans = (2 * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans += ((pws[lu]-1) * (pws[rd]-1))
	ans += ((pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1))
	ans += ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1))
	ans %= MOD
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 998244353
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	lus[i] = st.Get(pnt, n)
	lds[i] = i - lus[i]
	st.Add(pnt, 1)

st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	rus[i] = st.Get(pnt, n)
	rds[i] = n-1-i - rus[i]
	st.Add(pnt, 1)

pws = [1]
for _ in range(n-1):
	pws.append((pws[-1] * 2) % MOD)

ans = (n * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans = ans + ((pws[lu]-1) * (pws[rd]-1)) % MOD
	ans = ans + ((pws[ld]-1) * (pws[ru]-1)) % MOD
	ans = ans + ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1)) % MOD
	ans = ans + ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1)) % MOD
	ans = ans + ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1)) % MOD
	ans = ans + ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1)) % MOD
	ans = ans + ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1)) % MOD
print(ans)

Submission status: Wrong Answer

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

def sub(a, b):
    return (a % mod + mod - b % mod) % mod

sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    b = 0
    cs = []
    while True:
        if y == 0:
            r = 1
            break
        elif y == 1:
            r = x % mod
            break
        elif y % 2 == 0 :
            y = y // 2
            cs.append(0)
        else:
            y = (y-1)//2
            cs.append(1)
    while True:
        if len(cs) == 0:
            break
        c = cs.pop()
        if c == 1:
            r = r ** 2 * x % mod
        else:
            r = r ** 2 % mod
    return r

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    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

def mm(a, b, c, d, n):
    return 0
    return sub(power(2, b+c) + power(2, c+d) + power(2, d+a) + power(2, a+b),
                power(2, a) + power(2, b) + power(2, c) + power(2, d))

n, = list(map(int, input().split()))
xs, ys = [], []
for _ in range(n):
    x, y = list(map(int, input().split()))
    xs.append(x)
    ys.append(y)

ini = sorted(list(range(n)), key=lambda x:xs[x])
for i, yi in enumerate(sorted(list(range(n)), key=lambda x:ys[x])):
    ys[yi] = i 
nys = [ys[i] for i in ini]

ss1 = SegTree([0] * n, n, 0, lambda x,y:x+y)
r = 0
for i, y in enumerate(nys):
    ss1.update(y, 1)
    d = ss1.query(0, y)
    c = i - d
    b = (n-1) - y - c
    a = (n-1) - b - c - d
    r = (r + mm(a, b, c, d, n)) % mod

print(sub((power(2, n) * n) % mod, (r+n)%mod))

Submission status: Wrong Answer

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

def sub(a, b):
    return (a % mod + mod - b % mod) % mod

sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    b = 0
    cs = []
    while True:
        if y == 0:
            r = 1
            break
        elif y == 1:
            r = x % mod
            break
        elif y % 2 == 0 :
            y = y // 2
            cs.append(0)
        else:
            y = (y-1)//2
            cs.append(1)
    while True:
        if len(cs) == 0:
            break
        c = cs.pop()
        if c == 1:
            r = r ** 2 * x % mod
        else:
            r = r ** 2 % mod
    return r

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    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

def mm(a, b, c, d, n):
    return 0
    return sub(power(2, b+c) + power(2, c+d) + power(2, d+a) + power(2, a+b),
                power(2, a) + power(2, b) + power(2, c) + power(2, d))

n, = list(map(int, input().split()))
ys = [list(map(int, input().split())) for _ in range(n)]
ys = sorted(ys)

for i, yi in enumerate(sorted(list(range(n)), key=lambda x:ys[x][1])):
    ys[yi] = i 

ss1 = SegTree([0] * n, n, 0, lambda x,y:x+y)
r = 0
for i, y in enumerate(ys):
    ss1.update(y, 1)
    d = ss1.query(0, y)
    c = i - d
    b = (n-1) - y - c
    a = (n-1) - b - c - d
    r = (r + mm(a, b, c, d, n)) % mod

print(sub((power(2, n) * n) % mod, (r+n)%mod))

Submission status: Wrong Answer

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

def sub(a, b):
    return (a % mod + mod - b % mod) % mod

sys.setrecursionlimit(pow(10, 8))

def power(x, y):
    b = 0
    cs = []
    while True:
        if y == 0:
            r = 1
            break
        elif y == 1:
            r = x % mod
            break
        elif y % 2 == 0 :
            y = y // 2
            cs.append(0)
        else:
            y = (y-1)//2
            cs.append(1)
    while True:
        if len(cs) == 0:
            break
        c = cs.pop()
        if c == 1:
            r = r ** 2 * x % mod
        else:
            r = r ** 2 % mod
    return r

class SegTree:
    def __init__(self, init_val, n, ide_ele, seg_func):
        self.segfunc = seg_func
        self.num = 2**(n-1).bit_length()
        self.ide_ele = ide_ele
        self.seg=[self.ide_ele]*2*self.num
        for i in range(n):
            self.seg[i+self.num-1]=init_val[i]    
        for i in range(self.num-2,-1,-1) :
            self.seg[i]=self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
        
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k+1:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1],self.seg[k*2+2])
        
    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

def mm(a, b, c, d, n):
    return 0
    return sub(power(2, b+c) + power(2, c+d) + power(2, d+a) + power(2, a+b),
                power(2, a) + power(2, b) + power(2, c) + power(2, d))

n, = list(map(int, input().split()))
ys = [list(map(int, input().split())) for _ in range(n)]
ys.sort()

for i, yi in enumerate(sorted(list(range(n)), key=lambda x:ys[x][1])):
    ys[yi] = i 

ss1 = SegTree([0] * n, n, 0, lambda x,y:x+y)
r = 0
for i, y in enumerate(ys):
    ss1.update(y, 1)
    d = ss1.query(0, y)
    c = i - d
    b = (n-1) - y - c
    a = (n-1) - b - c - d
    r = (r + mm(a, b, c, d, n)) % mod

print(sub((power(2, n) * n) % mod, (r+n)%mod))