Problem p02599 (python)

Fixed submission:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())

    last = [-1]*(N+1)
    P = [[] for _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

    queries = [[] for _ in [0]*(N+1)]
    for i in range(Q):
        l, r = map(int, input().split())
        queries[l].append((r, i))

    def add(A, i, x):
        while i <= N:
            A[i] += x
            i += i & -i

    def sum(A, i):
        ret = 0
        while i:
            ret += A[i]
            i ^= i & -i
        return ret

    A = [0]*(N+1)
    ans = [0]*Q
    for l in range(N, 0, -1):
        for cr in P[l]:
            add(A, cr, 1)
        for r, i in queries[l]:
            ans[i] = r-l+1-sum(A, r)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, Q = map(int, input().split())
    *C, = map(int, input().split())

    last = [-1]*(N+1)
    P = [[] for _ in [0]*(N+1)]
    for i, c in enumerate(C):
        if last[c] != -1:
            P[last[c]].append(i+1)
        last[c] = i+1

    queries = [[] for _ in [0]*(N+1)]
    indices = [[] for _ in [0]*(N+1)]
    for i in range(Q):
        l, r = map(int, input().split())
        queries[l].append(r)
        indices[l].append(i)

    def add(A, i, x):
        while i <= N:
            A[i] += x
            i += i & -i

    def sum(A, i):
        ret = 0
        while i:
            ret += A[i]
            i ^= i & -i
        return ret

    A = [0]*(N+1)
    ans = [0]*Q
    for l in range(N, 0, -1):
        for cr in P[l]:
            add(A, cr, 1)
        for i, r in zip(queries[i], queries[l]):
            ans[i] = r-l+1-sum(A, r)

    print(*ans, sep='\n')


if __name__ == '__main__':
    main()

Buggy submission (verdict: Runtime Error):
import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
*C, = map(int, input().split())

last = [-1]*N
P = []
for i, c in enumerate(C):
    if last[c] != -1:
        P.append((last[c], i+1))
    last[c] = i+1

queries = []
for i in range(Q):
    l, r = map(int, input().split())
    queries.append((l, r, i))

P.sort()
queries.sort(reverse=True)

class BIT():
    def __init__(self, n, x=1):
        self.n = n
        self.T = [0]*(n+1)

    def add(self, i, x):
        while i <= self.n:
            self.T[i] += x
            i += i & -i

    def sum(self, i):
        ret = 0
        while i:
            ret += self.T[i]
            i -= i & -i
        return ret

bit = BIT(N)
ans = [0]*Q
for l, r, i in queries:
    while P and P[-1][0] >= l:
        cl, cr = P.pop()
        bit.add(cr, 1)
    ans[i] = r-l+1-bit.sum(r)

print('\n'.join(map(str, ans)))

Buggy submission (verdict: Runtime Error):
from functools import cmp_to_key
import sys
input = sys.stdin.readline
N, P = map(int, input().split())
*C, = map(int, input().split())

Q = [tuple(map(int, input().split())) for _ in range(P)]
Q = [(i, l, r) for i, (l, r) in enumerate(Q)]

block = int(N**0.5)


def compare(a, b):
    _, la, ra = a
    _, lb, rb = b
    if (la-1)//block != (lb-1)//block:
        return -1 if (la-1)//block < (lb-1)//block else 1
    return -1 if ra < rb else 1


Q.sort(key=cmp_to_key(compare))

ans = [0]*P
cl = cr = 0
S = dict()
S[C[0]] = set([0])
cnt = 1
for i, l, r in Q:
    l -= 1
    r -= 1
    while cl < l:
        x = C[cl]
        if x in S:
            if len(S[x]) == 1:
                del S[x]
                cnt -= 1
            else:
                S[x].remove(cl)
        cl += 1

    while l < cl:
        x = C[cl-1]
        if x in S:
            S[x].add(cl-1)
        else:
            S[x] = set([cl-1])
            cnt += 1
        cl -= 1

    while cr < r:
        x = C[cr+1]
        if x in S:
            S[x].add(cr+1)
        else:
            S[x] = set([cr+1])
            cnt += 1
        cr += 1

    while r < cr:
        x = C[cr]
        if x in S:
            if len(S[x]) == 1:
                del S[x]
                cnt -= 1
            else:
                S[x].remove(cr)
        cr -= 1

    ans[i] = cnt

print('\n'.join(map(str, ans)))