Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
N, M = map(int, input().split())
gate = [ list(map(int, input().split())) for i in range(M) ]

nopass = 0
for i in range(1, N+1):
	for j in gate:
		if j[0] > i or j[1] < i:
			nopass += 1
			break
print(N - nopass)

Fixed submission:
N, M = map(int, input().split())
gate = [ list(map(int, input().split())) for i in range(M) ]

max_L = max([ i[0] for i in gate])
min_R = min([ i[1] for i in gate])
ans = 0
if max_L > min_R:
	ans = 0
else:
	ans = min_R - max_L + 1
print(ans)
Buggy python submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(1000)

class UnionFind:
	def __init__(self, n=1):
		self.par = [ i for i in range(n)]
		self.size = [0] * n

#   木の根を求める
	def root(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]


#   x を含むグループと y を含むグループをマージする
	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		self.par[x] = y

if __name__ == '__main__':
	N, M = map(int, input().split())
	uf = UnionFind(N)
	for i in range(M):
		X, Y, Z = map(int, input().split())
		uf.merge(X-1, Y-1)
	
	ans = [ uf.root(i) for i in range(N)]

	print(len(set(ans)))

Fixed submission:
import sys
sys.setrecursionlimit(1000000)

class UnionFind:
	def __init__(self, n=1):
		self.par = [ i for i in range(n)]
		self.size = [0] * n

#   木の根を求める
	def root(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]


#   x を含むグループと y を含むグループをマージする
	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		self.par[x] = y

if __name__ == '__main__':
	N, M = map(int, input().split())
	uf = UnionFind(N)
	for i in range(M):
		X, Y, Z = map(int, input().split())
		uf.merge(X-1, Y-1)
	
	ans = [ uf.root(i) for i in range(N)]

	print(len(set(ans)))

Buggy python submission (verdict: Runtime Error):
class UnionFind:
	def __init__(self, n=1):
		self.par = [ i for i in range(n)]
		self.size = [0] * n

#   木の根を求める
	def root(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]


#   x を含むグループと y を含むグループをマージする
	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		self.par[x] = y

if __name__ == '__main__':
	N, M = map(int, input().split())
	uf = UnionFind(N)
	for i in range(M):
		X, Y, Z = map(int, input().split())
		uf.merge(X-1, Y-1)
#		print(uf.par)
	
	ans = [ uf.root(i) for i in range(N)]

	print(len(set(ans)))

Fixed submission:
import sys
sys.setrecursionlimit(1000000)

class UnionFind:
	def __init__(self, n=1):
		self.par = [ i for i in range(n)]
		self.size = [0] * n

