Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Runtime Error):
N, K = map(int, input().split())
S = list(input())
bw = [0] * N
ind = 0
for i in range(N):
  bw[ind] += S[i] == S[i + 1]
  if S[i] != S[i + 1]:
    bw[ind] += 1
    ind += 1
ind = 0
res = 0
cumsumbw = [0] + [bw[0]] + [0] * (N - 1)
for i in range(1, N):
  cumsumbw[i + 1] = cumsumbw[i] + bw[i]
if N - 2 * K <= 0:
  print(N)
  exit(0)
for i in range(N - 2 * K):
  if S[i] == "1":
    res = max(res, cumsumbw[i + 2 * K + 1] - cumsumbw[i])
  else:
    res = max(res, cumsumbw[i + 2 * K] - cumsumbw[i])
print(res)

Fixed submission:
N, K = map(int, input().split())
S = list(input()) + [-1]
bw = [0] * N
ind = 0
for i in range(N):
  bw[ind] += S[i] == S[i + 1]
  if S[i] != S[i + 1]:
    bw[ind] += 1
    ind += 1
ind = 0
res = 0
cumsumbw = [0] + [bw[0]] + [0] * (N - 1)
for i in range(1, N):
  cumsumbw[i + 1] = cumsumbw[i] + bw[i]
if N - 2 * K <= 0:
  print(N)
  exit(0)
for i in range(N - 2 * K):
  if S[cumsumbw[i]] == "1":
    res = max(res, cumsumbw[i + 2 * K + 1] - cumsumbw[i])
  else:
    res = max(res, cumsumbw[i + 2 * K] - cumsumbw[i])
  #print(res)
print(res)
#print(bw)
#print(cumsumbw)

Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10 ** 6)
N, K = map(int, input().split())
S = list(map(int, list(input())))
def solve(l, k):
  if k == K:
    temp = 1
    thrbl = 0
    for i in range(l + 1, N):
      temp += 1
      if thrbl == 0 and S[i] == 1:
        thrbl = 1
      elif thrbl == 1 and S[i] == 0:
        temp -= 1
        break
    #print(l, temp, k)
    return temp
  temp = 0
  for i in range(l + 1, N):
    if S[i] == 0:
      temp = solve(i, k + 1)
      thrbl = 0
      for j in range(l + 1, i):
        temp += 1
        if thrbl == 0 and S[j] == 1:
          thrbl = 1
        elif thrbl == 1 and S[j] == 0:
          temp -= 1
          break
      if k == 1:
        thrbl = 0
        for j in range(l, -1, -1):
          temp += 1
          #print(j)
          if j == l:
            continue
          if thrbl == 0 and S[j] == 1:
            thrbl = 1
          elif thrbl == 1 and S[j] == 0:
            temp -= 1
            break
      #print(l, i, temp, k)
      return temp
res = 0
for i in range(N):
  if S[i] == 0:
    if i > 0 and S[i - 1] != 0:
      res = max(solve(i, 1), res)
    elif i == 0:
      res = max(solve(i, 1), res)
print(res) if res != 0 else print(N)

Fixed submission:
N, K = map(int, input().split())
S = list(input()) + [-1]
bw = [0] * N
ind = 0
for i in range(N):
  bw[ind] += S[i] == S[i + 1]
  if S[i] != S[i + 1]:
    bw[ind] += 1
    ind += 1
ind = 0
res = 0
cumsumbw = [0] + [bw[0]] + [0] * (N - 1)
for i in range(1, N):
  cumsumbw[i + 1] = cumsumbw[i] + bw[i]
if N - 2 * K <= 0:
  print(N)
  exit(0)
for i in range(N - 2 * K):
  if S[cumsumbw[i]] == "1":
    res = max(res, cumsumbw[i + 2 * K + 1] - cumsumbw[i])
  else:
    res = max(res, cumsumbw[i + 2 * K] - cumsumbw[i])
  #print(res)
print(res)
#print(bw)
#print(cumsumbw)
Buggy python submission (verdict: Runtime Error):
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
table = [[] for _ in range(N + 1)]
a = []
t = 0
mod = 10 ** 9 + 7
for i in range(N):
  x = int(input())
  if t != x:
    table[x].append(i)
    t = x
  a.append(x)
