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 LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))


def cumulative_sum_ref(d1_array):
    for i in range(1, len(d1_array)):
        d1_array[i] += d1_array[i-1]


def cumulative_sum_val(d1_array):
    tmp = d1_array.copy()
    for i in range(1, len(tmp)):
        tmp[i] += tmp[i-1]
    return tmp



if __name__ != "__main__":
    N, M, Q = LI()
    LR = np.zeros((N+1, N+1), dtype='uint32')
    for i in range(M):
        l, r = LI()
        LR[l][r] += 1

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

    for _ in range(Q):
        p, q = LI()
        p -= 1
        result = LR[q][q] - LR[p][q] - LR[q][p] + LR[p][p]
        print(result)


if __name__ == "__main__":
    N, M, Q = LI()
    LR = np.zeros((N+1, N+1), dtype='uint32')
    for i in range(M):
        l, r = LI()
        LR[l][r] += 1

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

    for _ in range(Q):
        p, q = LI()
        p -= 1
        result = LR[q][q] - LR[p][q] - LR[q][p] + LR[p][p]
        print(result)


import numpy as np


def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))


def cumulative_sum_ref(d1_array):
    for i in range(1, len(d1_array)):
        d1_array[i] += d1_array[i-1]


def cumulative_sum_val(d1_array):
    tmp = d1_array.copy()
    for i in range(1, len(tmp)):
        tmp[i] += tmp[i-1]
    return tmp



if __name__ != "__main__":
    N, M, Q = LI()
    LR = np.zeros((N+1, N+1), dtype='uint32')
    for i in range(M):
        l, r = LI()
        LR[l][r] += 1

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

    for _ in range(Q):
        p, q = LI()
        p -= 1
        result = LR[q][q] - LR[p][q] - LR[q][p] + LR[p][p]
        print(result)


if __name__ == "__main__":
    N, M, Q = LI()
    LR = np.zeros((N+1, N+1), dtype='uint32')
    for i in range(M):
        l, r = LI()
        LR[l][r] += 1

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

    for _ in range(Q):
        p, q = LI()
        p -= 1
        result = LR[q][q] - LR[p][q] - LR[q][p] + LR[p][p]
        print(result)


from itertools import accumulate as acc
import sys


def main():
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    LR = [[0]*N for _ in [0]*N]
    for l, r in (map(int, e.split()) for e in s[1:M + 1]):
        LR[l - 1][r - 1] += 1

    S = [tuple(acc(reversed(s))) for s in zip(*(acc(x) for x in LR))]
    print('\n'.join(map(str, (S[q - 1][N - p] for p, q in (map(int, e.split()) for e in s[M + 1:])))))


if __name__ == "__main__":
    main()


Verdicts: Wrong Answer

Wrong Answer

Accepted