Problem p02951 (python)

Fixed submission:
test = False


def solve_a(test=False, a=0, b=0, c=0):
    if not test:
        a, b, c = map(int, input().split())
    d = max(c - (a - b), 0)
    print(d)


def solve_b(test=False, n=0):
    if not test:
        n = int(input())
    res = 0
    for i in range(1, n + 1):
        if len(str(i)) % 2 == 1:
            res += 1
    print(res)


def solve_c(test=False, n=0, h_list=[]):
    if not test:
        n = int(input())
        h_list = list(map(int, input().split()))
    res = 'Yes'
    new_h_list = [0] * n
    new_h_list[0] = h_list[0] - 1

    for i in range(1, n):
        # cannot down
        if h_list[i] == new_h_list[i - 1]:
            new_h_list[i] = h_list[i]
        elif h_list[i] < new_h_list[i - 1]:
            new_h_list[i] = h_list[i]
            res = 'No'
        else:
            new_h_list[i] = h_list[i] - 1
    print(res)


if __name__ == "__main__":
    if test:
        solve_a(test=True, a=6, b=4, c=3)
        solve_a(test=True, a=8, b=3, c=9)
        solve_a(test=True, a=12, b=3, c=7)
        solve_b(test=True, n=11)
        solve_b(test=True, n=136)
        solve_b(test=True, n=100000)
        solve_c(test=True, n=5, h_list=[1, 2, 1, 1, 3])
        solve_c(test=True, n=4, h_list=[1, 3, 2, 1])
        solve_c(test=True, n=5, h_list=[1, 2, 3, 4, 5])
        solve_c(test=True, n=1, h_list=[1000000000])
    else:
        solve_a()
        # solve_b()
        # solve_c()

Buggy submission (verdict: Runtime Error):
from heapq import heappush, heappop


class SegmentTree(object):

    def __init__(self, init_array, seg_func=min, seg_func_null=10 ** 9 + 7):

        self.seg_func = seg_func
        self.seg_func_null = seg_func_null
        self.n = 1
        while self.n < len(init_array):
            self.n *= 2
        self.dat = [0] * (2 * self.n - 1)
        for i in range(len(init_array)):
            self.dat[self.n - 1 + i] = init_array[i]
        for i in range(self.n - 2, -1, -1):
            self.dat[i] = self.seg_func(self.dat[2 * i + 1], self.dat[2 * i + 2])

    def update(self, k, a):
        k += self.n - 1
        self.dat[k] = a
        while k > 0:
            k = (k - 1) // 2
            self.dat[k] = self.seg_func(self.dat[k * 2 + 1], self.dat[k * 2 + 2])

    def query(self, p, q):
        # [p, q)
        if q <= p:
            return self.seg_func_null

        p += self.n - 1
        q += self.n - 2
        res = self.seg_func_null

        while q - p > 1:
            if p & 1 == 0:
                res = self.seg_func(res, self.dat[p])
            if q & 1 == 1:
                res = self.seg_func(res, self.dat[q])
                q -= 1
            p = p // 2
            q = (q-1) // 2
        if p == q:
            res = self.seg_func(res, self.dat[p])
        else:
            res = self.seg_func(self.seg_func(res, self.dat[p]), self.dat[q])

        return res


N = int(input())
hx = []
hy = []

for i in range(N):
    x, y = map(int, input().split())
    heappush(hx, (x, y))

y_list = [0] * N
for i in range(N):
    x, y = heappop(hx)
    y_list[i] = y
    heappush(hy, (y, i))

y_nor_list = [0] * N
for j in range(N):
    y, i = heappop(hy)
    y_nor_list[i] = j


def add(x, y):
    return x + y


sg_left = SegmentTree(init_array=[0]*N, seg_func=add, seg_func_null=0)
sg_right = SegmentTree(init_array=[0]*N, seg_func=add, seg_func_null=0)

left_lower = [0] * N
left_upper = [0] * N
right_lower = [0] * N
right_upper = [0] * N

for i in range(N):
    c = y_nor_list[i]
    left_lower[i] = sg_left.query(0, c)
    left_upper[i] = sg_left.query(c, N)
    sg_left.update(c, 1)

for i in range(N-1, -1, -1):
    c = y_nor_list[i]
    right_lower[i] = sg_right.query(0, c)
    right_upper[i] = sg_right.query(c, N)
    sg_right.update(c, 1)

# print(left_lower)
# print(left_upper)
# print(right_lower)
# print(right_upper)

LARGE = 998244353

res = 0
for i in range(N):
    r = pow(2, N, LARGE) - 1
    r -= pow(2, left_lower[i] + left_upper[i], LARGE) - 1
    r -= pow(2, right_lower[i] + right_upper[i], LARGE) - 1
    r -= pow(2, left_lower[i] + right_lower[i], LARGE) - 1
    r -= pow(2, left_upper[i] + right_upper[i], LARGE) - 1
    r += pow(2, left_lower[i], LARGE) - 1
    r += pow(2, left_upper[i], LARGE) - 1
    r += pow(2, right_lower[i], LARGE) - 1
    r += pow(2, right_upper[i], LARGE) - 1
    res += r

print(res % LARGE)