#print(table)
dp = [0] * N
dp[0] = 1
for i in range(N):
  j = br(table[a[i]], i)
  if j < len(table[a[i]]):
    dp[table[a[i]][j]] += dp[i]
    dp[table[a[i]][j]] %= mod
  if i + 1 < N: 
    dp[i + 1] += dp[i]
    dp[i + 1] %= mod
  #print(dp)
print(dp[-1])

Fixed submission:
import sys
from bisect import bisect_left as bl
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())
table = [[] for _ in range(2 * pow(10, 5) + 1)]
a = []
t = 0
mod = 10 ** 9 + 7
for i in range(N):
  x = int(input())
  if t != x:
    table[x].append(i)
    t = x
  a.append(x)
#print(table[4], table[3])
dp = [0] * N
dp[0] = 1
for i in range(N):
  j = br(table[a[i]], i)
  k = bl(table[a[i]], i)
  if j < len(table[a[i]]) and (table[a[i]][k] == i):
    dp[table[a[i]][j]] += dp[i]
    dp[table[a[i]][j]] %= mod
  if i + 1 < N: 
    dp[i + 1] += dp[i]
    dp[i + 1] %= mod
  #print(dp)
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
#xi以外の場所にコマを置く理由がない
#コマを置くというのは担当区間の分割
#xi x(i + 1)の間隔を無視するということ
#距離がでかいところから分割してやれば良い
N, M = map(int, input().split())
X = sorted(list(map(int, input().split())))
l = [X[i + 1] - X[i] for i in range(M - 1)]
l.sort()
for _ in range(N - 1):
  l.pop()
print(sum(l))

Fixed submission:
#xi以外の場所にコマを置く理由がない
#コマを置くというのは担当区間の分割
#xi x(i + 1)の間隔を無視するということ
#距離がでかいところから分割してやれば良い
N, M = map(int, input().split())
X = sorted(list(map(int, input().split())))
l = [X[i + 1] - X[i] for i in range(M - 1)]
l.sort()
for _ in range(N - 1):
  if len(l):
    l.pop()
print(sum(l))
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N, M = map(int, input().split())
a = [0] + list(map(int, input().split()))
edg = []
for i in range(1, M + 1):
  u, v, c = map(int, input().split())
  edg.append((u, v, c, i))

def check(x):
  e = dd(list)
  for u, v, c, i in edg:
    if c > x: continue
    e[u].append((v, c, i))
    e[v].append((u, c, i))

  vis = [0] * (N + 1)
  for i in range(1, N + 1):
    if vis[i]: continue
    s = [i]
    vs = 0
    es = 0
    evis = [0] * (M + 1)
    while len(s):
      p = s.pop()
      if vis[p]: continue
      vis[p] = 1
      vs += a[p]
      for q, c, k in e[p]:
        if evis[k]: continue
        es = max(es, c)
        evis[k] = 1
        s.append(q)
    if vs < es: return False
  return True

ok = 0
ng = sum(a) + 1
while ng - ok > 1:
  m = (ok + ng) // 2
  if check(m): ok = m
  else: ng = m

res = 0
for _, _, c, _ in edg: res += c > ok
print(res)

Fixed submission:
import sys
from collections import Counter
input = sys.stdin.readline
N, M = map(int, input().split())
a = list(map(int, input().split()))
e = []
ee = [[] for _ in range(N + 1)]
for _ in range(M):
  u, v, c = map(int, input().split())
  e.append((c, u, v))
  ee[u].append((v, c))
  ee[v].append((u, c))
e.sort()

table = [0] + a[: ]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1] * (n + 1)
    self.rnk = [0] * (n + 1)

  def Find_Root(self, x):
    if self.root[x] < 0:
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]

  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if x == y:
      return 
    elif self.rnk[x] > self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x] == self.rnk[y]:
        self.rnk[y] += 1

  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)

  def Count(self, x):
    return -self.root[self.Find_Root(x)]

uf = UnionFind(N)
edges = []
etable = [0] * (N + 1)
for i in range(M):
  c, u, v = e[i]
  if uf.isSameGroup(u, v):
    rt = uf.Find_Root(u)
    etable[rt] = max(etable[rt], c)
    if table[rt] >= etable[rt]: edges.append(i)

  else:
    ur = uf.Find_Root(u)
    vr = uf.Find_Root(v)
    uf.Unite(u, v)
    rt = uf.Find_Root(u)
    cmx = max(etable[ur], etable[vr], c)
    etable[rt] = cmx
    if table[ur] + table[vr] >= cmx: edges.append(i)

    table[rt] = table[ur] + table[vr]