#   木の根を求める
	def root(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.root(self.par[x])
			return self.par[x]


#   x を含むグループと y を含むグループをマージする
	def merge(self, x, y):
		x = self.root(x)
		y = self.root(y)
		if x == y:
			return
		self.par[x] = y

if __name__ == '__main__':
	N, M = map(int, input().split())
	uf = UnionFind(N)
	for i in range(M):
		X, Y, Z = map(int, input().split())
		uf.merge(X-1, Y-1)
	
	ans = [ uf.root(i) for i in range(N)]

	print(len(set(ans)))
Buggy python submission (verdict: Runtime Error):
b = int(input())

if b == "A":
	print("T")
elif b == "C":
	print("G")
elif b == "G":
	print("C")
else:
	print("A")


Fixed submission:
b = input()

if b == "A":
	print("T")
elif b == "C":
	print("G")
elif b == "G":
	print("C")
else:
	print("A")
Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
li = [list(map(int, input().split())) for i in range(Q)]
cnt = [0]*N
for i in range(N):
	cnt[i] = S[0:i+1].count("AC")
for i in range(Q):
	print(cnt[li[i][1]-1] - cnt[li[i][0]-1])


Fixed submission:
N, Q = map(int, input().split())
S = input()
cnt = [0]*(N)
for i in range(1,N):
	cnt[i] = cnt[i-1] + (1 if S[i-1:i+1] == "AC" else 0)
for i in range(Q):
	l, r = map(int, input().split())
	print(cnt[r-1] - cnt[l-1])

Buggy python submission (verdict: Time Limit Exceeded):
N, Q = map(int, input().split())
S = input()
li = [list(map(int, input().split())) for i in range(Q)]
cnt = [0]*N
for i in range(N):
	cnt[i] = S[0:i+1].count("AC")
for i in range(Q):
	print(S[li[i][0]-1:li[i][1]].count("AC"))


Fixed submission:
N, Q = map(int, input().split())
S = input()
cnt = [0]*(N)
for i in range(1,N):
	cnt[i] = cnt[i-1] + (1 if S[i-1:i+1] == "AC" else 0)
for i in range(Q):
	l, r = map(int, input().split())
	print(cnt[r-1] - cnt[l-1])
Buggy python submission (verdict: Runtime Error):
N = int(input())
lis = [list(map(int, input().split())) for i in range(N)]

dp = [[0,0,0] for i in range(N)]
dp[0] = lis[0]

for idx, val in enumerate(lis[1:], start=1):
	a = val[0] + max([dp[idx-1][i] for i in range(3) if 0 != i ])
	b = val[1] + max([dp[idx-1][i] for i in range(3) if 1 != i ])
	c = val[2] + max([dp[idx-1][i] for i in range(3) if 2 != i ])
	dp[idx] = [a,b,c]
print(max(dp[-1][0]))

Fixed submission:
N = int(input())
lis = [list(map(int, input().split())) for i in range(N)]

dp = [[0,0,0] for i in range(N)]
dp[0] = lis[0]

for idx, val in enumerate(lis[1:], start=1):
	a = val[0] + max([dp[idx-1][i] for i in range(3) if 0 != i ])
	b = val[1] + max([dp[idx-1][i] for i in range(3) if 1 != i ])
	c = val[2] + max([dp[idx-1][i] for i in range(3) if 2 != i ])
	dp[idx] = [a,b,c]
print(max(dp[-1]))
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction


def get_max(a, b, theta):
    kari = b * math.tan(math.radians(90 - theta))
    if kari > a:
        S = (a * b) - (a * (a * math.tan(math.radians(theta))) / 2)
    else:
        S = (kari * b) / 2
    max_water = S * a
    return max_water




def main():
    a, b, x = map(int, input().split())
    left, right = 0, 90

    for i in range(100000):
        half = (left + right) / 2
        max_water = get_max(a, b, half)
        if max_water >=x:
            left = half
        else:
            right = half

    print(left)





if __name__ == '__main__':
    main()



Fixed submission:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools
import queue
from collections import deque
from fractions import Fraction


def get_max(a, b, theta):
    kari = b * math.tan(math.radians(90 - theta))
    if kari > a:
        S = (a * b) - (a * (a * math.tan(math.radians(theta))) / 2)
    else:
        S = (kari * b) / 2
    max_water = S * a
    return max_water




def main():
    a, b, x = map(int, input().split())
    left, right = 0, 90

    for i in range(10000):
        half = (left + right) / 2
        max_water = get_max(a, b, half)
        if max_water >=x:
            left = half
        else:
            right = half

    print(left)





if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque



def main():
    num = int(input())
    s = list(input())

    for i in range(1, num)[::-1]:
        if s[i] == s[i - 1]:
            s.pop(i)

    print(len(s))






if __name__ == '__main__':
    main()


Fixed submission:
from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools

import queue
from collections import deque



def main():
    num = int(input())
    s = list(input())
    ans = 0
    for i in range(1, num)[::-1]:
        if s[i] == s[i - 1]:
            ans += 1

    print(len(s) - ans)






if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):

def main():
    s = int(input())

    saidai = 10 ** 9

    for i in range(1, int(s ** 0.5) + 1):
        teihenn = i
        if s % teihenn != 0:
            continue
        takasa = s // teihenn

        if teihenn <= saidai and takasa <= saidai:
            break

    print(0, 0, teihenn, 0, 0, takasa)




if __name__ == '__main__':
    main()

Fixed submission:

import math

def main():
    s = int(input())
    max_num = 10 ** 9
    y = math.ceil(s / (max_num))
    x = y * max_num - s

    print(0, 0, max_num, 1, x, y)




