Problem p03283 (python)

Fixed submission:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, Q = map(int, input().split())

mat = [[0]*(N+1) for _ in range(N+1)]

for _ in range(M):
    a, b = map(int, input().split())
    mat[a][b] += 1


def solve():

    for i in range(N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i][j-1]

    ans = []

    for _ in range(Q):
        ql, qr = map(int, input().split())
        tmp = 0
        for i in range(ql, qr+1):
            tmp += mat[i][qr] - mat[i][ql-1]
        ans.append(tmp)

    for a in ans:
        print(a)


def solve2():

    for i in range(1, N+1):
        for j in range(1, N+1):
            mat[i][j] += mat[i-1][j] + \
                mat[i][j-1] - mat[i-1][j-1]

    ans = [0]*Q
    for i in range(Q):
        ql, qr = map(int, input().split())
        t = mat[qr][qr] - mat[ql-1][qr] - mat[qr][ql-1] + mat[ql-1][ql-1]
        ans[i] = t

    for a in ans:
        print(a)


solve2()

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, Q = map(int, input().split())
trains = []
for _ in range(M):
    a, b = map(int, input().split())
    trains.append([a, b])

query = []
for _ in range(Q):
    a, b = map(int, input().split())
    query.append([a, b])


def solve():
    # i駅目以前に(i駅も含む)出発した電車
    start_acc = [0]*(N+2)
    # i駅目以前に(i駅も含む)終点を迎えた電車
    finished_acc = [0]*(N+2)

    train = sorted(trains, key=lambda x: x[0])

    # 各駅の出発・到着数をカウント
    for start, dest in train:
        start_acc[start] += 1
        finished_acc[dest] += 1

    # 累積和にする
    for i in range(1, N+2):
        start_acc[i] += start_acc[i-1]
        finished_acc[i] += finished_acc[i-1]

    # qs~qdの数 = qD(を含む)までに終わった数 - qs(を含む)までに終わったやつ - qs(を含まない)より前に出発したやつ
    ans = []
    for qs, qd in query:
        a = finished_acc[qd] - finished_acc[qs-1] - start_acc[qs-1]
        ans.append(a)

    return ans


def solve2():
    start = [set() for _ in range(N+1)]
    end = [set() for _ in range(N+1)]

    for i in range(M):
        tr = trains[i]
        s = tr[0]
        g = tr[1]
        start[s].add(i)
        end[g].add(i)

    for i in range(1, N+1):
        start[i] |= start[i-1]
        end[i] |= end[i-1]

    ans = []
    for ds, dq in query:

        ans.append(len((start[dq] - start[ds-1]) & (end[dq] - end[ds-1])))

    return ans


ans = solve2()
for a in ans:
    print(a)

Buggy submission (verdict: Runtime Error):
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, Q = map(int, input().split())
trains = []
for _ in range(M):
    a, b = map(int, input().split())
    trains.append([a, b])

query = []
for _ in range(Q):
    a, b = map(int, input().split())
    query.append([a, b])


def solve():
    # i駅目以前に(i駅も含む)出発した電車
    start_acc = [0]*(N+2)
    # i駅目以前に(i駅も含む)終点を迎えた電車
    finished_acc = [0]*(N+2)

    train = sorted(trains, key=lambda x: x[0])

    # 各駅の出発・到着数をカウント
    for start, dest in train:
        start_acc[start] += 1
        finished_acc[dest] += 1

    # 累積和にする
    for i in range(1, N+2):
        start_acc[i] += start_acc[i-1]
        finished_acc[i] += finished_acc[i-1]

    # qs~qdの数 = qD(を含む)までに終わった数 - qs(を含む)までに終わったやつ - qs(を含まない)より前に出発したやつ
    ans = []
    for qs, qd in query:
        a = finished_acc[qd] - finished_acc[qs-1] - start_acc[qs-1]
        ans.append(a)

    return ans


def solve2():
    start = [set() for _ in range(N+1)]
    end = [set() for _ in range(N+1)]

    for i in range(M):
        tr = trains[i]
        s = tr[0]
        g = tr[1]
        start[s].add(i)
        end[g].add(i)

    for i in range(1, N+1):
        start[i] |= start[i-1]
        end[i] |= end[i-1]

    ans = []
    for ds, dq in query:

        ans.append(len((start[dq] - start[ds-1]) & (end[dq] - end[ds-1])))

    return ans


ans = solve2()
for a in ans:
    print(a)