edges.reverse()
vis = [0] * (N + 1)
evis = Counter()
res = M
#print(edges)
for i in edges:
  mx, s, _ = e[i]
  if vis[s]: continue
  sta = [s]
  vis[s] = 1
  while len(sta):
    x = sta.pop()
    for y, c in ee[x]:
      if c > mx: continue
      if evis[(min(x, y), max(x, y))]: continue
      evis[(min(x, y), max(x, y))] = 1
      res -= 1
      if vis[y]: continue
      sta.append(y)
      vis[y] = 1
  #print(vis, res, e[i])
print(res)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

s = [tuple(map(int, input().split())) for _ in range(N)]
s.sort(key = lambda x: -x[1])
table = [(-1, -1)] * (N + 1)
c = 0
for i in range(N):
  if table[s[i][0]] == (-1, -1):
    table[s[i][0]] = (i, s[i][1])
    c += 1

table.sort(key = lambda x: -x[1])
res = [0] * (M + 1)
vis = set()
p = M
for i in range(M): res[0] += s[i][1]
for x in range(1, c + 1):
  res[x] = res[x - 1] + pow(x, 2) - pow(x - 1, 2)
  if table[x - 1][0] >= M:
    res[x] += table[x - 1][1]
    p -= 1
    while p in vis:
      p -= 1
    res[x] -= s[p][1]
  vis.add(table[x - 1][0])
  #print(p)
print(max(res))

Fixed submission:
import sys
input = sys.stdin.readline
N, M = map(int, input().split())

s = [tuple(map(int, input().split())) for _ in range(N)]
s.sort(key = lambda x: -x[1])
table = [(-1, -1)] * (N + 1)
c = 0
for i in range(N):
  if table[s[i][0]] == (-1, -1):
    table[s[i][0]] = (i, s[i][1])
    c += 1

table.sort(key = lambda x: -x[1])
res = [0] * (min(c, M) + 1)
vis = set()
p = M
for i in range(M): res[0] += s[i][1]
for x in range(1, min(c, M) + 1):
  res[x] = res[x - 1] + pow(x, 2) - pow(x - 1, 2)
  if table[x - 1][0] >= M:
    res[x] += table[x - 1][1]
    p -= 1
    while p in vis:
      p -= 1
    res[x] -= s[p][1]
  vis.add(table[x - 1][0])
  #print(p)
