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

Solution code:
import sys
from operator import itemgetter

input = sys.stdin.readline
 
 
class BIT:
            
    def __init__(self, L):
        self.N = len(L)
        self.bit = [0]*self.N
        for i,l in enumerate(L):
            self.add(i,l)
 
    def add(self, a, w):
        x = a + 1
        for i in range(1000):
            self.bit[x-1] += w
            x += x & -x
            if x > self.N:
                break
 
    def sum(self, a):
        x = a+1
        ret = 0
        for i in range(1000):
            ret += self.bit[x-1]
            x -= x & -x
            if x <= 0:
                break        
        return ret
 
 
N = int(input())
point = [list(map(int,input().split())) for i in range(N)]
 
point.sort(key=itemgetter(1))
for i in range(len(point)):
    point[i][1] = i
 
mod = 998244353
 
ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod
 
pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod
 
point.sort(key=itemgetter(0))
 
bit = BIT([0]*len(point))
 
 
for i,(x,y) in enumerate(point):
    if y > 0:
        ld = bit.sum(y-1)
 
    else:
        ld = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    bit.add(y,1)
 
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    ans -= (((free2 - 1) * (free4 - 1)) % MOD) * (((free1 - 1) * (free3 - 1)) % MOD) % MOD
    ans += ((free1 * free3) % MOD) * (((free2 - 1) * (free4 - 1)) % MOD) % MOD
    ans += ((free2 * free4) % MOD) * ((free1 - 1) * (free3 - 1) % MOD) % MOD
    ans %= MOD
# target included, n >= 2 selected
ans += pow2[n-1] * n % MOD
print(ans % MOD)

Submission status: Time Limit Exceeded

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

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow2 = []
a = 1
for i in range(n+1):
    pow2.append(a)
    a *= 2
    a %= MOD

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow2[points_in_quad[0][i]]
    free2 = pow2[points_in_quad[1][i]]
    free3 = pow2[points_in_quad[2][i]]
    free4 = pow2[points_in_quad[3][i]]
    ans -= (((free2 - 1) * (free4 - 1)) % MOD) * (((free1 - 1) * (free3 - 1)) % MOD) % MOD
    ans += ((free1 * free3) % MOD) * (((free2 - 1) * (free4 - 1)) % MOD) % MOD
    ans += ((free2 * free4) % MOD) * ((free1 - 1) * (free3 - 1) % MOD) % MOD
    ans %= MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow_dict = dict()
for i in range(n):
    pow_dict[i] = pow(2, i, MOD)
ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow_dict[points_in_quad[0][i]]
    free2 = pow_dict[points_in_quad[1][i]]
    free3 = pow_dict[points_in_quad[2][i]]
    free4 = pow_dict[points_in_quad[3][i]]
    ans -= (((free2 - 1) * (free4 - 1)) % MOD) * (((free1 - 1) * (free3 - 1)) % MOD) % MOD
    ans += ((free1 * free3) % MOD) * (((free2 - 1) * (free4 - 1)) % MOD) % MOD
    ans += ((free2 * free4) % MOD) * ((free1 - 1) * (free3 - 1) % MOD) % MOD
    ans %= MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

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

MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