if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict

def main():
    left, right = map(int, input().split())
    mod = 2019

    # a, b = left, left + 1
    # c, d = right, right - 1
    aaa = defaultdict(int)
    for i in range(left, min(right + 1, left + 5000)):
        aaa[i % mod] += 1

    score_sorted = list(sorted(aaa.items(), key=lambda x: x[1]))

    # print(score_sorted)

    if score_sorted[0][1] >= 2:
        a, b = score_sorted[0][0]
    else:
        a, b, = score_sorted[0][0], score_sorted[1][0]

    print((a * b)% mod)






if __name__ == '__main__':
    main()


Fixed submission:
from collections import defaultdict

def main():
    left, right = map(int, input().split())
    mod = 2019

    aaa = defaultdict(int)
    for i in range(left, min(right + 1, left + 5000)):
        aaa[i % mod] += 1

    score_sorted = list(sorted(aaa.items(), key=lambda x: x[0]))

    # print(score_sorted)

    ans = 2019
    for i in range(len(score_sorted)):
        if score_sorted[i][1] >= 2:
            ans = min(ans, (score_sorted[i][0] * score_sorted[i][0]) % mod)
        for j in range(i + 1, len(score_sorted)):
            ans = min(ans, (score_sorted[i][0] * score_sorted[j][0]) % mod)

    print(ans)







if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):
from collections import defaultdict
import math

from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

def main():
    num, k_bleu = map(int, input().split())
    red_num = num - k_bleu

    # ans = 0
    mod = 10 ** 9 + 7
    for i in range(k_bleu):
        kaisuu = i + 1
        ans = combinations_count(red_num + 1, kaisuu) * combinations_count(k_bleu - 1, kaisuu - 1)
        ans %= mod
        print(ans)








if __name__ == '__main__':
    main()

Fixed submission:
from collections import defaultdict
import math

from math import factorial
# 組み合わせ
def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

def main():
    num, k_bleu = map(int, input().split())
    red_num = num - k_bleu

    # ans = 0
    mod = 10 ** 9 + 7
    for i in range(k_bleu):
        kaisuu = i + 1
        if i >= min(k_bleu, red_num + 1):
            print(0)
        else:
            ans = combinations_count(red_num + 1, kaisuu) * combinations_count(k_bleu - 1, kaisuu - 1)
            ans %= mod
            print(ans)








if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
while 1:
  pass

Fixed submission:

from collections import defaultdict

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

def main():
    data = list(input())

    if data[0] == data[1] or data[1] == data[2] or data[2] == data[3]:
        print('Bad')
    else:
        print('Good')


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import bisect

def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]
    ans_list = [[0 for i in range(width)] for j in range(high)]

    for i in range(high):
        for j in range(width):
            if data[i][j] == '.':
                ans_list[i][j] = ans_list[i][j - 1] + 1
        for j in range(width - 1)[::-1]:
            if data[i][j] == '.':
                ans_list[i][j] = max(ans_list[i][j], ans_list[i][j + 1])

    # for i in range(high):
    #     print(ans_list[i])
    # print('---')

    ans_list2 = [[0 for i in range(width)] for j in range(high)]

    for j in range(width):
        for i in range(high):
            if data[i][j] == '.':
                ans_list2[i][j] = ans_list2[i - 1][j] + 1
        for i in range(high - 1)[::-1]:
            if data[i][j] == '.':
                ans_list2[i][j] = max(ans_list2[i][j], ans_list2[i + 1][j])

    ans = 0

    for i in range(high):
        for j in range(width):
            kari = ans_list[i][j] + ans_list2[i][j] - 1
            ans = max(ans, kari)

    print(ans)



if __name__ == '__main__':
    main()

Fixed submission:
import bisect