print(max(res))
Buggy python submission (verdict: Runtime Error):
import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))
cs = [0] * (N + 1)
cs2 = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]
for i in range(N - 1, -1, -2): cs2[i + 1] = a[i]
for i in range(N): cs2[i + 1] += cs2[i]
res = [0] * (N + 1)
for i in range(N + 1):
  res[i] = cs[-1] - cs[min(N, i + N // 2)] + cs2[min(N, i * 2)]
#print(res, cs, cs2)
for _ in range(Q):
  x = int(input())
  i = bl(a, x)
  if abs(a[i - 1] - x) <= abs(a[i] - x): i -= 1
  y = max(0, i - N // 4)
  print(res[y])

Fixed submission:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))
a.reverse()
cs = [0] * (N + 1)
cs2 = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]
for i in range(0, N, 2): cs2[i + 1] = a[i]
for i in range(N): cs2[i + 1] += cs2[i]
#print(cs, cs2)
for _ in range(Q):
  x = int(input())
  ok = 0
  ng = -(-N // 2)
  while ng - ok > 1:
    m = (ok + ng) // 2
    if a[m] + a[m * 2] >= 2 * x: ok = m
    else: ng = m
  res = cs[ok + 1]
  #print(x)
  if (ok + 1) * 2 <= N: res += cs2[-1] - cs2[(ok + 1) * 2]
  print(res)

Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
d1 = []
d2 = []
for i in range(3):
  if a[i] < b[i]: d1.append((a[i], b[i]))
  if a[i] > b[i]: d2.append((b[i], a[i]))

dp = [0] * (N + 1)

for i in range(N, -1, -1):
  for t in d1:
    x = t[0]
    y = t[1]
    if i - x >= 0:
      dp[i - x] += y + dp[i]
for i in range(N + 1): dp[i] += i
res1 = max(dp)
#print(dp)
dp2 = [0] * (res1 + 1)
for i in range(res1, -1, -1):
  for t in d2:
    x = t[0]
    y = t[1]
    if i - x >= 0:
      dp2[i - x] += y
for i in range(res1 + 1): dp2[i] += i
print(max(dp2))

Fixed submission:
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
a = list(map(int, input().split()))
a.reverse()
cs = [0] * (N + 1)
cs2 = [0] * (N + 1)
for i in range(N): cs[i + 1] = cs[i] + a[i]
for i in range(0, N, 2): cs2[i + 1] = a[i]
for i in range(N): cs2[i + 1] += cs2[i]
#print(cs, cs2)
for _ in range(Q):
  x = int(input())
  ok = 0
  ng = -(-N // 2)
  while ng - ok > 1:
    m = (ok + ng) // 2
    if a[m] + a[m * 2] >= 2 * x: ok = m
    else: ng = m
  res = cs[ok + 1]
  #print(x)
  if (ok + 1) * 2 <= N: res += cs2[-1] - cs2[(ok + 1) * 2]
  print(res)
Buggy python submission (verdict: Runtime Error):
n,w=map(int,input().split())
b=[]
for _ in range(n):
  u,v=map(int,input().split())
  b.append((u, v))
dp=[[float("inf")]*(10**3*n+1) for _in range(n+1)]
dp[0][0]=0
res=0
for i in range(n):
  for j in range(10**3*n+1):
    if dp[i][j]!=float("inf"):
      dp[i+1][j]=min(dp[i+1][j],dp[i][j])
      dp[i+1][j+b[i][1]]=min(dp[i+1][j+b[i][1]],dp[i][j]+b[i][0])
for i in range(10**3*n+1):
  dp[-1][i]!=float("inf"):
    res=i
print(res)

Fixed submission:
import sys
input = sys.stdin.readline
N, W = map(int, input().split())
b = [tuple(map(int, input().split())) for _ in range(N)]
dp = [[float("inf")] * (pow(10, 5) + 1) for _ in range(N + 1)]
dp[0][0] = 0
for i in range(N):
  for j in range(pow(10, 5) + 1):
    if dp[i][j] != float("inf"):
      dp[i + 1][j + b[i][1]] = min(dp[i][j] + b[i][0], dp[i + 1][j + b[i][1]])
    dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
res = 0
for j in range(pow(10, 5) + 1):
  if dp[-1][j] <= W:
    res = max(res, j)
print(res)
Buggy python submission (verdict: Time Limit Exceeded):
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))

dp = [[0] * (N + 1) for _ in range(N)]
for l in range(N):
  for r in range(l, N + 1):
    if l == r: continue
    if (N - (r - l)) % 2: dp[l][r] = float("inf")
    else: dp[l][r] = -float("inf") 
for c in range(N + 1):
  for l in range(N - c + 1):
    if l == N: continue
    r = l + c
    t = (N - (r - l)) % 2
    if l - 1 >= 0:
      if t == 0:
        dp[l - 1][r] = min(dp[l - 1][r], dp[l][r] - a[l - 1])
      else:
        dp[l - 1][r] = max(dp[l - 1][r], dp[l][r] + a[l - 1])
    if r + 1 <= N:
      if t == 0:
        dp[l][r + 1] = min(dp[l][r + 1], dp[l][r] - a[r])
      else:
        dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a[r])
print(dp[0][N])

Fixed submission:
import sys
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
inf = 10 ** 14
dp = [[0] * (N + 1) for _ in range(N)]
for l in range(N):
  for r in range(l, N + 1):
    if l == r: continue
    if (N - (r - l)) % 2: dp[l][r] = inf
    else: dp[l][r] = -inf
for c in range(N + 1):
  for l in range(N - c + 1):
    if l == N: continue
    r = l + c
    t = (N - (r - l)) % 2
    if l - 1 >= 0:
      if t == 0:
        dp[l - 1][r] = min(dp[l - 1][r], dp[l][r] - a[l - 1])
      else:
        dp[l - 1][r] = max(dp[l - 1][r], dp[l][r] + a[l - 1])
    if r + 1 <= N:
      if t == 0:
        dp[l][r + 1] = min(dp[l][r + 1], dp[l][r] - a[r])
      else:
        dp[l][r + 1] = max(dp[l][r + 1], dp[l][r] + a[r])