pow_dict = dict()
for i in range(n):
    pow_dict[i] = pow(2, i, MOD)
ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow_dict[points_in_quad[0][i]]
    free2 = pow_dict[points_in_quad[1][i]]
    free3 = pow_dict[points_in_quad[2][i]]
    free4 = pow_dict[points_in_quad[3][i]]
    # free1 = pow(2, points_in_quad[0][i], MOD)
    # free2 = pow(2, points_in_quad[1][i], MOD)
    # free3 = pow(2, points_in_quad[2][i], MOD)
    # free4 = pow(2, points_in_quad[3][i], MOD)
    ans -= (((free2 - 1) * (free4 - 1)) % MOD) * (((free1 - 1) * (free3 - 1)) % MOD) % MOD
    ans += ((free1 * free3) % MOD) * (((free2 - 1) * (free4 - 1)) % MOD) % MOD
    ans += ((free2 * free4) % MOD) * ((free1 - 1) * (free3 - 1) % MOD) % MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow(2, points_in_quad[0][i], MOD)
    free2 = pow(2, points_in_quad[1][i], MOD)
    free3 = pow(2, points_in_quad[2][i], MOD)
    free4 = pow(2, points_in_quad[3][i], MOD)
    ans -= (((free2 - 1) * (free4 - 1)) % MOD) * (((free1 - 1) * (free3 - 1)) % MOD) % MOD
    ans += ((free1 * free3) % MOD) * (((free2 - 1) * (free4 - 1)) % MOD) % MOD
    ans += ((free2 * free4) % MOD) * ((free1 - 1) * (free3 - 1) % MOD) % MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
MOD = 998244353
n = int(input())
xy = []
y_index = dict() 
for i in range(n):
    xy.append([int(item) for item in input().split()])
xy.sort(key=lambda x: x[1])
for i, (_, y) in enumerate(xy):
    y_index[y] = i
xy.sort()

cnt = [0] * (n+1)
def BIT_sum(i):
    ret = 0
    while i > 0:
        ret += cnt[i]
        i -= i & -i
    return ret

def BIT_add(i, x=1):
    while i <= n:
        cnt[i] += x
        i += i & -i
    return

points_in_quad = [[0] * n for _ in range(4)]
seen = 0
for i, (x, y) in enumerate(xy):
    index = y_index[y]
    points_in_quad[2][i] = BIT_sum(index + 1)
    points_in_quad[1][i] = seen - points_in_quad[2][i] 
    BIT_add(index + 1)
    seen += 1
seen = 0
cnt = [0] * (n+1)
for i, (x, y) in enumerate(xy[::-1]):
    index = y_index[y]
    points_in_quad[3][n - 1 - i] = BIT_sum(index + 1)
    points_in_quad[0][n - 1 - i] = seen - points_in_quad[3][n - 1 - i] 
    BIT_add(index + 1)
    seen += 1

ans = 0
for i in range(n):
    # target not included, n >= 2 selected
    free1 = pow(2, points_in_quad[0][i], MOD)
    free2 = pow(2, points_in_quad[1][i], MOD)
    free3 = pow(2, points_in_quad[2][i], MOD)
    free4 = pow(2, points_in_quad[3][i], MOD)
    ans -= (free2 - 1) * (free4 - 1) * (free1 - 1) * (free3 - 1) % MOD
    ans += free1 * free3 * (free2 - 1) * (free4 - 1) % MOD
    ans += free2 * free4 * (free1 - 1) * (free3 - 1) % MOD
    # target included, n >= 2 selected
    ans += pow(2, n-1, MOD)
    ans %= MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())
XY = [[int(x) for x in input().split()] for i in range(N)]
mod = 998244353
XY.sort() #Xについてソート
X, Y = zip(*XY)
Y_rank = {x:i for i, x in enumerate(sorted(Y), 1)}
BIT = [0] * (N+1)

def append_BIT(x):
    while x <= N:
        BIT[x] += 1
        x += x & (-x)

def sum_BIT(x):
    ret = 0
    while x:
        ret += BIT[x]
        x &= (x-1)
    return ret

pow2 = [1]
for i in range(N):
    pow2.append(pow2[-1] * 2 % mod)

ret = 0 
for i in range(N):
    y = Y_rank[Y[i]]
    L = i
    R = N-i-1
    D = y-1
    U = N-D-1
    LD = sum_BIT(y)
    append_BIT(y)
    LU = L - LD
    RU = U - LU
    RD = D - LD
    
    ret += (pow2[N]-1 - pow2[L] - pow2[R] - pow2[U] - pow2[D] + pow2[LD] + pow2[LU] + pow2[RU] + pow2[RD])
    ret %= mod

print(ret)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import bisect

MOD = 998244353  # type: int


