Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
read = sys.stdin.read

n, t = map(int, input().split())
m = map(int, read().split())
AB = sorted(zip(m, m))
A, B = zip(*AB)
dp = [[0]*t for _ in range(n+1)]
for i, a in enumerate(A[:-1]):
  for j in range(t):
    if j < a:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-a]+B[i], dp[i][j])
ans = 0
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
for i in range(n-1):
  ans = max(ans, dp[i+1][-1] + maxB[i+1])
print(ans)

Fixed submission:
n, t = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(n)])
A, B = zip(*ab)
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t+1):
    if A[i] >= j:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-A[i]] + B[i], dp[i][j])
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
ans = 0
for i in range(n-1):
  ans = max(ans, dp[i+1][t] + maxB[i+1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
read = sys.stdin.read

n, t = map(int, input().split())
m = map(int, read().split())
AB = sorted(zip(m, m))
A, B = zip(*AB)
dp = [[0]*t for _ in range(n+1)]
for i, a in enumerate(A[:-1]):
  for j in range(t):
    if j < a:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-a]+B[i], dp[i][j])
ans = 0
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
for i in range(n-1):
  ans = max(ans, dp[i+1][-1] + maxB[i+1])
print(ans)

Fixed submission:
n, t = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(n)])
A, B = zip(*ab)
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t+1):
    if A[i] >= j:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-A[i]] + B[i], dp[i][j])
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
ans = 0
for i in range(n-1):
  ans = max(ans, dp[i+1][t] + maxB[i+1])
print(ans)

Buggy python submission (verdict: Time Limit Exceeded):
n, t = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(n)])
A, B = zip(*ab)
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t+1):
    if A[i] >= j:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-A[i]] + B[i], dp[i][j])
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
ans = 0
for i in range(n-1):
  ans = max(ans, dp[i+1][t] + maxB[i+1])
print(ans)

Fixed submission:
n, t = map(int, input().split())
ab = sorted([ list(map(int, input().split())) for _ in range(n)])
A, B = zip(*ab)
dp = [[0]*(t+1) for _ in range(n+1)]
for i in range(n):
  for j in range(t+1):
    if A[i] >= j:
      dp[i+1][j] = dp[i][j]
    else:
      dp[i+1][j] = max(dp[i][j-A[i]] + B[i], dp[i][j])
maxB = [B[-1]]*n
for i in range(n-2, 0, -1):
  maxB[i] = max(B[i], maxB[i+1])
ans = 0
for i in range(n-1):
  ans = max(ans, dp[i+1][t] + maxB[i+1])
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
route_list = [[float("inf")]*n for _ in range(n)]
lrc = [ list(map(int, input().split())) for _ in range(m) ]
for l, r, c in lrc:
  for i in range(l, r):
    for j in range(i+1, r+1):
      route_list[i-1][j-1] = min(route_list[i-1][j-1], c)
      route_list[j-1][i-1] = min(route_list[j-1][i-1], c)
  
  
node_num = n

unsearched_nodes = list(range(node_num))
distance = [float("inf")] * node_num
previous_nodes = [-1] * node_num
distance[0] = 0 

def get_target_min_index(min_index, distance, unsearched_nodes):
    start = 0
    while True:
        index = distance.index(min_index, start)
        found = index in unsearched_nodes
        if found:
            return index
        else:
            start = index + 1
            
  
while(len(unsearched_nodes) != 0):
   
    posible_min_distance = float("inf")
    for node_index in unsearched_nodes: 
        if posible_min_distance > distance[node_index]: 
            posible_min_distance = distance[node_index]
    target_min_index = get_target_min_index(posible_min_distance, distance, unsearched_nodes) 
    unsearched_nodes.remove(target_min_index) 

    target_edge = route_list[target_min_index] 
    for index, route_dis in enumerate(target_edge):
        if route_dis != 0:
            if distance[index] > (distance[ target_min_index] + route_dis):
                distance[index] = distance[ target_min_index] + route_dis 
                previous_nodes[index] =  target_min_index 
                
if distance[node_num - 1] == float("inf"):
  print(-1)
else:
  print(distance[node_num - 1])

Fixed submission:
import sys
input = sys.stdin.readline

import heapq

def dijkstra(start, edge):
    n = len(edge)
    dist = [float("inf")]*n
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, v = heapq.heappop(que)
        if dist[v] < d:
            continue
        for nv, nd in edge[v]:
            if dist[nv] > d + nd:
                dist[nv] = d + nd
                heapq.heappush(que, (dist[nv], nv))
    return dist
  
