Problem: In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east. A company called _AtCoder Express_ possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i). Takahashi the king is interested in the following Q matters:    * The number of the trains that runs **strictly within** the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.  Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Submission attempts (in order):
import numpy as np
def main():
    N, M, Q = map(int, input().split())
    LR = []
    for i in range(M):
        l, r = map(int, input().split())
        LR.append([l-1, r])
    PQ = []
    for i in range(Q):
        p, q = map(int, input().split())
        PQ.append([p-1, q-1])
    ar = np.zeros([M, N])
    for m in range(M):
        ar[m, LR[m][0]:LR[m][1]] = 1
    flags_start = [np.ones(M, dtype=np.bool)]
    flags_end = []
    for i in range(1, N):
        flags_start.append((ar[:, :i].max(axis=1)==0))# * (ar[:, i:].max(axis=1)==1))
        flags_end.append((ar[:, i:].max(axis=1)==0))# * (ar[:, :i].max(axis=1)==1))
    flags_end.append(np.ones(M, dtype=np.bool))
    for q in range(Q):
        left = PQ[q][0]
        right = PQ[q][1]
        print(sum(flags_start[left] * flags_end[right]))

if __name__=='__main__':
    main()

N, M, Q = map(int, input().split())
LR = []
for i in range(M):
    l, r = map(int, input().split())
    LR.append([l-1, r])
PQ = []
for i in range(Q):
    p, q = map(int, input().split())
    PQ.append([p-1, q-1])


import numpy as np
ar = np.zeros([M, N])
for m in range(M):
    ar[m, LR[m][0]:LR[m][1]] = 1

for q in range(Q):
    left = PQ[q][0]
    right = PQ[q][1]
    if left != 0 and right!=9:
        flag = (ar[:, left-1] == 0)* (ar[:, right+1] == 0) * (ar[:, left:right+1].max(axis=1) > 0)
        print(sum(flag))
    elif left == 0 and right!=9:
        flag = (ar[:, right+1] == 0) * (ar[:, left:right+1].max(axis=1) > 0)
        print(sum(flag))
    elif left != 0 and right==9:
        flag = (ar[:, left-1] == 0) * (ar[:, left:right+1].max(axis=1) > 0)
        print(sum(flag))
    else:
        print(M)


N, M, Q = map(int, input().split())
LR = []
for i in range(M):
    l, r = map(int, input().split())
    LR.append([l-1, r])
PQ = []
for i in range(Q):
    p, q = map(int, input().split())
    PQ.append([p-1, q-1])
    

import numpy as np
ar = np.zeros([M, N])
for m in range(M):
    ar[m, LR[m][0]:LR[m][1]] = 1
flags_start = [np.ones(M, dtype=np.bool)]
flags_end = []
for i in range(1, N):
    flags_start.append((ar[:, :i].max(axis=1)==0))# * (ar[:, i:].max(axis=1)==1))
    flags_end.append((ar[:, i:].max(axis=1)==0))# * (ar[:, :i].max(axis=1)==1))
flags_end.append(np.ones(M, dtype=np.bool))
for q in range(Q):
    left = PQ[q][0]
    right = PQ[q][1]
    print(sum(flags_start[left] * flags_end[right]))


import numpy as np
N, M, Q = map(int, input().split())
LR = []
for i in range(M):
    l, r = map(int, input().split())
    LR.append([l, r])
PQ = []
for i in range(Q):
    p, q = map(int, input().split())
    PQ.append([p, q])
ar_sec = np.zeros([N, N])
for i in range(M):
    l, r = LR[i][0], LR[i][1]
    ar_sec[l-1][r-1] += 1


ar_sum = np.zeros([N+1, N+1])
for i in range(N):
    for j in range(N):
        ar_sum[i+1][j+1] = ar_sum[i][j+1]+ar_sum[i+1][j]-ar_sum[i][j]+ar_sec[i][j]

for i in range(Q):
    p, q = PQ[i][0], PQ[i][1]
    print(int(ar_sum[q][q]-ar_sum[p-1][q]))


Verdicts: Time Limit Exceeded

Runtime Error

Time Limit Exceeded

Accepted