def solve(N: int, P: "List[tuple]"):
    res = 0
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % MOD

    P.sort()
    for i, p in enumerate(P):
        left = sorted([t[1] for t in P[:i]])
        right = sorted([t[1] for t in P[i+1:]])
        # print(p, left, right)
        a3 = bisect.bisect(left, p[1])
        a2 = len(left) - a3
        a4 = bisect.bisect(right, p[1])
        a1 = len(right) - a4

        b1 = power[a1]
        b2 = power[a2]
        b3 = power[a3]
        b4 = power[a4]

        res += (b1 - 1) * (b3 - 1) * b2 * b4
        res += (b2 - 1) * (b4 - 1) * b1 * b3

        res -= (b1 - 1) * (b2 - 1) * (b3 - 1) * (b4 - 1)

        res += b1 * b2 * b3 * b4

        res %= MOD
    print(res)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    P = [()] * (N)  # type: "List[tuple]" 
    for i in range(N):
        x = int(next(tokens))
        y = int(next(tokens))
        P[i] = [x, y]
    solve(N, P)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

N=int(input())
POINT=[list(map(int,input().split())) for i in range(N)]
mod=998244353

PX=[p[0] for p in POINT]
PY=[p[1] for p in POINT]

compression_dict_x={a: ind for ind, a in enumerate(sorted(set(PX)))}
compression_dict_y={a: ind for ind, a in enumerate(sorted(set(PY)))}

for i in range(N):
    POINT[i]=[compression_dict_x[POINT[i][0]]+1,compression_dict_y[POINT[i][1]]+1]


P_Y=sorted(POINT,key=lambda x:x[1])

# BIT(BIT-indexed tree)

LEN=len(compression_dict_x)# 必要なら座標圧縮する

BIT=[0]*(LEN+1)# 1-indexedなtree

def update(v,w):# vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v))# 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v):# [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v))# 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS


ALL = pow(2,N,mod)-1

ANS= ALL*N%mod

for i in range(N):
    ANS = (ANS - (pow(2,i,mod) -1)*4)%mod

for i in range(N):
    x,y=P_Y[i]
    up=getvalue(x)

    ANS=(ANS+pow(2,up,mod)+pow(2,i-up,mod)-2)%mod

    update(x,1)

P_Y2=P_Y[::-1]
BIT=[0]*(LEN+1)

for i in range(N):
    x,y=P_Y2[i]
    down=getvalue(x)

    ANS=(ANS+pow(2,down,mod)+pow(2,i-down,mod)-2)%mod

    update(x,1)


print(ANS)

Submission status: Time Limit Exceeded

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

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = []
for i in range(n):
	x, y = map(int, input().split())
	dd.append((x, y, i))
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
d = [(x[0], x[1]) for x in d]
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	x = d[i][1]
	s = bitl.Sum(x)
	lu[i] = i - s
	ld[i] = s
	bitl.PointAdd(x, 1)

for i in range(n-1, -1, -1):
	x = d[i][1]
	s = bitr.Sum(x)
	ru[i] = n-1-i - s
	rd[i] = s
	bitr.PointAdd(x, 1)
#print(lu, ld, rd, ru, sep="\n")

ans = (n*pow(2, n, MOD) - n) % MOD
for i in range(n):
	ans -= pow(2, lu[i]+ld[i], MOD) + pow(2, ld[i]+rd[i], MOD) + pow(2, rd[i]+ru[i], MOD) + pow(2, ru[i]+lu[i], MOD)
	ans += pow(2, lu[i], MOD) + pow(2, ld[i], MOD) + pow(2, rd[i], MOD) + pow(2, ru[i], MOD)
	ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
d = [(x[0], x[1]) for x in d]
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	x = d[i][1]
	s = bitl.Sum(x)
	lu[i] = i - s
	ld[i] = s
	bitl.PointAdd(x, 1)

for i in range(n-1, -1, -1):
	x = d[i][1]
	s = bitr.Sum(x)
	ru[i] = n-1-i - s
	rd[i] = s
	bitr.PointAdd(x, 1)
