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:
mod=998244353
N=int(input())
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().split())
#f(T)を求めて各f(T)の値に対してその値を取りうるTの状態数を求める
#|f^-1(k)|を各1<=k<=Nで求める
#f(T)>0
#f^-1(1)={{1},{2},...,{N}}
#f^-1(2)=x座標またはy座標の順番が連続していればOK　高々2(N-1)
#f^-1(3)=xmin~xmaxとymin~ymaxの間に共通部分が存在しなければOK
#f(T)=kのときTの要素数はk以下
#dpとか?
#Tがf^-1(k)の元であるとき,p not in Tにおいて
#T cup {p}がf^-1(T)の元であるようなものはどれだけ存在するのか？
#どこまで削られるかを測定するとか？
#x座標かy座標が連続であるものに辺を結べばグラフになる
#でも木にはならない
#連結性をうまい感じに判断すればいけるのでは？
#サンプルの2つめは(1,4)と(1,2,4)の部分だけ余計に点が入ってしまう
#その点は3
#|T|=2のときはグラフにしたときの最短パスの長さになりそう
#(1,2,4)のときは、連結なのにうまくいってない
#1,4の2を経由しないルートが必要なのだろうか？
print((N*pow(2,N-1,mod))%mod)
#　　終
#お　わ　り
#制作・著作
#－－－－－
#Ｎ　Ｈ　Ｋ

Submission status: Wrong Answer

Solution code:
import sys
from operator import itemgetter

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

n = ni()

co = []
for i in range(n):
    co.append(na())

co.sort(key=itemgetter(1))
for i in range(n):
    co[i][1] = i

print(co)
ft = [0] * (n + 5)

co.sort(key=itemgetter(0), reverse=True)

ups = [0] * n
downs = [0] * n

def addfenwick(ft, i, v):
    if v == 0 or i < 0: return
    i += 1
    while i < len(ft):
        ft[i] += v
        i += i&-i

def sumfenwick(ft, i):
    s = 0
    i += 1
    while i > 0:
        s += ft[i]
        i -= i&-i
    return s

for i in range(n):
    c = co[i]
    downs[n-1-i] = sumfenwick(ft, c[1])
    ups[n-1-i] = i - downs[n-1-i]
    addfenwick(ft, c[1], 1)

ft = [0] * (n+5)
co = co[::-1]

ans = 0
mod = 998244353
for i in range(n):
    c = co[i]
    d = sumfenwick(ft, c[1])
    u = i - d

    # print(d, u, ups[i], downs[i])
    ans += (pow(2, d, mod)-1) * (pow(2, ups[i], mod)-1) * pow(2, u+downs[i], mod)
    ans += (pow(2, u, mod)-1) * (pow(2, downs[i], mod)-1) * pow(2, d+ups[i], mod)
    ans -= (pow(2, d, mod)-1) * (pow(2, ups[i], mod)-1) * (pow(2, downs[i], mod)-1) * (pow(2, u, mod)-1)
    ans += pow(2, n-1, mod)
    addfenwick(ft, c[1], 1)

ans %= mod
if ans < 0:
    ans += mod
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
S=sys.stdin.readlines()
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

N=int(S[0])
X=[list(map(int,S[i+1].split())) for i in range(N)]
X.sort()
for i in range(N):
  X[i][0]=i
D=dict()
Y=sorted([X[i][1] for i in range(N)])
for i in range(N):
  D[Y[i]]=i
for i in range(N):
  X[i][1]=D[X[i][1]]
B1,B2=[],[]
Binit(B1,N+1)
Binit(B2,N+1)
for i in range(N):
  Badd(B2,i+1,1)
mod=998244353
P=N*pow(2,N-1,mod)%mod
Z=[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,0,1,1],[1,0,0,1],[0,1,1,1],[0,1,1,0]]
A=0
for i in range(N):
  Badd(B2,X[i][1]+1,-1)
  V=[Bsum(B1,X[i][1]+1),Bsum(B2,X[i][1]+1)]
  for j in range(7):
    A=1
    if Z[j][0]:
      A=A*(pow(2,V[0],mod)-1)%mod
    if Z[j][1]:
      A=A*(pow(2,i-V[0],mod)-1)%mod
    if Z[j][2]:
      A=A*(pow(2,V[1],mod)-1)%mod
    if Z[j][3]:
      A=A*(pow(2,N-i-1-V[1],mod)-1)%mod
    P=(P+A)%mod
  Badd(B1,X[i][1]+1,1)
