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
import math
from operator import itemgetter, attrgetter

INF = 1 << 20
MOD = 998244353
# 座標
class Pair:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def main():
    N = int(sys.stdin.readline().strip())
    numbers = []
    for i in range(N):
        x, y = [int(i) for i in sys.stdin.readline().strip().split()]
        numbers.append(Pair(x, y))

    print("%d" % solve(N, numbers))

    
def solve(N, numbers):
    ans = 0
    

    # sort based Y
    numbers.sort(key=attrgetter("y"))
    for index in range(N):
        numbers[index].y = index

    # compressed numbers
    # sort based X
    numbers.sort(key=attrgetter("x"))
    for index in range(N):
        numbers[index].x = index
        
    
     
    # 各象限に存在する点の個数
    a = [0 for i in range(N)]
    b = [0 for i in range(N)]
    c = [0 for i in range(N)]
    d = [0 for i in range(N)]


    # 一番左の点から数えていく
    for rep in range(2):
        # treeを構築。これは、あるy座標以下の点の数がどれだけあるかを数えるもの
        bit = BIT(N)
        # 都合上、iは「それまでに追加した、今計算の対象となっている座標よりも左にある点の数」になる。
        for i in range(N):
            # 左から考えるので、その点より下にある点の数を代入
            a[i] = bit.sum(numbers[i].y)

            # これまでに追加した点の数マイナス、自分より下にある点の数(a)を引く
            b[i] = i - a[i]

            # 点を足す
            bit.update(numbers[i].y)
        numbers.reverse()
        a,b,c,d = c,d,a,b
        a.reverse()
        b.reverse()
        c.reverse()
        d.reverse()

    for i in range(N):
        ans += f([a[i], b[i], c[i], d[i]]) % MOD
    ans %= MOD
    return ans



def f(nums):
    res = 0
    
    o = [2**i-1 % MOD for i in nums]
    ox = [i+1 % MOD for i in o]
    res += (ox[0] * o[1] * o[2] * ox[3]) % MOD
    res += (o[0] * ox[1] * ox[2] * o[3]) % MOD
    res += (ox[0] * ox[1] * ox[2] * ox[3]) % MOD
    res -= (o[0] * o[1] * o[2] * o[3]) % MOD

    return res



# Binary Indexed Tree
# Reference http://hos.ac/slides/20140319_bit.pdf
class BIT:
    def __init__(self, size):
        self.bits = [0 for i in range(size+1)]
        self.size = size


    def update(self, index, value = 1):
        index += 1
        while index <= self.size:
            self.bits[index] += value
            index += index & (-1 * index)
    
    def sum(self, index):
        index += 1
        ans = 0
        while index > 0:
            ans += self.bits[index]
            index -= index & (-1 * index)
        return ans

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

import sys
import math
from operator import itemgetter, attrgetter

INF = 1 << 20
MOD = 998244353
# 座標
class Pair:
    def __init__(self, x, y):
        self.x = x
        self.y = y

def main():
    N = int(sys.stdin.readline().strip())
    numbers = []
    for i in range(N):
        x, y = [int(i) for i in sys.stdin.readline().strip().split()]
        numbers.append(Pair(x, y))

    print("%d" % solve(N, numbers))

    