print(dp[0][N])
Buggy python submission (verdict: Time Limit Exceeded):
import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
mod = 10 ** 9 + 7
dp = [0] * (1 << N)
dp[0] = 1
for t in range(N):
  for c in combi([x for x in range(N)], t):
    x = 0
    for i in c: x += 1 << i
    s = set(c)
    for i in range(N):
      if i in s: continue
      if a[t][i]:
        dp[x + (1 << i)] += dp[x]
        dp[x + (1 << i)] %= mod
print(dp[-1])

Fixed submission:
import sys
from itertools import combinations as combi
input = sys.stdin.readline
N = int(input())
a = [list(map(int, input().split())) for _ in range(N)]
mod = 10 ** 9 + 7
dp = [0] * (1 << N)
dp[0] = 1
for t in range(N):
  for c in combi([x for x in range(N)], t):
    x = 0
    table = [0] * N
    for i in c:
      x += 1 << i
      table[i] = 1
    for i in range(N):
      if table[i]: continue
      if a[t][i]:
        tt = 1 << i
        dp[x + tt] += dp[x]
        dp[x + tt] %= mod
print(dp[-1])
Buggy python submission (verdict: Runtime Error):
K = input()
D = int(input())
dp = [[0] * D for _ in range(len(K))]
mod = 10 ** 9 + 7
#桁DP
#0 ~ K[0] - 1までの数をトップとする場合
for i in range(int(K[0])):
  dp[0][i % D] += 1
#tightは上限付近の制御に使う
#K[0]をトップとする場合がtight
#tightは上限ギリギリを攻める
tight = int(K[0]) % D
for k in range(int(K[1])):
    dp[1][(tight + k) % D] += 1
tight = (tight + int(K[1])) % D
if len(K) > 1:
  for i in range(len(K) - 1):
    for j in range(D):
      for k in range(10):
        dp[i + 1][(j + k) % D] += dp[i][j]
        dp[i + 1][(j + k) % D] %= mod
  #Kを超えないようにしている
  for k in range(int(K[i + 1])):
    dp[i + 1][(tight + k) % D] += 1
  #上から(i + 1)桁まで見たもので、上限ギリギリのものの剰余
  tight = (tight + int(K[i + 1])) % D
#tightは最終的に上限の剰余に一致するので、0でないならその分を除く
print((dp[len(K) - 1][0] + (tight == 0) - 1) % mod)



Fixed submission:
K = input()
D = int(input())
dp = [[0] * D for _ in range(len(K))]
mod = 10 ** 9 + 7
#桁DP
#0 ~ K[0] - 1までの数をトップとする場合
for i in range(int(K[0])):
  dp[0][i % D] += 1
#tightは上限付近の制御に使う
#K[0]をトップとする場合がtight
#tightは上限ギリギリを攻める
tight = int(K[0]) % D
if len(K) > 1:
  for i in range(len(K) - 1):
    for j in range(D):
      for k in range(10):
        dp[i + 1][(j + k) % D] += dp[i][j]
        dp[i + 1][(j + k) % D] %= mod
    #Kを超えないようにしている
    for k in range(int(K[i + 1])):
      dp[i + 1][(tight + k) % D] += 1
    #上から(i + 1)桁まで見たもので、上限ギリギリのものの剰余
    tight = (tight + int(K[i + 1])) % D
#tightは最終的に上限の剰余に一致するので、0でないならその分を除く
print((dp[len(K) - 1][0] + (tight == 0) - 1) % mod)

Buggy python submission (verdict: Runtime Error):
K = input()
D = int(input())
dp = [[0] * D for _ in range(len(K))]
mod = 10 ** 9 + 7
for i in range(int(K[0])):
  dp[0][i % D] = 1
tight = int(K[i]) % D
if len(K) > 1:
  for i in range(len(K)):
    for j in range(D):
      for k in range(10):
        dp[i + 1][(j + k) % D] += dp[i][j]
        dp[i + 1][(j + k) % D] %= mod
  for k in range(int(K[i])):
    dp[i][(tight + k) % D] += 1
  tight = (tight + int(K[i])) % D
print((dp[len(K) - 1][0] + (tight == 0) - 1) % mod)