n, m = map(int, input().split())
G = [[] for _ in range(n)]
for i in range(1, n):
  G[i].append((i-1, 0))
for _ in range(m):
  l, r, c = map(int, input().split())
  G[l-1].append((r-1, c))

D = dijkstra(0, G)
ans = D[n-1]
if ans == float("inf"):
  ans = -1
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import math
n = int(input())
m = int(math.sqrt(n))
while True:
  if n%m==0:
    print(n//m + m - 2)
    exit()
  m += 1  
    

Fixed submission:
n = int(input())
m = int(n**0.5)
c = float("inf")
for i in range(m, 0, -1):
  if n%i == 0:
    print(n//i + i - 2)
    exit()

Buggy python submission (verdict: Time Limit Exceeded):
import math
n = int(input())
m = int(math.sqrt(n))
while True:
  if n%m==0:
    print(n//m + m - 2)
    exit()
  m += 1  
    

Fixed submission:
n = int(input())
m = int(n**0.5)
c = float("inf")
for i in range(m, 0, -1):
  if n%i == 0:
    print(n//i + i - 2)
    exit()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

import numpy as np

def main():
  n, k = map(int, input().split())
  A = np.array(sorted(list(map(int, input().split()))))
  F = np.array(sorted(list(map(int, input().split())), reverse=True))
  def is_time(x):
    c = 0
    for i in range(n):
      c = np.maximum(A - x//F, 0).sum()
    if c <= k:
      return True
    return False
  ng = -1
  ok = max(A*F)
  while ok - ng > 1:
    m = (ng + ok)//2
    if is_time(m):
      ok = m
    else:
      ng = m
  print(ok)
  
if __name__ == "__main__":
  main()

Fixed submission:
n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())))[::-1]
def is_time(x):
  c = 0
  for i in range(n):
    c += max(0, A[i] - x//F[i])
  if c <= k:
    return True
  return False
ng = -1
ok = 0
for i in range(n):
  ok = max(ok, A[i]*F[i])
while ok - ng > 1:
  m = (ng + ok)//2
  if is_time(m):
    ok = m
  else:
    ng = m
print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

import numpy as np

n, k = map(int, input().split())
A = np.array(sorted(list(map(int, input().split()))))
F = np.array(sorted(list(map(int, input().split())), reverse=True))
def is_time(x):
  c = 0
  for i in range(n):
    c = np.maximum(A - x//F, 0).sum()
  if c <= k:
    return True
  return False
ng = -1
ok = max(A*F)
while ok - ng > 1:
  m = (ng + ok)//2
  if is_time(m):
    ok = m
  else:
    ng = m
print(ok)

Fixed submission:
n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())))[::-1]
def is_time(x):
  c = 0
  for i in range(n):
    c += max(0, A[i] - x//F[i])
  if c <= k:
    return True
  return False
ng = -1
ok = 0
for i in range(n):
  ok = max(ok, A[i]*F[i])
while ok - ng > 1:
  m = (ng + ok)//2
  if is_time(m):
    ok = m
  else:
    ng = m
print(ok)

Buggy python submission (verdict: Time Limit Exceeded):
n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())))[::-1]
def is_time(x):
  c = 0
  for i in range(n):
    c += max(0, A[i] - x//F[i])
  if c <= k:
    return True
  return False
ng = -1
ok = 0
for i in range(n):
  ok = max(ok, A[i]*F[i])
while ok - ng > 1:
  m = (ng + ok)//2
  if is_time(m):
    ok = m
  else:
    ng = m
print(ok)

Fixed submission:
n, k = map(int, input().split())
A = sorted(list(map(int, input().split())))
F = sorted(list(map(int, input().split())))[::-1]
def is_time(x):
  c = 0
  for i in range(n):
    c += max(0, A[i] - x//F[i])
  if c <= k:
    return True
  return False
ng = -1
ok = 0
for i in range(n):
  ok = max(ok, A[i]*F[i])
while ok - ng > 1:
  m = (ng + ok)//2
  if is_time(m):
    ok = m
  else:
    ng = m
print(ok)
Buggy python submission (verdict: Time Limit Exceeded):
n, m = map(int, input().split())
G = [[] for _ in range(n)]
ST = tuple(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(m))
for s, t in ST:
  G[s].append(t)
#枝(s, t)を塞いだ時にそれぞれそこからあと何手かかるかを求める
def f(s, t):
  dp = [0]*n #そこからあと何手かかるかの期待値
  for i in range(n-2, -1, -1):
    temp = 0
    for v in G[i]:
      temp += dp[v]
    if i==s:
      temp -= dp[t]
      dp[i] = temp/(len(G[i])-1) + 1
    else:
      dp[i] = temp/len(G[i]) + 1
  return dp
T = f(-1, -1)
ans = T[0]
for i in range(n-1):
  if len(G[i]) == 1:
    continue
  m = 0
  t = -1
  for v in G[i]:
    if T[v] > m:
      m = T[v]
      t = v
  temp = f(i, t)[0]
  ans = min(ans, temp)
print(ans)

Fixed submission:
n, m = map(int, input().split())
G = [[] for _ in range(n)]
ST = tuple(tuple(map(lambda x:int(x)-1, input().split())) for _ in range(m))
for s, t in ST:
  G[s].append(t)
#枝(s, t)を塞いだ時にそれぞれそこからあと何手かかるかを求める
def f(s, t):
  dp = [0]*n #そこからあと何手かかるかの期待値
  for i in range(n-2, -1, -1):
    temp = 0
    for v in G[i]:
      temp += dp[v]
    if i==s:
      temp -= dp[t]
      dp[i] = temp/(len(G[i])-1) + 1
    else:
      dp[i] = temp/len(G[i]) + 1
  return dp
T = f(-1, -1)
ans = T[0]
for i in range(n-1):
  if len(G[i]) == 1:
    continue
  m = 0
  t = -1
  for v in G[i]:
    if T[v] > m:
      m = T[v]
      t = v
  temp = f(i, t)[0]
  ans = min(ans, temp)
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
count = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    if l[i] >= l[j]*2:
      break
    else:
      for k in range(j+1, n):
        if l[i] < l[j]+l[k]:
          count += 1
        else:
          break
print(count)

Fixed submission:
import bisect

n = int(input())
l = sorted(list(map(int, input().split())))
count = 0
for b in range(n-2):
  for c in range(b+1, n-1):
    count += max(0, bisect.bisect_left(l, l[b]+l[c])-c-1)

print(count)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
l = list(map(int, input().split()))
l.sort(reverse=True)
count = 0
for i in range(n-2):
  for j in range(i+1, n-1):
    for k in range(j+1, n):
      if l[i] < l[j]+l[k]:
        count += 1
      else:
        break

print(count)

Fixed submission:
import bisect

n = int(input())
l = sorted(list(map(int, input().split())))
count = 0
for b in range(n-2):
  for c in range(b+1, n-1):
    count += max(0, bisect.bisect_left(l, l[b]+l[c])-c-1)

print(count)
Buggy python submission (verdict: Runtime Error):
from itertools import groupby

s = input()
k = int(input())
a, b = [], []
count1, count2 = 0, 0

for key, group in groupby(s):
  a.append(list(group))

if len(a) == 1:
  print(len(s*k) // 2)
  
else:
  for key, group in groupby(s*2):
    b.append(list(group))  

  for i in a:
    count1 += len(i) // 2

  for i in b:
    count2 += len(i) // 2

  c = count2 - count1

  print(count1 + c*(k-1))

Fixed submission:
from itertools import groupby

s = input()
k = int(input())
a, b = [], []
count1, count2 = 0, 0

for key, group in groupby(s):
  a.append(list(group))

if len(a) == 1:
  if len(s)%2==1 and k%2==1:
    print(len(s)//2 + len(s)*(k-1)//2 )
  else:
    print(len(s)*k//2)
else:
  for key, group in groupby(s*2):
    b.append(list(group))  

  for i in a:
    count1 += len(i) // 2

  for i in b:
    count2 += len(i) // 2

  c = count2 - count1

  print(count1 + c*(k-1))

Buggy python submission (verdict: Runtime Error):
from itertools import groupby

s = input()
k = int(input())
a, b = [], []
count1, count2 = 0, 0

for key, group in groupby(s):
  a.append(list(group))

if len(a) == 1:
  print(len(s*k) // 2)
  
else:
  for key, group in groupby(s*2):
    b.append(list(group))  

  for i in a:
    count1 += len(i) // 2

  for i in b:
    count2 += len(i) // 2

  c = count2 - count1

  print(count1 + c*(k-1))

Fixed submission:
from itertools import groupby

s = input()
k = int(input())
a, b = [], []
count1, count2 = 0, 0

for key, group in groupby(s):
  a.append(list(group))

if len(a) == 1:
  if len(s)%2==1 and k%2==1:
    print(len(s)//2 + len(s)*(k-1)//2 )
  else:
    print(len(s)*k//2)
else:
  for key, group in groupby(s*2):
    b.append(list(group))  

  for i in a:
    count1 += len(i) // 2

  for i in b:
    count2 += len(i) // 2

  c = count2 - count1

  print(count1 + c*(k-1))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())
order = list(map(int, input().split()))
result = []
for j in range(n):
  for k in range(n):
    if j+1 == order[k]:
      result.append(k+1)
print(*result)

Fixed submission:
n = int(input())
a = []
for i in sorted(enumerate(list(map(int, input().split())), start=1), key = lambda x :x[1]):
	a.append(i[0])
print(*a)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
order = list(map(int, input().split()))
result = []
for j in range(n):
  for k in range(n):
    if j+1 == order[k]:
      result.append(k+1)
print(*result)

Fixed submission:
n = int(input())
a = []
for i in sorted(enumerate(list(map(int, input().split())), start=1), key = lambda x :x[1]):
	a.append(i[0])
print(*a)

Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
order = list(map(int, input().split()))
result = []
for j in range(n):
  for k in range(n):
    if j+1 == order[k]:
      result.append(k+1)
print(*result)

Fixed submission:
n = int(input())
a = []
for i in sorted(enumerate(list(map(int, input().split())), start=1), key = lambda x :x[1]):
	a.append(i[0])
print(*a)
Buggy python submission (verdict: Time Limit Exceeded):
goods, ticket = map(int, input().split())
list = list(map(int, input().split()))
sum = 0
for i in range(ticket):
  list.sort(reverse=True)
  list[0] //= 2
for j in list:
  sum += j
print(sum)

Fixed submission:
import heapq

n, m = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for i in range(m):
    tmp_min = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-tmp_min//2))  # 計算誤差の関係で-1を2回かけてます
print(-sum(a))
Buggy python submission (verdict: Runtime Error):
print(int(input() ** 3))

Fixed submission:
print(int(input()) ** 3)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

n = int(input())
S = sorted(map(int, input().split()), reverse=True)
L = [S[0]]
used = [False]*(1<<n)
used[0] = True
for i in range(n):
  T = []
  for l in L:
    for j, s in enumerate(S):
      if used[j]:
        continue
      if l > s:
        T.append(s)
        used[j] = True
        break
    else:
      print("No")
      exit()
  L += T
print("Yes")

Fixed submission:
import sys
input = sys.stdin.readline

n = int(input())
S = sorted(map(int, input().split()), reverse=True)
L = [S[0]]
used = [False]*(1<<n)
used[0] = True
for i in range(n):
  L.sort(reverse=True)
  idx = 0
  for j, s in enumerate(S):
    if used[j]:
      continue
    if L[idx] > s:
      L.append(s)
      used[j] = True
      idx += 1
      if idx == 1<<i:
        break
  else:
    print("No")
    exit()
print("Yes")
Buggy python submission (verdict: Runtime Error):
def Kleene(a, k):
  if k==1:
    count = 0
    for i in range(len(a)-1):
      for j in range(i+1, len(a)):
        if a[i] > a[j]:
          count += 1
    return count
  
  else:
    a.sort()
    l = [ i for i in range(len(a)) ]
    for i in range(1, len(a)):
      if a[i] == a[i-1]:
        l[i] = l[i-1]
    count = sum(l) * (k-1)
    return ( Kleene(a, 1) + Kleene(a, k-1) + count ) % 1000000007

n, k = map(int, input().split())
a = list(map(int, input().split()))
print(Kleene(a, k))

Fixed submission:
n, k = map(int, input().split())
a = list(map(int, input().split()))
t, s = 0, 0

for i in range(n-1):
  for j in range(i+1, n):
    if a[i] > a[j]:
      t += 1
      
a.sort()
l = [ i for i in range(n) ]
for i in range(1, n):
  if a[i] == a[i-1]:
    l[i] = l[i-1]
s = sum(l)
    
print((k*t%1000000007 + s*k*(k-1)//2%1000000007)%1000000007)
Buggy python submission (verdict: Runtime Error):
c=0;a=input();for i in input().split():
  c+=1/int(i)
print(1/c)

Fixed submission:
c=0
a=input()
for i in input().split():
  c+=1/int(i)
print(1/c)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

p = int(input())
A = tuple(map(int, input().split()))
B = [0]*p
U = p-1
MOD = p
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

for j, a in enumerate(A):
  if a:
    B[0] += 1
    temp = 1
    for i in range(p-1, -1, -1):
      B[i] -= (-1)**(i%2) * temp * comb(p-1, i)
      temp *= j
      temp %= p
      B[i] %= p
print(*B)

Fixed submission:
import sys
input = sys.stdin.readline

p = int(input())
A = tuple(map(int, input().split()))
B = [0]*p
U = p-1
MOD = p
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

for j, a in enumerate(A):
  if a:
    B[0] += 1
    temp = 1
    for i in range(p-1, -1, -1):
      B[i] -= (-1)**(i%2) * temp * comb(p-1, i)
      temp *= j
      temp %= p
      B[i] %= p
print(*B)

Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

p = int(input())
A = tuple(map(int, input().split()))
B = [0]*p
U = p-1
MOD = p
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

for j, a in enumerate(A):
  if a:
    B[0] += 1
    for i in range(p):
      B[i] -= (-1)**(p-1-i) * pow(j, p-1-i, p) * comb(p-1, i)
      B[i] %= p
print(*B)

Fixed submission:
import sys
input = sys.stdin.readline

p = int(input())
A = tuple(map(int, input().split()))
B = [0]*p
U = p-1
MOD = p
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

for j, a in enumerate(A):
  if a:
    B[0] += 1
    temp = 1
    for i in range(p-1, -1, -1):
      B[i] -= (-1)**(i%2) * temp * comb(p-1, i)
      temp *= j
      temp %= p
      B[i] %= p
print(*B)
Buggy python submission (verdict: Time Limit Exceeded):
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)

Fixed submission:
import sys
input = sys.stdin.readline
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)
ans = pow(2, n-1, mod) * n % mod
for a, b, c, d in zip(A, B, C, D):
  a = pow(2, a, mod)
  b = pow(2, b, mod)
  c = pow(2, c, mod)
  d = pow(2, d, mod)
  temp = (a-1)*b*c*(d-1) + a*(b-1)*(c-1)*d - (a-1)*(b-1)*(c-1)*(d-1)
  ans += temp
  ans %= mod
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline

U = 4*10**6
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

n, m = map(int, input().split())
ans = 0
for k in range(m%2, min(n, m)+1, 2):
  ans += comb((3*m-k)//2+n-1, n-1) * comb(n, k)
  ans %= MOD
cnt = 0
for k in range(m):
  cnt += comb(k+n-2, n-2)
  cnt %= MOD
cnt *= n
cnt %= MOD
ans -= cnt
ans %= MOD
print(ans)

Fixed submission:
import sys
input = sys.stdin.readline

U = 4*10**6
MOD = 998244353
 
fact = [1]*(U+1)
fact_inv = [1]*(U+1)
 
for i in range(1,U+1):
    fact[i] = (fact[i-1]*i)%MOD
fact_inv[U] = pow(fact[U], MOD-2, MOD)
 
for i in range(U,0,-1):
    fact_inv[i-1] = (fact_inv[i]*i)%MOD
 
def perm(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[n-k]
    z %= MOD
    return z

def comb(n, k):
    if k < 0 or k > n:
        return 0
    z = fact[n]
    z *= fact_inv[k]
    z %= MOD
    z *= fact_inv[n-k]
    z %= MOD
    return z

n, m = map(int, input().split())
ans = 0
for k in range(m%2, min(n, m)+1, 2):
  ans += comb((3*m-k)//2+n-1, n-1) * comb(n, k)
  ans %= MOD
cnt = 0
for k in range(m):
  cnt += comb(k+n-2, n-2)
  cnt %= MOD
cnt *= n
cnt %= MOD
ans -= cnt
ans %= MOD
print(ans)
Buggy python submission (verdict: Time Limit Exceeded):
n = int(input())
A = [int(input()) for _ in range(n)]
L = []
for i in A:
  for j in range(len(L)):
    if L[j] < i:
      L[j] = i
      break
  else:
    L.append(i)
print(len(L))

Fixed submission:
import bisect
n = int(input())
A = [int(input()) for _ in range(n)]
L = [-1]*n
count = 0
for i in A:
  t = bisect.bisect_left(L, i) - 1
  if L[t] == -1:
    count += 1
  L[t] = i
print(count)