def main():
    high, width = map(int, input().split())
    data = [list(input()) for i in range(high)]
    ans_list = [[0 for i in range(width)] for j in range(high)]

    for i in range(high):
        for j in range(width):
            if data[i][j] == '.':
                ans_list[i][j] = ans_list[i][j - 1] + 1
        for j in range(width - 1)[::-1]:
            if data[i][j] == '.':
                ans_list[i][j] = max(ans_list[i][j], ans_list[i][j + 1])

    # for i in range(high):
    #     print(ans_list[i])
    # print('---')

    ans_list2 = [[0 for i in range(width)] for j in range(high)]

    for j in range(width):
        for i in range(high):
            if data[i][j] == '.':
                ans_list2[i][j] = ans_list2[i - 1][j] + 1
        for i in range(high - 1)[::-1]:
            if data[i][j] == '.':
                ans_list2[i][j] = max(ans_list2[i][j], ans_list2[i + 1][j])

    ans = 0

    for i in range(high):
        for j in range(width):
            kari = ans_list[i][j] + ans_list2[i][j] - 1
            ans = max(ans, kari)

    print(ans)



if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):

def main():
    data = input()
    ans = 0
    while 'ABC' in data:
        ans += data.count('ABC')
        data = data.replace('ABC', 'BCA')

    print(ans)

if __name__ == '__main__':
    main()

Fixed submission:

def main():
    data = input()
    data = data.replace('BC', 'D')
    count_a = 0
    ans = 0
    for i in range(len(data)):
        now_str = data[i]
        if now_str == 'A':
            count_a += 1
        elif now_str == 'D':
            ans += count_a
        else:
            count_a = 0

    print(ans)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Runtime Error):

import math


def kari():
    a = list(map(int, input().split()))
    b = map(int, input().split())


def start_process(num, data):
    kouyakusuu1, kouyakusuu2, kouyakusuu3 = math.gcd(data[0], data[1]), max(data[0], data[1]), min(data[0], data[1])
    # print(kouyakusuu2, kouyakusuu3)

    for i in range(2, num):
        if i == 2:
            a = math.gcd(data[i], kouyakusuu2)
            b = math.gcd(data[i], kouyakusuu3)
            kari1 = max(a, b)
            kari2 = kouyakusuu1

            kari3 = math.gcd(data[i], kouyakusuu1)
        else:
            kari1 = math.gcd(data[i], kouyakusuu2)
            kari2 = kouyakusuu1

            kari3 = math.gcd(data[i], kouyakusuu1)



        kouyakusuu1 = kari3
        kouyakusuu2 = max(kari1, kari2)



    print(max(kouyakusuu1, kouyakusuu2))

# def start_process(num, data):
#     for i in range(num)

def main():
    num = int(input())
    data = list(map(int, input().split()))
    start_process(num, data)



if __name__ == '__main__':
    main()


Fixed submission:
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def kari():
    a = list(map(int, input().split()))
    b = map(int, input().split())


def start_process(num, data):
    kouyakusuu1, kouyakusuu2, kouyakusuu3 = gcd(data[0], data[1]), max(data[0], data[1]), min(data[0], data[1])
    # print(kouyakusuu2, kouyakusuu3)

    for i in range(2, num):
        if i == 2:
            a = gcd(data[i], kouyakusuu2)
            b = gcd(data[i], kouyakusuu3)
            kari1 = max(a, b)
            kari2 = kouyakusuu1

            kari3 = gcd(data[i], kouyakusuu1)
        else:
            kari1 = gcd(data[i], kouyakusuu2)
            kari2 = kouyakusuu1

            kari3 = gcd(data[i], kouyakusuu1)



        kouyakusuu1 = kari3
        kouyakusuu2 = max(kari1, kari2)



    print(max(kouyakusuu1, kouyakusuu2))

# def start_process(num, data):
#     for i in range(num)

def main():
    num = int(input())
    data = list(map(int, input().split()))
    start_process(num, data)



if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):

import itertools

def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    p = itertools.product(A, B)
    data = [i + j for i, j in p]
    data.sort(reverse=True)
    data = data[:min(len(data), K)]

    p = itertools.product(data, C)
    data = [i + j for i, j in p]
    data.sort(reverse=True)
    # data = data[:K]

    for i in range(K):
        print(data[i])

if __name__ == '__main__':
    main()


Fixed submission:


def main():
    X, Y, Z, K = list(map(int, input().split()))

    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)


    data = []
    for i in range(X):
        for j in range(Y):
            if i * j > K:
                break
            for k in range(Z):
                if i * j * k > K:
                    break
                data.append(A[i] + B[j] + C[k])

    data.sort(reverse=True)

    for i in range(K):
        print(data[i])

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Time Limit Exceeded):

import itertools

def main():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    p = itertools.product(A, B, C)
    data = [i + j + k for i, j, k in p]
    data.sort(reverse=True)

    for i in range(K):
        print(data[i])

if __name__ == '__main__':
    main()


Fixed submission:


def main():
    X, Y, Z, K = list(map(int, input().split()))

    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    A.sort(reverse=True)
    B.sort(reverse=True)
    C.sort(reverse=True)


    data = []
    for i in range(X):
        for j in range(Y):
            if i * j > K:
                break
            for k in range(Z):
                if i * j * k > K:
                    break
                data.append(A[i] + B[j] + C[k])

    data.sort(reverse=True)

    for i in range(K):
        print(data[i])

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):



def start_process(length, q_num, char):
    for i in range(q_num):
        start_ind, fin_ind = map(int, input().split())
        now_str = char[start_ind - 1:fin_ind]
        print(now_str.count('AC'))



def main():
    length, q_num = map(int, input().split())
    char = input()
    start_process(length, q_num, char)

if __name__ == '__main__':
    main()


Fixed submission:



def start_process(length, q_num, char):
    data = [0 for i in range(length + 1)]
    char = list(char)

    for i in range(1, length):
        if char[i] == 'C' and char[i - 1] == 'A':
            data[i] = data[i - 1] + 1
        else:
            data[i] = data[i - 1]

    for i in range(q_num):
        start_ind, fin_ind = map(int, input().split())
        print(data[fin_ind - 1] - data[start_ind - 1])


def main():
    length, q_num = map(int, input().split())
    char = input()
    start_process(length, q_num, char)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import itertools
import functools
import operator

def main():
    num = int(input())
    data = list(input())

    count_dic = defaultdict(int)

    for i in range(num):
        count_dic[data[i]] += 1

    count_list = list(count_dic.values())

    ans = 0
    for i in range(1, len(count_list) + 1):
        now_data = list(itertools.combinations(count_list, i))
        for ele in now_data:
            result = functools.reduce(operator.mul, ele)
            ans += result
    mod = 10 ** 9 + 7
    print(ans % mod)





if __name__ == '__main__':
    main()


Fixed submission:

from collections import defaultdict

def main():
    num = int(input())
    data = list(input())

    count_dic = defaultdict(int)

    for i in range(num):
        count_dic[data[i]] += 1

    count_list = list(count_dic.values())

    ans = 1
    for ele in count_list:
        ans *= ele + 1

    mod = 10 ** 9 + 7
    print((ans - 1) % mod)





if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
from collections import defaultdict
import sys
input = sys.stdin.readline

def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    pre = -1
    for i in range(num)[::-1]:
        if data[i] == pre:
            data.pop(i)
        pre = data[i]

    num = len(data)

    dic = defaultdict(int)
    mod = 10 ** 9 + 7
    dp = [1 for i in range(num + 1)]

    for i in range(num):
        now_num = data[i]
        dp[i + 1] = (dp[i] + dic[now_num]) % mod
        dic[now_num] += dp[i]
        dic[now_num] %= mod

    print(dp[num])

if __name__ == '__main__':
    main()


Fixed submission:
from collections import defaultdict

def main():
    num = int(input())
    data = [int(input()) for i in range(num)]

    dic = defaultdict(int)
    mod = 10 ** 9 + 7
    dp = [1 for i in range(num + 1)]

    for i in range(num):
        if i != 0:
            if data[i] == data[i - 1]:
                dp[i + 1] = dp[i]
                continue

        now_num = data[i]
        dp[i + 1] = (dp[i] + dic[now_num]) % mod
        dic[now_num] += dp[i]
        dic[now_num] %= mod

    print(dp[num])

if __name__ == '__main__':
    main()