Fixed submission:
K = input()
D = int(input())
dp = [[0] * D for _ in range(len(K))]
mod = 10 ** 9 + 7
#桁DP
#0 ~ K[0] - 1までの数をトップとする場合
for i in range(int(K[0])):
  dp[0][i % D] += 1
#tightは上限付近の制御に使う
#K[0]をトップとする場合がtight
#tightは上限ギリギリを攻める
tight = int(K[0]) % D
if len(K) > 1:
  for i in range(len(K) - 1):
    for j in range(D):
      for k in range(10):
        dp[i + 1][(j + k) % D] += dp[i][j]
        dp[i + 1][(j + k) % D] %= mod
    #Kを超えないようにしている
    for k in range(int(K[i + 1])):
      dp[i + 1][(tight + k) % D] += 1
    #上から(i + 1)桁まで見たもので、上限ギリギリのものの剰余
    tight = (tight + int(K[i + 1])) % D
#tightは最終的に上限の剰余に一致するので、0でないならその分を除く
print((dp[len(K) - 1][0] + (tight == 0) - 1) % mod)
Buggy python submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
H, W, N = map(int, input().split())
table = [set() for _ in range(H + 1)]
qs = []
for _ in range(N):
  x, y = map(int, input().split())
  table[y - 1].add(x - 1)
  if x >= y: qs.append((x - 1, y - 1))
u, v = 0, 0
while u < W and (v < H):
  u += 1
  v += not (u in table[v + 1])
t = []
for i in range(len(qs)):
  if qs[i][1] <= v: t.append(qs[i])
qs = t
def check(x, y):
  u, v = 0, 0
  while u <= x:
    if (u + 1) in table[v]: return True
    u += 1
    if v < y: v += not (u in table[v + 1])
  return False

qs.sort(key = lambda x: x[0])
ng = -1
ok = len(qs)
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(qs[m][0], qs[m][1]): ok = m
  else: ng = m
#print(ok, ng, qs)
#print(table)
if ok == len(qs): print(W)
else:
  x, y = qs[ok]
  u, v = 0, 0
  res = 0
  stop = 0
  while True:
    if (u + 1) in table[v]:
      stop += 1
    else:
      u += 1
      stop = 0
    res += 1
    if stop > 1: break
    if v >= y or (u in table[v + 1]) or (stop > 0): stop += 1
    else:
      v += 1
      stop = 0
    if stop > 1: break
  print(res)

Fixed submission:
import sys
input = sys.stdin.readline
W, H, N = map(int, input().split())
table = [set() for _ in range(H + 1)]
qs = []
for _ in range(N):
  x, y = map(int, input().split())
  table[y - 1].add(x - 1)
  if x >= y: qs.append((x - 1, y - 1))
u, v = 0, 0
while u < W and (v < H):
  u += 1
  v += not (u in table[v + 1])
t = []
for i in range(len(qs)):
  if qs[i][1] <= v: t.append(qs[i])
qs = t
def check(x, y):
  u, v = 0, 0
  while u <= x:
    if (u + 1) in table[v]: return True
    u += 1
    if v < y: v += not (u in table[v + 1])
  return False

qs.sort(key = lambda x: x[0])
ng = -1
ok = len(qs)
while ok - ng > 1:
  m = (ok + ng) // 2
  if check(qs[m][0], qs[m][1]): ok = m
  else: ng = m
#print(ok, ng, qs)
#print(table)
if ok == len(qs): print(W)
else:
  x, y = qs[ok]
  u, v = 0, 0
  res = 0
  stop = 0
  while True:
    if (u + 1) in table[v]:
      stop += 1
    else:
      u += 1
      stop = 0
    res += 1
    if stop > 1: break
    if v >= y or (u in table[v + 1]) or (stop > 0): stop += 1
    else:
      v += 1
      stop = 0
    if stop > 1: break
  print(res)
Buggy python submission (verdict: Runtime Error):
if int(input) in [7, 5, 3]: print("YES")
else: print("NO")

Fixed submission:
print("YES" if int(input()) in [3, 5, 7] else "NO")
Buggy python submission (verdict: Runtime Error):
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())

def check(x):
  i = 2
  res = []
  while i * i <= x:
    while x % i == 0:
      x //= i
      res.append(i)
    i += 1
  if x > 1:
    res.append(x)
  return res