#print(lu, ld, rd, ru, sep="\n")

ans = (n*pow(2, n, MOD) - n) % MOD
for i in range(n):
	ans -= pow(2, lu[i]+ld[i], MOD) + pow(2, ld[i]+rd[i], MOD) + pow(2, rd[i]+ru[i], MOD) + pow(2, ru[i]+lu[i], MOD)
	ans += pow(2, lu[i], MOD) + pow(2, ld[i], MOD) + pow(2, rd[i], MOD) + pow(2, ru[i], MOD)
	ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

def power(x):
	return pow(2, x, MOD)-1

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
d = [(x[0], x[1]) for x in d]
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	x = d[i][1]
	s = bitl.Sum(x)
	lu[i] = i - s
	ld[i] = s
	bitl.PointAdd(x, 1)

for i in range(n-1, -1, -1):
	x = d[i][1]
	s = bitr.Sum(x)
	ru[i] = n-1-i - s
	rd[i] = s
	bitr.PointAdd(x, 1)
#print(lu, ld, rd, ru, sep="\n")

ans = 0
for i in range(n):
	ans += pow(2, n, MOD)-1
	ans -= pow(2, lu[i]+ld[i], MOD) + pow(2, ld[i]+rd[i], MOD) + pow(2, rd[i]+ru[i], MOD) + pow(2, ru[i]+lu[i], MOD)
	ans += pow(2, lu[i], MOD) + pow(2, ld[i], MOD) + pow(2, rd[i], MOD) + pow(2, ru[i], MOD)
	ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

def power(x):
	return pow(2, x, MOD)-1

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
d = [(x[0], x[1]) for x in d]
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	lu[i] = i - bitl.Sum(d[i][1])
	ld[i] = i - lu[i]
	bitl.PointAdd(d[i][1], 1)

for i in range(n-1, -1, -1):
	ru[i] = n-1-i - bitr.Sum(d[i][1])
	rd[i] = n-1-i - ru[i]
	bitr.PointAdd(d[i][1], 1)
#print(lu, ld, rd, ru, sep="\n")

ans = 0
for i in range(n):
	ans += pow(2, n, MOD)-1
	ans -= pow(2, lu[i]+ld[i], MOD) + pow(2, ld[i]+rd[i], MOD) + pow(2, rd[i]+ru[i], MOD) + pow(2, ru[i]+lu[i], MOD)
	ans += pow(2, lu[i], MOD) + pow(2, ld[i], MOD) + pow(2, rd[i], MOD) + pow(2, ru[i], MOD)
	ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

def power(x):
	return pow(2, x, MOD)-1

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
d = [(x[0], x[1]) for x in d]
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	lu[i] = i - bitl.Sum(d[i][1])
	ld[i] = i - lu[i]
	bitl.PointAdd(d[i][1], 1)

for i in range(n-1, -1, -1):
	ru[i] = n-1-i - bitr.Sum(d[i][1])
	rd[i] = n-1-i - ru[i]
	bitr.PointAdd(d[i][1], 1)
#print(lu, ld, rd, ru, sep="\n")

ans = 0
for i in range(n):
	ans += power(n)
	ans -= power(lu[i]+ld[i]) + power(ld[i]+rd[i]) + power(rd[i]+ru[i]) + power(ru[i]+lu[i])
	ans += power(lu[i]) + power(ld[i]) + power(rd[i]) + power(ru[i])
	ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

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

def power(x):
	return pow(2, x, MOD)-1

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	lu[i] = i - bitl.Sum(d[i][1])
	ld[i] = i - lu[i]
	bitl.PointAdd(d[i][1], 1)

for i in range(n-1, -1, -1):
	ru[i] = n-1-i - bitr.Sum(d[i][1])
	rd[i] = n-1-i - ru[i]
	bitr.PointAdd(d[i][1], 1)
#print(lu, ld, rd, ru, sep="\n")