print(P)

Submission status: Time Limit Exceeded

Solution code:
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
X.sort()
for i in range(N):
  X[i][0]=i
D=dict()
Y=sorted([X[i][1] for i in range(N)])
for i in range(N):
  D[Y[i]]=i
for i in range(N):
  X[i][1]=D[X[i][1]]
B1,B2=[],[]
Binit(B1,N+1)
Binit(B2,N+1)
for i in range(N):
  Badd(B2,i+1,1)
mod=998244353
P=N*pow(2,N-1,mod)%mod
Z=[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,0,1,1],[1,0,0,1],[0,1,1,1],[0,1,1,0]]
A=0
for i in range(N):
  Badd(B2,X[i][1]+1,-1)
  V=[Bsum(B1,X[i][1]+1),Bsum(B2,X[i][1]+1)]
  for j in range(7):
    A=1
    if Z[j][0]:
      A=A*(pow(2,V[0],mod)-1)%mod
    if Z[j][1]:
      A=A*(pow(2,i-V[0],mod)-1)%mod
    if Z[j][2]:
      A=A*(pow(2,V[1],mod)-1)%mod
    if Z[j][3]:
      A=A*(pow(2,N-i-1-V[1],mod)-1)%mod
    P=(P+A)%mod
  Badd(B1,X[i][1]+1,1)
print(P)

Submission status: Time Limit Exceeded

Solution code:
def Binit(B,siz):
  while len(B)<siz+1:
    B.append(0)
  while len(B)>siz+1:
    del B[-1]
  for i in range(siz+1):
    B[i]=0
  B.append(siz)

def Badd(B,a,x):
  z=a
  while z<=B[-1]:
    B[z]+=x
    z+=(z&(-z))

def Bsum(B,a):
  r=0
  z=a
  while z>0:
    r+=B[z]
    z-=(z&(-z))
  return r

def Bssum(B,a,b):
  return Bsum(B,max(a,b))-Bsum(B,min(a,b)-1)

N=int(input())
X=[list(map(int,input().split())) for i in range(N)]
X.sort()
for i in range(N):
  X[i][0]=i
D=dict()
Y=sorted([X[i][1] for i in range(N)])
for i in range(N):
  D[Y[i]]=i
for i in range(N):
  X[i][1]=D[X[i][1]]
B1,B2=[],[]
Binit(B1,N+1)
Binit(B2,N+1)
for i in range(N):
  Badd(B2,i+1,1)
mod=998244353
P=N*pow(2,N-1,mod)%mod
Z=[[1,1,1,1],[1,1,1,0],[1,1,0,1],[1,0,1,1],[1,0,0,1],[0,1,1,1],[0,1,1,0]]
A=0
for i in range(N):
  Badd(B2,X[i][1]+1,-1)
  for j in range(7):
    A=1
    if Z[j][0]:
      A=A*(pow(2,Bsum(B1,X[i][1]+1),mod)-1)%mod
    if Z[j][1]:
      A=A*(pow(2,i-Bsum(B1,X[i][1]+1),mod)-1)%mod
    if Z[j][2]:
      A=A*(pow(2,Bsum(B2,X[i][1]+1),mod)-1)%mod
    if Z[j][3]:
      A=A*(pow(2,N-i-1-Bsum(B2,X[i][1]+1),mod)-1)%mod
    P=(P+A)%mod
  Badd(B1,X[i][1]+1,1)
print(P)

Submission status: Time Limit Exceeded

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 = list(zip(indx, indy))
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,(x,y) in enumerate(xy):
    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=itemgetter(1))
bit = [0]*(n+1)
for i,(x,y) in enumerate(xy):
    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 = xy[i]
    ans += pows[(n-1-i) - query(bit, x+1)]
    add(bit, x+1, 1)
    ans %= M
print(ans%M)

Submission status: Time Limit Exceeded

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)

    def power(a, n, mod):
        bi=str(format(n,"b")) #2進数
        res=1
        for i in range(len(bi)):
            res=(res*res) %mod
            if bi[i]=="1":
                res=(res*a) %mod
        return res

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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)

    def power(a, n, mod):
        bi=str(format(n,"b")) #2進数
        res=1
        for i in range(len(bi)):
            res=(res*res) %mod
            if bi[i]=="1":
                res=(res*a) %mod
        return res

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

n = int(input())
mod = 998244353
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)