table = [0] * (N + 1)
for i in range(2, N + 1):
  for p in check(i):
    table[p] += 1
  #print(check(i))
t = []
#print(table)
for p in table:
  if p > 0: t.append(p)
t.sort()
#print(t)
k = len(t)
#print(k)
res = t[-1] >= 74
for i in range(k - 1):
  for j in range(i + 1, k):
    if t[i] + 1 >= 3 and (t[j] + 1 >= 25):
      res += 1
    if t[i] + 1 >= 5 and (t[j] + 1 >= 15):
      res += 1
    if t[i] + 1 >= 15 and (t[j] + 1 >= 5):
      res += 1
    if t[i] + 1 >= 25 and (t[j] + 1 >= 3):
      res += 1
#print(k, res)
for i in range(k - 2):
  for j in range(i + 1, k - 1):
    for l in range(j + 1, k):
      if (t[i] + 1) >= 3 and (t[j] + 1 >= 5) and (t[l] + 1 >= 5):
        res += 1
      if (t[i] + 1) >= 5 and (t[j] + 1 >= 3) and (t[l] + 1 >= 5):
        res += 1
      if (t[i] + 1) >= 5 and (t[j] + 1 >= 5) and (t[l] + 1 >= 3):
        res += 1
print(res)

Fixed submission:
import sys
from bisect import bisect_right as br
input = sys.stdin.readline
N = int(input())

def check(x):
  i = 2
  res = []
  while i * i <= x:
    while x % i == 0:
      x //= i
      res.append(i)
    i += 1
  if x > 1:
    res.append(x)
  return res
table = [0] * (N + 1)
for i in range(2, N + 1):
  for p in check(i):
    table[p] += 1
  #print(check(i))
t = [0]
#print(table)
for p in table:
  if p > 0: t.append(p)
t.sort()
#print(t)
k = len(t)
#print(k)
res = t[-1] >= 74
for i in range(k - 1):
  for j in range(i + 1, k):
    if t[i] + 1 >= 3 and (t[j] + 1 >= 25):
      res += 1
    if t[i] + 1 >= 5 and (t[j] + 1 >= 15):
      res += 1
    if t[i] + 1 >= 15 and (t[j] + 1 >= 5):
      res += 1
    if t[i] + 1 >= 25 and (t[j] + 1 >= 3):
      res += 1
#print(k, res)
for i in range(k - 2):
  for j in range(i + 1, k - 1):
    for l in range(j + 1, k):
      if (t[i] + 1) >= 3 and (t[j] + 1 >= 5) and (t[l] + 1 >= 5):
        res += 1
      if (t[i] + 1) >= 5 and (t[j] + 1 >= 3) and (t[l] + 1 >= 5):
        res += 1
      if (t[i] + 1) >= 5 and (t[j] + 1 >= 5) and (t[l] + 1 >= 3):
        res += 1
print(int(res))
Buggy python submission (verdict: Runtime Error):
import sys
from math import gcd
input = sys.stdin.readline
N, M = map(int, input().split())
S = list(input())[: -1]
T = list(input())[: -1]
ln = N * M // gcd(N, M)
res = ["a"] * ln
x = 0
y = 0
for i in range(ln):
  if i == x * ln // N and (i == y * ln // M):
    if S[x] != T[y]:
      print(-1)
      exit(0)
    res[i] = S[x]
    x += 1
    y += 1
  elif i == x * ln // N:
    res[i] = S[x]
    x += 1
  elif i == y * ln // M:
    res[i] = T[y]
    y += 1
print(len(res))

Fixed submission:
import sys
from math import gcd
input = sys.stdin.readline
N, M = map(int, input().split())
S = list(input())[: -1]
T = list(input())[: -1]
g = gcd(N, M)
ln = N * M // g
x = 0
y = 0
while x < N and (y < M):
  if S[x] != T[y]:
    print(-1)
    exit(0)
  x += ln // M
  y += ln // N
print(ln)
Buggy python submission (verdict: Runtime Error):
N = input()
for i in range(len(N)):
  if N[i] == "1":
    N[i] = "9"
  else:
    N[i] = "1"
print(N)

Fixed submission:
import sys
input = sys.stdin.readline
n = list(input())[: -1]
for i in range(len(n)):
  if n[i] == "1":
    n[i] = "9"
  elif n[i] == "9":
    n[i] = "1"
print("".join(n))