Buggy python submission (verdict: Time Limit Exceeded):
import bisect
import numpy as np
N, M, Q = map(int, input().split())
trains = np.array([list(map(int, input().split())) for i in range(M)])
queries =np.array([list(map(int, input().split())) for i in range(Q)])

A  =np.zeros([N, N])#A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1, ri - 1] += 1
dp = np.zeros([N, N])

def ans(left, right):
    if dp[left, right] > 0:
        return dp[left, right]
    elif left > right:
        return 0
    elif left == right:
        dp[left, right] = A[left, right]
        return dp[left, right]
    else:
        dp[left, right] = ans(left, right-1) + ans(left + 1, right) + A[left, right] - ans(left + 1, right - 1)
        return dp[left, right]

for q in range(Q):
    pi, qi = queries[q]
    print(int(ans(pi - 1, qi - 1)))


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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1
dp = [[0] * N for __ in range(N)]

def ans(left, right):
    if dp[left][right] > 0:
        return dp[left][right]
    elif left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        return A[left][right]
    else:
        x = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        dp[left][right] = x
        return x

for q in range(Q):
    pi, qi = queries[q]
    print(ans(pi - 1, qi - 1))


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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1
dp = [[0] * N for __ in range(N)]

def ans(left, right):
    if dp[left][right] > 0:
        return dp[left][right]
    elif left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        return A[left][right]
    else:
        x = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        dp[left][right] = x
        return x

for q in range(Q):
    pi, qi = queries[q]
    print(ans(pi - 1, qi - 1))


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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1
dp = [[0 for _ in range(N)] for __ in range(N)]

def ans(left, right):
    if dp[left][right] > 0:
        return dp[left][right]
    elif left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        return dp[left][right]
    else:
        dp[left][right] = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        return dp[left][right]

for q in range(Q):
    pi, qi = queries[q]
    print(ans(pi - 1, qi - 1))


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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1
dp = [[0 for _ in range(N)] for __ in range(N)]

def ans(left, right):
    if left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        return dp[left][right]
    else:
        dp[left][right] = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        return dp[left][right]

for q in range(Q):
    pi, qi = queries[q]
    print(ans(pi - 1, qi - 1))


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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])
L = [train[0] for train in trains]
R = [train[1] for train in trains]

dp = [[0] * N for i in range(N)]
for i in range(N):
    for j in range(i, N):
        right = bisect.bisect_right(R, j + 1)
        A = sorted(L[:right])
        left = bisect.bisect_left(A, i + 1)
        dp[i][j] = right - left

for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][qi - 1])


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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])
L = [train[0] for train in trains]
R = [train[1] for train in trains]

dp = [[0] * N for i in range(N)]
for i in range(N):
    for j in range(i, N):
        right = bisect.bisect_right(R, j + 1)
        A = sorted(L[:right])
        left = bisect.bisect_left(A, i + 1)
        dp[i][j] = right - left
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][qi - 1])


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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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

trains = [list(map(int, input().split())) for i in range(M)]
intervals = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])
L = [train[0] for train in trains]
R = [train[1] for train in trains]
for i in range(Q):
    pi, qi = intervals[i]
    right = bisect.bisect_right(R, qi)
    A = sorted(L[:right])
    left = bisect.bisect_left(A, pi)
    print(right - left)


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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])

Buggy python submission (verdict: Time Limit Exceeded):
import bisect

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

trains = [list(map(int, input().split())) for i in range(M)]
intervals = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])
L = [train[0] for train in trains]
R = [train[1] for train in trains]
for i in range(Q):
    pi, qi = intervals[i]
    right = bisect.bisect_right(R, qi)
    A = sorted(L[:right])
    left = bisect.bisect_left(A, pi)
    print(right - left)


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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])