def power(a, n, mod):
    bi=str(format(n,"b")) #2進数
    res=1
    for i in range(len(bi)):
        res=(res*res) %mod
        if bi[i]=="1":
            res=(res*a) %mod
    return res

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

Submission status: Time Limit Exceeded

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

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)
      
def main():
  N = int(input())
  xy = [tuple(map(int,input().split())) for _ in range(N)]

  # 平面走査のためのソート（高速化のため１次元にしてソート）
  # ソート後の復元+座標圧縮用の辞書作成
  # 座標圧縮: 小さい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)
  
if __name__=="__main__":
  main()

Submission status: Time Limit Exceeded

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
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 = (pow(2,n1,mod)-1)*(pow(2,n4,mod)-1)*pow(2,n2+n3,mod) %mod
  prod23 = (pow(2,n2,mod)-1)*(pow(2,n3,mod)-1)*pow(2,n1+n4,mod) %mod
  prod1234 = (pow(2,n1,mod)-1)*(pow(2,n4,mod)-1)*(pow(2,n2,mod)-1)*(pow(2,n3,mod)-1) %mod
  ans += pow(2,N-1,mod)+prod14+prod23-prod1234
  ans %= mod
  
print(ans)

Submission status: Time Limit Exceeded

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
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)

Submission status: Time Limit Exceeded

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, read().split()))
mod = 998244353

it = iter(xy)
xs = []
ys = []
for x,y,i in zip(it,it,range(n)):
    xs.append([x,i])
    ys.append([y,i])

xs.sort()
ys.sort()

point = [[-1,-1] for _ in range(n)]
for i,(x,ind) in enumerate(xs):
    point[ind][0] = i
for i,(y,ind) in enumerate(ys):
    point[ind][1] = i

point.sort()

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: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque, defaultdict
#deque(l), pop(), append(x), popleft(), appendleft(x)
#q.rotate(n)で → にn回ローテート
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate,combinations,permutations,product#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
from functools import reduce,lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率
from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("## ",*x,file=sys.stderr)
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def binr(x): return bin(x)[2:]
def bitcount(x): #xは64bit整数
    x= x - ((x >> 1) & 0x5555555555555555)
    x= (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333)
    x= (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f 
    x+= (x >> 8); x+= (x >> 16); x+= (x >> 32) 
    return x & 0x7f

class BIT():#添字は1から始まることに注意
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        self.tot=0
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        self.tot=0
        for i,x in enumerate(seq,1):
            self.tot+=x
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, val):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += val
            i += i & -i
        self.tot+=val
    
    def find(self,k):#k番目（最小は１）の要素,使うときは数列のサイズとbitのサイズを合わせること
        if k>self.tot: return self.size
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

def main():
    mod = 998244353
    #w.sort(key=itemgetter(1),reverse=True)  #二個目の要素で降順並び替え

    N = int(input())
    #N, K = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列
    xs=[]
    ys=[]
    for x,y in S:
        xs.append(x)
        ys.append(y)

    ixsort=argsort(xs)
    iysort=argsort(ys)
    s=[[0,0] for _ in range(N)]

    for i in range(N):
        s[ixsort[i]][0]=i
        s[iysort[i]][1]=i
    
    s.sort()

    xsmall=BIT(N)
    xlarge=BIT(N)
    for i in range(0,N):
        xlarge.add(s[i][1]+1,1)
    p2n=pow(2,N,mod)
    ans=0
    for i,(x,y) in enumerate(s):
        xlarge.add(y+1,-1)
        
        lxsy=xlarge.sum(y+1)
        lxly=xlarge.tot-lxsy
        sxsy=xsmall.sum(y+1)
        sxly=xsmall.tot-sxsy

        xsmall.add(y+1,1)
        
        t=1
        t+=pow(2,lxsy,mod)+pow(2,lxly,mod)+pow(2,sxly,mod)+pow(2,sxsy,mod)-4
        t%=mod
        t+=(pow(2,lxly+lxsy,mod)-pow(2,lxly,mod)-pow(2,lxsy,mod)+1)
        t+=(pow(2,lxly+sxly,mod)-pow(2,sxly,mod)-pow(2,lxly,mod)+1)
        t+=(pow(2,sxsy+lxsy,mod)-pow(2,sxsy,mod)-pow(2,lxsy,mod)+1)
        t+=(pow(2,sxsy+sxly,mod)-pow(2,sxsy,mod)-pow(2,sxly,mod)+1)
        t%=mod
        ans+=p2n-t
        ans%=mod
    print(ans)


        
        



if __name__ == "__main__":
    main()