def solve(N, numbers):
    ans = 0
    
    # compressed numbers
    # sort based X
    numbers.sort(key=attrgetter("x"))
    for index in range(N):
        numbers[index].x = index
        
    
    # sort based Y
    numbers.sort(key=attrgetter("y"))
    for index in range(N):
        numbers[index].y = index
     
    # 各象限に存在する点の個数
    a = [0 for i in range(N)]
    b = [0 for i in range(N)]
    c = [0 for i in range(N)]
    d = [0 for i in range(N)]

    # X座標の一番左から調べる
    numbers.sort(key=attrgetter("x"))

    # 一番左の点から数えていく
    for rep in range(2):
        # treeを構築。これは、あるy座標以下の点の数がどれだけあるかを数えるもの
        bit = BIT(N)
        # 都合上、iは「それまでに追加した、今計算の対象となっている座標よりも左にある点の数」になる。
        for i in range(N):
            # 左から考えるので、その点より下にある点の数を代入
            a[i] = bit.sum(numbers[i].y)

            # これまでに追加した点の数マイナス、自分より下にある点の数(a)を引く
            b[i] = i - a[i]

            # 点を足す
            bit.update(numbers[i].y)
        numbers.reverse()
        a,b,c,d = c,d,a,b
        a.reverse()
        b.reverse()
        c.reverse()
        d.reverse()

    for i in range(N):
        ans += f([a[i], b[i], c[i], d[i]]) % MOD
    ans %= MOD
    return ans



def f(nums):
    res = 0
    
    o = [2**i-1 % MOD for i in nums]
    ox = [i+1 % MOD for i in o]
    res += (ox[0] * o[1] * o[2] * ox[3]) % MOD
    res += (o[0] * ox[1] * ox[2] * o[3]) % MOD
    res += (ox[0] * ox[1] * ox[2] * ox[3]) % MOD
    res -= (o[0] * o[1] * o[2] * o[3]) % MOD

    return res



# Binary Indexed Tree
# Reference http://hos.ac/slides/20140319_bit.pdf
class BIT:
    def __init__(self, size):
        self.bits = [0 for i in range(size+1)]
        self.size = size


    def update(self, index, value = 1):
        index += 1
        while index <= self.size:
            self.bits[index] += value
            index += index & (-1 * index)
    
    def sum(self, index):
        index += 1
        ans = 0
        while index > 0:
            ans += self.bits[index]
            index -= index & (-1 * index)
        return ans

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
from operator import itemgetter
def solve():
    p_list = XY[:]

    # y座標の圧縮
    p_list = sorted(p_list, key=itemgetter(1))
    p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

    # xでソート
    p_list= sorted(p_list)

    a = [0] * N # 左下
    b = [0] * N# 左上
    c = [0] * N# 右下
    d = [0] * N# 右上

    # a,bを求める
    bit = Bit(N)
    for i, (x, y, r) in enumerate(p_list):
        tmp = bit.sum(r)
        a[i] = tmp
        b[i] = i-tmp
        bit.add(r, 1)

    # c,dを求める
    bit = Bit(N)
    for i, (x, y, r) in enumerate(reversed(p_list)):
        tmp = bit.sum(r)
        c[i] = tmp
        d[i] = i-tmp
        bit.add(r, 1)
    c = c[::-1]
    d = d[::-1]

    # ある点が四角に含まれる場合の総数を求めるメソッド
    power = [1] * N
    for i in range(1, N):
        power[i] = power[i-1] * 2 % 998244353

    ans = 0
    for _a,_b,_c,_d in zip(a,b,c,d):
        _a = power[_a] - 1
        _b = power[_b] - 1
        _c = power[_c] - 1
        _d = power[_d] - 1

        ret = (_a+1) * (_d+1) * _c * _b
        ret += (_b+1) * (_c+1) * _a * _d
        ret -= _a*_b*_c*_d
        ret += power[N-1]
        ans += ret % 998244353

    print(ans % 998244353)
    
solve()

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
p_list = XY[:]

# y座標の圧縮
from operator import itemgetter
p_list = sorted(p_list, key=itemgetter(1))
p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

# xでソート
p_list= sorted(p_list)

a = [0] * N # 左下
b = [0] * N# 左上
c = [0] * N# 右下
d = [0] * N# 右上

# a,bを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(p_list):
    tmp = bit.sum(r)
    a[i] = tmp
    b[i] = i-tmp
    bit.add(r, 1)

# c,dを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(reversed(p_list)):
    tmp = bit.sum(r)
    c[i] = tmp
    d[i] = i-tmp
    bit.add(r, 1)
c = c[::-1]
d = d[::-1]

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2 % 998244353
 
