Harryxun/testdata huggingface dataset:
Buggy python submission (verdict: Time Limit Exceeded):
import collections
import bisect
import copy
def main():

    N, M, Q = map(int, input().split())
    train = []
    for _ in range(M):
        l, r = map(int, input().split())
        train.append([l, r])
    train.sort()
    # print(train)

    end = []
    ends = []
    j = M-1
    for i in range(N, 0, -1):
        while j >= 0 and train[j][0] >= i:
            l, r = train[j]
            bisect.insort(end, r)
            j -= 1
        ends.append(copy.copy(end))
    ends.append([])
    ends = ends[::-1]
    # print(N)
    # print(ends)

    for _ in range(Q):
        p, q = map(int, input().split())
        j = bisect.bisect_right(ends[p], q)
        print(j)

if __name__ == '__main__':
    main()

Fixed submission:
def main():

    N, M, Q = map(int, input().split())
    train = [[0 for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        l, r = map(int, input().split())
        train[l-1][r-1] += 1

    accum = [[0 for _ in range(N+1)]]
    for i in range(N):
        temp = [0]
        v = 0
        for j in range(N):
            v += train[i][j]
            temp.append(accum[-1][j+1]+v)
        accum.append(temp)
        # print(temp)

    for _ in range(Q):
        p, q = map(int, input().split())
        v = accum[q][q] - accum[p-1][q] - accum[q][p-1] + accum[p-1][p-1]
        print(v)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import collections
def main():
    s = input()
    K = int(input())
    d = collections.defaultdict(set)
    n = len(s)
    for i in range(n):
        for l in range(1, n-i+1):
            d[s[i]].add(s[i:i+l])
    for c in sorted(d.keys()):
        if len(d[c]) < K:
            K -= len(d[c])
        else:
            d[c] = sorted(d[c])
            return d[c][K-1]

if __name__ == '__main__':
    print(main())


Fixed submission:
import collections
def main():
    s = input()
    K = int(input())
    d = collections.defaultdict(int)
    idx = collections.defaultdict(list)
    n = len(s)
    for i in range(n):
        idx[s[i]].append(i)

    cand = set()
    for c in sorted(idx.keys())[:K]:
        cand.add(c)
        for i in idx[c]:
            for l in range(1, K+1):
                cand.add(s[i:i+l])

    cand = sorted(list(cand))
    return cand[K-1]

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    H, W, D = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    Q = int(input())
    queries = []
    for _ in range(Q):
        R, L = map(int, input().split())
        queries.append([R, L])

    d = dict()
    for i in range(H):
        for j in range(W):
            d[A[i][j]] = [i, j]

    for R, L in queries:
        i, j = d[R]
        magic = 0
        if R != L:
            while R+D != L:
                k, l = d[R+D]
                magic += abs(i-k)+abs(j-l)
                i, j = k, l
                R = R+D
            k, l = d[R+D]
            magic += abs(i-k) + abs(j-l)
        print(magic)

if __name__ == '__main__':
    main()

Fixed submission:
import collections
def main():
    H, W, D = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    Q = int(input())
    queries = []
    for _ in range(Q):
        L, R = map(int, input().split())
        queries.append([L, R])

    d = collections.defaultdict(list)
    for i in range(H):
        for j in range(W):
            d[A[i][j] % D].append([A[i][j], i, j])
    for v in d:
        d[v] = sorted(d[v], key = lambda x: x[0])

    d1 = collections.defaultdict(list)
    for v in d:
        prefix = [0]
        if v == 0:
            prefix.append(0)
        for i in range(len(d[v])-1):
            mag = abs(d[v][i][1] - d[v][i+1][1]) + abs(d[v][i][2]-d[v][i+1][2])
            prefix.append(prefix[-1]+mag)
        d1[v] = prefix
    # print(d1)

    # print(A)
    for L, R in queries:
        if L == R:
            print(0)
        else:
            l = (R-L) // D
            i = L // D
            v = L % D
            magic = d1[v][i+l] - d1[v][i]
            print(magic)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import collections
def main():
    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for _ in range(M):
        L, R, D = map(int, input().split())
        graph[L][R] = D
        graph[R][L] = -D

    visited = set()
    for i in range(1, N+1):
        if i not in visited:
            cur = dict()
            cur[i] = 0
            while True:
                temp = dict()
                for j in cur:
                    for k in graph[j]:
                        l = cur[j] + graph[j][k]
                        if k not in cur:
                            temp[k] = l
                        elif k in cur and cur[k] != l:
                            return "No"
                        elif k in temp and temp[k] != l:
                            return "No"
                for k in temp:
                    cur[k] = temp[k]
                if len(temp) == 0:
                    break
    return "Yes"

if __name__ == '__main__':
    print(main())

Fixed submission:
import collections
def main():
    N, M = map(int, input().split())
    graph = collections.defaultdict(dict)
    for _ in range(M):
        L, R, D = map(int, input().split())
        graph[L][R] = D
        graph[R][L] = -D

    visited = set()
    used = set()
    for i in range(1, N+1):
        if i not in visited:
            dist = dict()
            dist[i] = 0
            cur = [i]
            visited.add(i)
            while cur:
                temp = []
                for j in cur:
                    for k in graph[j]:
                        if (j, k) not in used and (k, j) not in used:
                            used.add((j, k))
                            used.add((k, j))
                            if k not in dist:
                                dist[k] = dist[j] + graph[j][k]
                                temp.append(k)
                                visited.add(k)
                            elif k in dist:
                                if dist[k] != dist[j] + graph[j][k]:
                                    return "No"
                cur = temp

    return "Yes"

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

    N, C = map(int, input().split())
    d = collections.defaultdict(list)

    for _ in range(N):
        s, t, c  = map(int, input().split())
        d[c].append([s, t])

    for c in d:
        d[c].sort()
        lv = []
        for i in range(len(d[c])):
            if i == 0:
                lv.append(d[c][i])
            else:
                if lv[-1][1] == d[c][i][0]:
                    lv[-1][1] = d[c][i][1]
                else:
                    lv.append(d[c][i])
        d[c] = lv

    # print(d)
    index = dict()
    for c in d: index[c] = 0
    bound = max([d[c][-1][1] for c in d])
    ans = 0
    for i in range(1, bound + 1):
        cnt = 0
        for c in d:
            while index[c] < len(d[c]) and d[c][index[c]][1] < i:
                index[c] += 1
            if index[c] < len(d[c]) and d[c][index[c]][0] <= i <= d[c][index[c]][1]:
                cnt += 1
        # print(i, cnt)
        ans = max(ans, cnt)
    return ans


if __name__ == '__main__':
    print(main())

Fixed submission:
import collections
def main():

    N, C = map(int, input().split())
    d = collections.defaultdict(list)

    for _ in range(N):
        s, t, c  = map(int, input().split())
        d[c].append([s, t])

    for c in d:
        d[c].sort()
        lv = []
        for i in range(len(d[c])):
            if i == 0:
                lv.append(d[c][i])
            else:
                if lv[-1][1] == d[c][i][0]:
                    lv[-1][1] = d[c][i][1]
                else:
                    lv.append(d[c][i])
        d[c] = lv

    # print(d)
    index = dict()
    for c in d: index[c] = 0
    bound = max([d[c][-1][1] for c in d])
    ans = 0
    for i in range(1, bound + 1):
        cnt = 0
        for c in d:
            while index[c] < len(d[c]) and d[c][index[c]][1] < i:
                index[c] += 1
            if index[c] < len(d[c]) and d[c][index[c]][0] <= i <= d[c][index[c]][1]:
                cnt += 1
        # print(i, cnt)
        ans = max(ans, cnt)
    return ans


if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
v = math.sqrt(N)
pritn(int(v)*int(v))

Fixed submission:
import math
n = int(input())
v = int(math.sqrt(n))
print(v*v)

Buggy python submission (verdict: Runtime Error):
import math
def main():
	N = int(input())
	v = int(math.sqrt(N))
    print(v*v)
if __name__ == "__main__":
	main()

Fixed submission:
import math
n = int(input())
v = int(math.sqrt(n))
print(v*v)

Buggy python submission (verdict: Runtime Error):
import math
N = int(input())
v = int(math.sqrt(N))
return v*v

Fixed submission:
import math
n = int(input())
v = int(math.sqrt(n))
print(v*v)

Buggy python submission (verdict: Runtime Error):
import math
v = int(math.sqrt(N))
print(v*v)

Fixed submission:
import math
n = int(input())
v = int(math.sqrt(n))
print(v*v)

Buggy python submission (verdict: Runtime Error):
import math
v = int(math.sqrt(N))
return v*v

Fixed submission:
import math
n = int(input())
v = int(math.sqrt(n))
print(v*v)
Buggy python submission (verdict: Time Limit Exceeded):
import itertools
def main():

    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    r = [v-1 for v in r]

    dist = [[float('inf') for _ in range(N)] for _ in range(N)]
    for i in range(N): dist[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    path = itertools.permutations(r)
    ans = float('inf')
    for p in path:
        d = 0
        for i in range(len(p)-1):
            d += dist[p[i]][p[i+1]]
        ans = min(ans, d)

    return ans

if __name__ == '__main__':
    print(main())

Fixed submission:
import itertools
def main():

    N, M, R = map(int, input().split())
    r = list(map(int, input().split()))
    r = [v-1 for v in r]

    dist = [[float('inf') for _ in range(N)] for _ in range(N)]
    for i in range(N): dist[i][i] = 0
    for _ in range(M):
        a, b, c = map(int, input().split())
        dist[a-1][b-1] = c
        dist[b-1][a-1] = c

    for k in range(N):
        for i in range(N):
            for j in range(N):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    path = itertools.permutations(r)
    ans = float('inf')
    for p in path:
        d = 0
        for i in range(len(p)-1):
            d += dist[p[i]][p[i+1]]
        ans = min(ans, d)

    return ans

if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Runtime Error):
def main():
	N, M = map(int, input().split())
    d = dict()
    for _ in range(M):
        a, b = map(int, input().split())
        d[a] = d.get(a, 0) + 1
        d[b] = d.get(b, 0) + 1

    for a in range(1, N+1):
        if a in d:
            print(d[a])
        else:
            print(0)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, M = map(int, input().split())
    d = dict()
    for _ in range(M):
        a, b = map(int, input().split())
        d[a] = d.get(a, 0) + 1
        d[b] = d.get(b, 0) + 1

    for a in range(1, N+1):
        if a in d:
            print(d[a])
        else:
            print(0)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
	N, M = map(int, input().split())
    d = dict()
    for _ in range(M):
        a, b = map(int, input().split())
        d[a] = d.get(a, 0) + 1
        d[b] = d.get(b, 0) + 1

    for a in range(1, N+1):
        if a in d:
            print(d[a])
        else:
            print(0)

if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, M = map(int, input().split())
    d = dict()
    for _ in range(M):
        a, b = map(int, input().split())
        d[a] = d.get(a, 0) + 1
        d[b] = d.get(b, 0) + 1

    for a in range(1, N+1):
        if a in d:
            print(d[a])
        else:
            print(0)

if __name__ == '__main__':
    main()

Buggy python submission (verdict: Runtime Error):
def main():
    N, M = map(int, input().split())
    d = dict()
    for _ in range(M):
        a, b = map(int, input().split())
        d[a] = d.get(a, 0) + 1
        d[b] = d.get(b, 0) + 1

    for a in range(1, N+1):
        print(d[a])


if __name__ == '__main__':
    main()

Fixed submission:
def main():
    N, M = map(int, input().split())
    d = dict()
    for _ in range(M):
        a, b = map(int, input().split())
        d[a] = d.get(a, 0) + 1
        d[b] = d.get(b, 0) + 1

    for a in range(1, N+1):
        if a in d:
            print(d[a])
        else:
            print(0)

if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    tot = 0
    while A:
        A.pop()
        tot += A.pop()
        A.pop(0)
    return tot
 
if __name__ == '__main__':
    print(main())

Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    tot = 0
    for i in range(N):
        tot += A[3*N-2-2*i]
    return tot
if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Time Limit Exceeded):
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    tot = 0
    while A:
        A.pop()
        tot += A.pop()
        A.pop(0)
    return tot

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():
    N = int(input())
    A = list(map(int, input().split()))
    A.sort()
    tot = 0
    for i in range(N):
        tot += A[3*N-2-2*i]
    return tot
if __name__ == '__main__':
    print(main())
Buggy python submission (verdict: Time Limit Exceeded):
import collections
def main():

    H, W, N = map(int, input().split())
    checked = collections.defaultdict(set)
    black = collections.defaultdict(set)
    refs = []
    for _ in range(N):
        a, b = map(int, input().split())
        black[a].add(b)
        refs.append([a, b])

    ans = [0 for _ in range(10)]
    for a, b in refs:
        for da in [-1, 0, 1]:
            for db in [-1, 0, 1]:
                c, d = a+da, b+db
                if d not in checked[c]:
                    checked[c].add(d)
                    if all(1<=c+dc<=H and 1<=d+dd<=W for dc in [-1,0,1] for dd in[-1, 0, 1]):
                        count = 0
                        for dc in [-1, 0, 1]:
                            for dd in [-1, 0, 1]:
                                if d+dd in black[c+dc]:
                                    count += 1
                        ans[count] += 1
    ans[0] = (H-2)*(W-2) - sum(ans[1:]) 
    for i in range(10):
        print(ans[i])

if __name__ == '__main__':
    main()

Fixed submission:
import collections
def main():

    H, W, N = map(int, input().split())
    checked = collections.defaultdict(set)
    black = collections.defaultdict(set)
    refs = []
    for _ in range(N):
        a, b = map(int, input().split())
        black[a].add(b)
        refs.append([a, b])

    ans = [0 for _ in range(10)]
    for a, b in refs:
        for da in [-1, 0, 1]:
            for db in [-1, 0, 1]:
                c, d = a+da, b+db
                if d not in checked[c]:
                    checked[c].add(d)
                    if all(1<=c+dc<=H and 1<=d+dd<=W for dc in [-1,0,1] for dd in[-1, 0, 1]):
                        count = 0
                        for dc in [-1, 0, 1]:
                            for dd in [-1, 0, 1]:
                                if d+dd in black[c+dc]:
                                    count += 1
                        ans[count] += 1
    ans[0] = (H-2)*(W-2) - sum(ans[1:]) 
    for i in range(10):
        print(ans[i])

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

    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    # print(A)
    pairs = 0
    for i in range(N-1):
        pairs += A[i] // 2
        A[i] = A[i] % 2
        pairs += min(A[i], A[i+1])
        A[i], A[i+1] = A[i]-min(A[i], A[i+1]), A[i+1]-min(A[i], A[i+1])
    pairs += A[i+1] // 2

    return pairs

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():

    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    # print(A)
    pairs = 0
    for i in range(N-1):
        pairs += A[i] // 2
        A[i] = A[i] % 2
        pairs += min(A[i], A[i+1])
        A[i], A[i+1] = A[i]-min(A[i], A[i+1]), A[i+1]-min(A[i], A[i+1])
    pairs += A[N-1] // 2

    return pairs

if __name__ == '__main__':
    print(main())

Buggy python submission (verdict: Runtime Error):
def main():

    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    # print(A)
    pairs = 0
    for i in range(N-1):
        pairs += min(A[i], A[i+1])
        A[i], A[i+1] = A[i]-min(A[i], A[i+1]), A[i+1]-min(A[i], A[i+1])
        pairs += A[i] // 2
    pairs += A[i+1] // 2

    return pairs

if __name__ == '__main__':
    print(main())

Fixed submission:
def main():

    N = int(input())
    A = []
    for _ in range(N):
        A.append(int(input()))

    # print(A)
    pairs = 0
    for i in range(N-1):
        pairs += A[i] // 2
        A[i] = A[i] % 2
        pairs += min(A[i], A[i+1])
        A[i], A[i+1] = A[i]-min(A[i], A[i+1]), A[i+1]-min(A[i], A[i+1])
    pairs += A[N-1] // 2

    return pairs

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

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}


def main():
    N, M = map(int, readline().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, readline().split())
        uf.union(a-1,b-1)
    L = uf.all_group_members().values()
    ans = 1
    for l in L:
        ans = max(ans, len(l))
    print(ans)


if __name__ == '__main__':
    main()


Fixed submission:
import sys

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]


def main():
    N, M = map(int, readline().split())
    uf = UnionFind(N)
    for _ in range(M):
        a, b = map(int, readline().split())
        uf.union(a - 1, b - 1)
    print(-min(uf.parents))


if __name__ == '__main__':
    main()
Buggy python submission (verdict: Time Limit Exceeded):
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    X = 1
    for i in range(K):
        X *= A[i]
    B = [X]
    for i in range(K,N):
        tmp = B[-1] * A[i] // A[i-K]
        B.append(tmp)

    for i in range(N-K):
        if B[i+1]<=B[i]:
            print('No')
        else:
            print('Yes')



if __name__ == '__main__':
    main()



Fixed submission:
import sys
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    for i in range(K,N):
        if A[i]<=A[i-K]:
            print('No')
        else:
            print('Yes')


if __name__ == '__main__':
    main()