ans = 0
for i in range(n):
	ans += power(n)
	ans -= power(lu[i]+ld[i]) + power(ld[i]+rd[i]) + power(rd[i]+ru[i]) + power(ru[i]+lu[i])
	ans += power(lu[i]) + power(ld[i]) + power(rd[i]) + power(ru[i])
	ans %= MOD

print(ans)

Submission status: Time Limit Exceeded

Solution code:

class SegmentTree:
    def __init__(self, L, op, default_val):
        self.op = op
        self.default_val = default_val
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.default_val]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def get(self, l, r):
        res = self.default_val
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        n1 = n//2        
        #left
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        n1 = n//2        
        #right
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

N = int(input())
point = [list(map(int,input().split())) for i in range(N)]

point.sort(lambda x: x[1])
for i in range(len(point)):
    point[i][1] = i

mod = 998244353

ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod

pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod

point.sort(lambda x: x[0])

ST = SegmentTree([0]*len(point), lambda a,b:a+b, 0)


for i,(x,y) in enumerate(point):
    if y > 0:
        ld = ST.get(0,y-1)
        #ls = i//2
    else:
        ld = 0
    lu = i-ld
    rd = y - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    ST.add(point[i][1],1)

print(ans)

Submission status: Time Limit Exceeded

Solution code:


class SegmentTree:
    def __init__(self, L, op, default_val):
        self.op = op
        self.default_val = default_val
        self.sz = len(L)
        self.n = 1
        self.s = 1
        for i in range(1000):
            self.n *= 2
            self.s += 1
            if self.n >= self.sz:
                break
        self.node = [self.default_val]*(2*self.n-1)

        for i in range(self.sz):
            self.node[i+self.n-1] = L[i]

        for i in range(self.n-2,-1,-1):
            self.node[i] = self.op(self.node[i*2+1],self.node[i*2+2])
    
    def add(self, a, x):
        k = a+self.n-1
        self.node[k] += x
        for i in range(1000):
            k = (k-1)//2
            self.node[k] = self.op(self.node[2*k+1], self.node[2*k+2])
            if k <= 0:
                break
    
    def get(self, l, r):
        res = self.default_val
        n = self.n
        if self.sz <= r or 0 > l:
            print("ERROR: the indice are wrong.")
            return False

        for i in range(self.s):
            count = 2**i-1
            a = (r+1)//n
            b = (l-1)//n
            if a-b == 3:
                res = self.op(self.node[count+b+1],res)
                res = self.op(self.node[count+b+2],res)
                right = a*n
                left = (b+1)*n-1
                break
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n
                left = (b+1)*n-1
                break
            n = n//2

        n1 = n//2        
        #left
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (left+1)//n1
            b = (l-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                left = (b+1)*n1-1                
            n1 = n1//2

        n1 = n//2        
        #right
        for j in range(i+1,self.s):
            count = 2**j-1 
            a = (r+1)//n1
            b = (right-1)//n1
            if a-b == 2:
                res = self.op(self.node[count+b+1],res)
                right = a*n1                
            n1 = n1//2
        return res

N = int(input())
point = [list(map(int,input().split())) for i in range(N)]

point.sort(lambda x: x[1])
for i in range(len(point)):
    point[i][1] = i

mod = 998244353

ans = ((N-4)*pow(2,N,mod)+3*N+4)%mod

pow2 = []
a = 1
for i in range(N+1):
    pow2.append(a)
    a *= 2
    a %= mod

point.sort(lambda x: x[0])

ST = SegmentTree([0]*len(point), lambda a,b:a+b, 0)


for i in range(len(point)):
    if point[i][1] > 0:
        ld = ST.get(0,point[i][1]-1)
        #ls = i//2
    else:
        ld = 0
    lu = i-ld
    rd = point[i][1] - ld
    ru = N - i - 1 - rd    
    ans += pow2[lu]-1
    ans += pow2[ld]-1
    ans += pow2[ru]-1
    ans += pow2[rd]-1
    ans %= mod
    ST.add(point[i][1],1)

print(ans)