ans = 0
for _a,_b,_c,_d in zip(a,b,c,d):
    _a = power[_a] - 1
    _b = power[_b] - 1
    _c = power[_c] - 1
    _d = power[_d] - 1
    
    ret = (_a+1) * (_d+1) * _c * _b
    ret += (_b+1) * (_c+1) * _a * _d
    ret -= _a*_b*_c*_d
    ret += power[N-1]
    ans += ret % 998244353
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
p_list = XY[:]

# y座標の圧縮
from operator import itemgetter
p_list = sorted(p_list, key=itemgetter(1))
p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

# xでソート
p_list= sorted(p_list)

a = [0] * N # 左下
b = [0] * N# 左上
c = [0] * N# 右下
d = [0] * N# 右上

# a,bを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(p_list):
    tmp = bit.sum(r)
    a[i] = tmp
    b[i] = i-tmp
    bit.add(r, 1)

# c,dを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(reversed(p_list)):
    tmp = bit.sum(r)
    c[i] = tmp
    d[i] = i-tmp
    bit.add(r, 1)
c = c[::-1]
d = d[::-1]

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2 % 998244353
 
ans = 0
for i in range(N):
    _a = power[a[i]] - 1
    _b = power[b[i]] - 1
    _c = power[c[i]] - 1
    _d = power[d[i]] - 1
    
    ret = (_a+1) * (_d+1) * _c * _b
    ret += (_b+1) * (_c+1) * _a * _d
    ret -= _a*_b*_c*_d
    ret += power[N-1]
    ans += ret % 998244353
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
p_list = XY[:]

# y座標の圧縮
from operator import itemgetter
p_list = sorted(p_list, key=itemgetter(1))
p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

# xでソート
p_list= sorted(p_list)

a = [0] * N # 左下
b = [0] * N# 左上
c = [0] * N# 右下
d = [0] * N# 右上

# a,bを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(p_list):
    tmp = bit.sum(r)
    a[i] = tmp
    b[i] = i-tmp
    bit.add(r, 1)

# c,dを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(reversed(p_list)):
    tmp = bit.sum(r)
    c[i] = tmp
    d[i] = i-tmp
    bit.add(r, 1)
c = c[::-1]
d = d[::-1]

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2 % 998244353
def p_comb(a, b, c, d):
    a = power[a] - 1
    b = power[b] - 1
    c = power[c] - 1
    d = power[d] - 1
    
    ret = (a+1) * (d+1) * c * b
    ret += (b+1) * (c+1) * a * d
    ret -= a*b*c*d
    ret += power[N-1]
    return ret % 998244353
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i

#######################
# 開始
p_list = XY[:]

# y座標の圧縮
from operator import itemgetter
p_list = sorted(p_list, key=itemgetter(1))
p_list = [ (x, y, i+1) for i, (x, y) in enumerate(p_list)]

# xでソート
p_list= sorted(p_list)

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(p_list):
    tmp = bit.sum(r)
    a.append(tmp)
    b.append(i-tmp)
    bit.add(r, 1)

# c,dを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(reversed(p_list)):
    tmp = bit.sum(r)
    c.append(tmp)
    d.append(i-tmp)
    bit.add(r, 1)
c = c[::-1]
d = d[::-1]

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2 % 998244353
def p_comb(a, b, c, d):
    a = power[a] - 1
    b = power[b] - 1
    c = power[c] - 1
    d = power[d] - 1
    
    ret = (a+1) * (d+1) * c * b
    ret += (b+1) * (c+1) * a * d
    ret -= a*b*c*d
    ret += power[N-1]
    return ret % 998244353
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
#p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]
p_list = [ (p[0], p[1], i+1) for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list)

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(p_list):
    tmp = bit.sum(r)
    a.append(tmp)
    b.append(i-tmp)
    bit.add(r, 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(reversed(p_list)):
    tmp = bit.sum(r)
    c.append(tmp)
    d.append(i-tmp)
    bit.add(r, 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2 % 998244353
def p_comb(a, b, c, d):
    a = power[a] - 1
    b = power[b] - 1
    c = power[c] - 1
    d = power[d] - 1
    
    ret = (a+1) * (d+1) * c * b
    ret += (b+1) * (c+1) * a * d
 
    ret -= a*b*c*d
 
    ret += power[N-1]
    return ret % 998244353
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
#p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]
p_list = [ (p[0], p[1], i+1) for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list)

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(p_list):
    tmp = bit.sum(r)
    a.append(tmp)
    b.append(i-tmp)
    bit.add(r, 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(reversed(p_list)):
    tmp = bit.sum(r)
    c.append(tmp)
    d.append(i-tmp)
    bit.add(r, 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2 % 998244353
def p_comb(a, b, c, d):
    a = power[a] - 1
    b = power[b] - 1
    c = power[c] - 1
    d = power[d] - 1
    
    # 中心だけ
    #ret = 1
    # 一か所だけ(必ず中心点を入れる)
    #ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    #ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    #ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    #ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    #ret += a*b*c*d*2
    ret = (a+1) * (d+1) * c * b
    ret += (b+1) * (c+1) * a * d
 
    ret -= a*b*c*d
 
    ret += power[N-1]
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
#p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]
p_list = [ (p[0], p[1], i+1) for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list)

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(p_list):
    tmp = bit.sum(r)
    a.append(tmp)
    b.append(i-tmp)
    bit.add(r, 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(reversed(p_list)):
    tmp = bit.sum(r)
    c.append(tmp)
    d.append(i-tmp)
    bit.add(r, 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2
def p_comb(a, b, c, d):
    a = power[a] - 1
    b = power[b] - 1
    c = power[c] - 1
    d = power[d] - 1
    
    # 中心だけ
    #ret = 1
    # 一か所だけ(必ず中心点を入れる)
    #ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    #ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    #ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    #ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    #ret += a*b*c*d*2
    ret = (a+1) * (d+1) * c * b
    ret += (b+1) * (c+1) * a * d
 
    ret -= a*b*c*d
 
    ret += power[N-1]
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
#p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]
p_list = [ (p[0], p[1], i+1) for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list)

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(p_list):
    a.append(bit.sum(r))
    b.append(i-a[-1])
    bit.add(r, 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(reversed(p_list)):
    c.append(bit.sum(r))
    d.append(i-c[-1])
    bit.add(r, 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2
def p_comb(a, b, c, d):
    a = power[a] - 1
    b = power[b] - 1
    c = power[c] - 1
    d = power[d] - 1
    
    # 中心だけ
    #ret = 1
    # 一か所だけ(必ず中心点を入れる)
    #ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    #ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    #ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    #ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    #ret += a*b*c*d*2
    ret = (a+1) * (d+1) * c * b
    ret += (b+1) * (c+1) * a * d
 
    ret -= a*b*c*d
 
    ret += power[N-1]
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
#p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]
p_list = [ (p[0], p[1], i+1) for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list)

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(p_list):
    a.append(bit.sum(r))
    b.append(i-a[-1])
    bit.add(r, 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, (x, y, r) in enumerate(reversed(p_list)):
    c.append(bit.sum(r))
    d.append(i-c[-1])
    bit.add(r, 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2
def p_comb(a, b, c, d):
    a = power[a] - 1
    b = power[b] - 1
    c = power[c] - 1
    d = power[d] - 1
    
    # 中心だけ
    ret = 1
    # 一か所だけ(必ず中心点を入れる)
    ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    ret += a*b*c*d*2
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list, key=lambda x: x['x'])

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, p in enumerate(p_list):
    a.append(bit.sum(p['y_rank']))
    b.append(i-a[-1])
    bit.add(p['y_rank'], 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, p in enumerate(reversed(p_list)):
    c.append(bit.sum(p['y_rank']))
    d.append(i-c[-1])
    bit.add(p['y_rank'], 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
power = [1] * N
for i in range(1, N):
    power[i] = power[i-1] * 2
def p_comb(a, b, c, d):
    a = power[a] - 1
    b = power[b] - 1
    c = power[c] - 1
    d = power[d] - 1
    
    # 中心だけ
    ret = 1
    # 一か所だけ(必ず中心点を入れる)
    ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    ret += a*b*c*d*2
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list, key=lambda x: x['x'])

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, p in enumerate(p_list):
    a.append(bit.sum(p['y_rank']))
    b.append(i-a[-1])
    bit.add(p['y_rank'], 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, p in enumerate(reversed(p_list)):
    c.append(bit.sum(p['y_rank']))
    d.append(i-c[-1])
    bit.add(p['y_rank'], 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
def p_comb(a, b, c, d):
    a = (1<<a) - 1
    b = (1<<b) - 1
    c = (1<<c) - 1
    d = (1<<d) - 1
    
    # 中心だけ
    ret = 1
    # 一か所だけ(必ず中心点を入れる)
    ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    ret += a*b*c*d*2
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list, key=lambda x: x['x'])

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, p in enumerate(p_list):
    a.append(bit.sum(p['y_rank']))
    b.append(i-a[-1])
    bit.add(p['y_rank'], 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, p in enumerate(reversed(p_list)):
    c.append(bit.sum(p['y_rank']))
    d.append(i-c[-1])
    bit.add(p['y_rank'], 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
def p_comb(a, b, c, d):
    a = pow(2, a) - 1
    b = pow(2, b) - 1
    c = pow(2, c) - 1
    d = pow(2, d) - 1
    
    # 中心だけ
    ret = 1
    # 一か所だけ(必ず中心点を入れる)
    ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    ret += a*b*c*d*2
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)

Submission status: Time Limit Exceeded

Solution code:
N = int(input())

XY = []
for _ in range(N):
    x, y = map(int, input().split())
    XY.append((x, y))
    
# BITの定義
import math
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    # index 1からiの値の和を返す
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    # index iの値にxを加算する
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
#######################
# 開始
p_list = XY[:]

# y座標の圧縮
p_list = sorted(p_list, key=lambda x: x[1])
p_list = [ {'x': p[0], 'y': p[1], 'y_rank': i+1} for i, p in enumerate(p_list)]

# xでソート
p_list= sorted(p_list, key=lambda x: x['x'])

a = [] # 左下
b = [] # 左上
c = [] # 右下
d = [] # 右上

# a,bを求める
bit = Bit(N)
for i, p in enumerate(p_list):
    a.append(bit.sum(p['y_rank']))
    b.append(i-a[-1])
    bit.add(p['y_rank'], 1)

#print(p_list)
#print(a)
#print(b)

# c,dを求める
bit = Bit(N)
for i, p in enumerate(reversed(p_list)):
    c.append(bit.sum(p['y_rank']))
    d.append(i-c[-1])
    bit.add(p['y_rank'], 1)
c = c[::-1]
d = d[::-1]
#print(c)
#print(d)

# ある点が四角に含まれる場合の総数を求めるメソッド
def p_comb(a, b, c, d):
    a = 2**a - 1
    b = 2**b - 1
    c = 2**c - 1
    d = 2**d - 1
    
    # 中心だけ
    ret = 1
    # 一か所だけ(必ず中心点を入れる)
    ret += a + b + c + d
    # 対角線2か所(中心点はどちらでも)
    ret += (a*d + b*c)*2
    # 隣接2か所(必ず中心点を入れる)
    ret += (a*b+b*d+d*c+c*a)
    # 3か所(中心点はどちらでも)
    ret += (a*b*d+b*d*c+d*c*a+c*a*b)*2
    # 4か所
    ret += a*b*c*d*2
    
    
    return ret
 
ans = 0
for i in range(N):
    ans += p_comb(a[i], b[i], c[i], d[i])
    
print(ans % 998244353)