Problem:
 Score: 400 points    Problem Statement  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.      Constraints   N is an integer between 1 and 500 (inclusive).  M is an integer between 1 and 200 \ 000 (inclusive).  Q is an integer between 1 and 100 \ 000 (inclusive).  1 \leq L_i \leq R_i \leq N  (1 \leq i \leq M)  1 \leq p_i \leq q_i \leq N  (1 \leq i \leq Q)         Input  Input is given from Standard Input in the following format:  N  M  Q  L_1  R_1  L_2  R_2  :  L_M  R_M  p_1  q_1  p_2  q_2  :  p_Q  q_Q       Output  Print Q lines. The i -th line should contain the number of the trains that runs strictly within the section from City p_i to City q_i .        Sample Input 1 2 3 1
1 1
1 2
2 2
1 2      Sample Output 1 3  As all the trains runs within the section from City 1 to City 2 , the answer to the only query is 3 .       Sample Input 2 10 3 2
1 5
2 8
7 10
1 7
3 10      Sample Output 2 1
1  The first query is on the section from City 1 to 7 . There is only one train that runs strictly within that section: Train 1 .
The second query is on the section from City 3 to 10 . There is only one train that runs strictly within that section: Train 3 .       Sample Input 3 10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10      Sample Output 3 7
9
10
6
8
9
6
7
8
10

Solution (Python):
def dpdo(left, right):
    if dp[left][right]!=-1:
        return dp[left][right]
    elif left==right:
        dp[left][right] = grid[left][right]
        return dp[left][right]
    elif right-left==1:
        dp[left][right] = dpdo(left,right-1) + dpdo(left+1, right) + grid[left][right]
        return dp[left][right]
    else:
        dp[left][right] = dpdo(left,right-1) + dpdo(left+1, right) + grid[left][right] - dpdo(left+1,right-1)
        return dp[left][right]

dp = []
grid = []
temp1 = []
temp2 = []
for i in range(0,501):
    temp1 = []
    temp2 = []
    for j in range(0,501):
        temp1.append(0)
        temp2.append(-1)
    dp.append(temp2)
    grid.append(temp1)
    
n, m, q = map(int,input().split())
for i in range(1,m+1):
    left, right = map(int, input().split())
    grid[left][right] += 1
    
dpdo(1,n)

for i in range(1,q+1):
    left, right = map(int, input().split())
    print(dp[left][right])

Solution (Python):

N, M, Q = map(int, input().split())
train_query = {} 
for i in range(M + Q):
    train_query[i] = list(map(int, input().split()))

train_query = sorted(train_query.items(), key=lambda x: x[1][1])


StartPoints = [0 for _ in range(N)] 
ans = [0 for _ in range(Q)] 

for j in range(M + Q):
    if train_query[j][0] < M: 
        StartPoints[train_query[j][1][0] - 1] += 1
    else: 
        ans[train_query[j][0] - M] = sum(StartPoints[(train_query[j][1][0] - 1):(train_query[j][1][1])])

for i in range(Q):
    print(ans[i])

Solution (Python):


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



T = [[] for l in range(N + 1)]
for i in range(M):
    l, r = map(int, input().split())
    T[l].append(r)


nt = [[0] * (N + 2) for l in range(N + 1)]
for i in range(1, N + 1):
    T[i].append(N + 1)  
    T[i].sort()
    prev = 0
    for r in T[i]:
        if r != prev:
            for j in range(prev + 1, r + 1):
                nt[i][j] = nt[i][prev]
            prev = r
        nt[i][r] += 1


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


for i in range(Q):
    p, q = map(int, input().split())
    print(nt[p][q])

Solution (Python):
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]))

Solution (Python):
def main():
    """
    """
    N, M, Q = map(int, input().split())
    L, R = zip(*(
        map(int, input().split())
        for _ in range(M)
    ))
    p, q = zip(*(
        map(int, input().split())
        for _ in range(Q)
    ))

    
    
    
    answers = editorial_2(N, M, Q, L, R, p, q)
    for ans in answers:
        print(ans)


def editorial_2(N, M, Q, L, R, p, q):
    """
    ２次元累積和のライブラリを持っておくとよいらしい
        確かに実装ミスりそう
    """
    t = [[0] * (N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        t[l][r] += 1

    
    
    for l in range(1, N+1):
        for r in range(1, N+1):
            t[l][r] += t[l][r-1]
    for l in range(1, N+1):
        for r in range(1, N+1):
            t[l][r] += t[l-1][r]

    answers = []
    for l, r in zip(p, q):
        ans = 0
        ans += t[r][r]
        ans -= t[l-1][r]
        ans -= t[r][l-1]
        ans += t[l-1][l-1]

        answers.append(ans)

    return answers


def editorial_1(N, M, Q, L, R, p, q):
    
    t1 = [[0] * (N+1) for _ in range(N+1)]
    t2 = [[0] * (N+1) for _ in range(N+1)]
    
    for l, r in zip(L, R):
        t1[l][r] += 1

    for l in range(1, N+1):
        for r in range(1, N+1):
            t2[l][r] = t2[l][r-1] + t1[l][r]

    answers = []
    for _p, _q in zip(p, q):
        ans = 0
        for l in range(_p, _q+1):
            ans += t2[l][_q] - t2[l][_p-1]

        answers.append(ans)

    return answers


def TLE(N, M, Q, L, R, p, q):
    """
    10^5 * 10^5
    """
    answers = []
    for _p, _q in zip(p, q):
        ans = 0
        for left, right in zip(L, R):
            if _p <= left and right <= _q:
                ans += 1

        answers.append(ans)

    return answers


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    """
    """
    N, M, Q = map(int, input().split())
    L, R = zip(*(
        map(int, input().split())
        for _ in range(M)
    ))
    p, q = zip(*(
        map(int, input().split())
        for _ in range(Q)
    ))

    
    
    
    answers = editorial(N, M, Q, L, R, p, q)
    for ans in answers:
        print(ans)


def editorial(N, M, Q, L, R, p, q):
    """
    ２次元累積和のライブラリを持っておくとよいらしい
        確かに実装ミスりそう

    """
    
    t1 = [[0] * (N+1) for _ in range(N+1)]
    t2 = [[0] * (N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        t1[l][r] += 1

    
    for l in range(1, N+1):
        for r in range(1, N+1):
            t2[l][r] = t2[l][r-1] + t1[l][r]

    answers = []
    for _p, _q in zip(p, q):
        ans = 0
        for l in range(_p, _q+1):
            ans += t2[l][_q] - t2[l][_p-1]

        answers.append(ans)

    return answers


def TLE(N, M, Q, L, R, p, q):
    """
    10^5 * 10^5
    """
    answers = []
    for _p, _q in zip(p, q):
        ans = 0
        for left, right in zip(L, R):
            if _p <= left and right <= _q:
                ans += 1

        answers.append(ans)

    return answers


if __name__ == '__main__':
    main()

Solution (Python):
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()

Solution (Python):
from itertools import accumulate as acc
import sys

if __name__ == "__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:])))))

Solution (Python):
from itertools import accumulate as acc
import sys

if __name__ == "__main__":
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    LR = [[0]*N for _ in range(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:])))))

Solution (Python):
from itertools import accumulate as acc
import sys

if __name__ == "__main__":
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    LR = [[0]*N for _ in range(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))]
    for p, q in (map(int, e.split()) for e in s[M+1:]):
        print(S[q-1][N-p])

Solution (Python):
import sys
s = sys.stdin.readlines()
 
N,M,Q = map(int,s[0].split())
 
Section = [[0]*N for _ in [0]*N]
for L,R in (map(int, e.split()) for e in s[1:M+1]):
    Section[L-1][R-1] += 1
 
Sum = [[0]*(N+1) for _ in [0]*(N+1)]
for i in range(N):
    for j in range(N):
        Sum[i+1][j+1] = Sum[i][j+1]+Sum[i+1][j]-Sum[i][j]+Section[i][j]
 
for p,q in (map(int, e.split()) for e in s[M+1:]):
    print(Sum[q][q]-Sum[p-1][q])

Solution (Python):
from itertools import accumulate as acc

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


if __name__ == "__main__":
    N, M, Q = LI()
    LR = [[0]*N for _ in range(N)]
    for i in range(M):
        l, r = LI_()
        LR[l][r] += 1

    
    S = [tuple(acc(reversed(s))) for s in zip(*(acc(x) for x in LR))]
    for _ in range(Q):
        p, q = LI()
        
        print(S[q-1][N-p])

Solution (Python):
from itertools import accumulate as acc

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


if __name__ == "__main__":
    N, M, Q = LI()
    LR = [[0]*N for _ in range(N)]
    for i in range(M):
        l, r = LI_()
        LR[l][r] += 1

    
    S = [[0] * N for _ in range(N)]
    for i, row in enumerate(LR):
        LR[i] = list(acc(row))
    for i, col in enumerate(zip(*LR)):
        S[i] = list(acc(reversed(col)))

    for _ in range(Q):
        p, q = LI()
        
        print(S[q-1][N-p])

Solution (Python):
n,m,q = list(map(int,input().split()))
c = []
query = []

for i in range(n):
  c.append([0*i for i in range(n)])
for i in range(m):
  train = []
  train = list(map(int,input().split()))
  c[train[0]-1][train[1]-1] += 1
for i in range(q):
  query.append(list(map(int,input().split())))

for i in range(n):    
  for j in range(n):
    if j > 0:
      c[i][j] += c[i][j-1]
    else:
      pass

for i in range(n):    
  for j in range(n):
    if i > 0:
      c[i][j] += c[i-1][j]
    else:
      pass

for l in query:    
  if l[0]-1 >= 1 and l[1]-1 >= 1:
    print(c[l[1]-1][l[1]-1] - c[l[1]-1][l[0]-2] - c[l[0]-2][l[1]-1] + c[l[0]-2][l[0]-2])
  elif l[1]-1 > 0:
    print(c[l[1]-1][l[1]-1])
  else:
    print(c[0][0])

Solution (Python):
import sys
s = sys.stdin.readlines()

N,M,Q = map(int,s[0].split())

Section = [[0]*N for _ in [0]*N]
for L,R in (map(int, e.split()) for e in s[1:M+1]):
    Section[L-1][R-1] += 1

Sum = [[0]*(N+1) for _ in [0]*(N+1)]
for i in range(N):
    for j in range(N):
        Sum[i+1][j+1] = Sum[i][j+1]+Sum[i+1][j]-Sum[i][j]+Section[i][j]

for p,q in (map(int, e.split()) for e in s[M+1:]):
    print(Sum[q][q]-Sum[p-1][q])

Solution (Python):
def arr(row, column, value): return [[value for _ in range(column)] for _ in range(row)]

n, m, q = map(int, input().split())

sum_range = arr(n + 1, n + 1, 0)




for _ in range(m):
    L, R = map(int, input().split())
    sum_range[L][R] += 1
    
for L in range(1, n + 1):
    for R in range(1, n + 1):
        
        
        sum_range[L][R] += sum_range[L - 1][R]
        sum_range[L][R] += sum_range[L][R - 1]
        sum_range[L][R] -= sum_range[L - 1][R - 1]


for _ in range(q):
    p, q = map(int, input().split())
    ans = sum_range[q][q] - sum_range[p - 1][q] - sum_range[q][p - 1] + sum_range[p - 1][p - 1]
    print(ans)

Solution (Python):
import sys
s = sys.stdin.readlines()

N,M,Q = map(int,s[0].split())

Section = [[0]*N for _ in range(N)]
for L,R in (map(int, e.split()) for e in s[1:M+1]):
    Section[L-1][R-1] += 1

Sum = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        Sum[i+1][j+1] = Sum[i][j+1]+Sum[i+1][j]-Sum[i][j]+Section[i][j]

for p,q in (map(int, e.split()) for e in s[M+1:]):
    print(Sum[q][q]-Sum[p-1][q])

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

range_array = [[0 for _ in range(N)] for _ in range(N)]
ans = [[0 for _ in range(N)] for _ in range(N)]

for _ in range(M):
    l, r = map(int, input().split())
    range_array[l - 1][r - 1] += 1

for i in range(N):
    sum = 0
    for j in range(N):
        sum += range_array[i][j]
        range_array[i][j] = sum
'''
for i in range(N):
    for j in range(i, N):
        sum = 0
        for k in range(i, j + 1):
            sum += range_array[k][j]
        ans[i][j] = sum
'''
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    sum = 0
    for k in range(p, q + 1):
        sum += range_array[k][q]
    print(sum)

Solution (Python):
import sys
s = sys.stdin.readlines()
N,M,Q = map(int,s[0].split())

Section = [[0]*N for _ in range(N)]
for L,R in (map(int, e.split()) for e in s[1:M+1]):
    Section[L-1][R-1] += 1

Sum = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        Sum[i+1][j+1] = Sum[i][j+1]+Sum[i+1][j]-Sum[i][j]+Section[i][j]

Ans = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(i,N):
        Ans[i][j] = Sum[j+1][j+1]-Sum[i][j+1]

for p,q in (map(int, e.split()) for e in s[M+1:]):
    print(Ans[p-1][q-1])

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

Section = [[0]*N for _ in range(N)]
for _ in range(M):
    L,R = map(int,input().split())
    Section[L-1][R-1] += 1

Sum = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        Sum[i+1][j+1] = Sum[i][j+1]+Sum[i+1][j]-Sum[i][j]+Section[i][j]

Ans = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(i,N):
        Ans[i][j] = Sum[j+1][j+1]-Sum[i][j+1]

for _ in range(Q):
    p,q = map(int,input().split())
    print(Ans[p-1][q-1])

Solution (Python):
n, m, q = map(int, input().split())

temp = [ [0 for _ in range(n)] for _ in range(n)]
tables = [ [0 for _ in range(n)] for _ in range(n)]

if n == 1:
    print('1')
    exit()

for _ in range(m):
    l, r = map(int, input().split())
    temp[l - 1][r - 1] += 1

pq = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

hoge = 0
for j in range(n):
    hoge += temp[0][j]
    tables[0][j] = hoge

for i in range(1, n):
    hoge = 0
    for j in range(n):
        hoge += temp[i][j]
        tables[i][j] = tables[i - 1][j] + hoge

for p, q in pq:
    if p == 0:
        print(tables[q][q])
    else:
        print(tables[q][q] - tables[p - 1][q] - tables[q][p - 1] + tables[p - 1][p - 1] )

Solution (Python):
import numpy as np

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = np.array([[0 for j in range(n)] for i in range(n)],dtype=np.int32)
for (l,r) in rails:
    xlist[l-1,r-1]+=1

sumsumlist = np.cumsum(np.cumsum(xlist,axis=1),axis=0)


for (p,q) in qs:
    if p>1:
        ans = sumsumlist[q-1][q-1] - sumsumlist[q-1][p-2] - sumsumlist[p-2][q-1] + sumsumlist[p-2][p-2]
    elif p==1:
        ans = sumsumlist[q-1][q-1]

    print(ans)

Solution (Python):
from collections import Counter
from itertools import product
import numpy as np

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = np.array([[0 for j in range(n)] for i in range(n)])
for (l,r) in rails:
    xlist[l-1,r-1]+=1

sumsumlist = np.cumsum(np.cumsum(xlist,axis=1),axis=0)


for (p,q) in qs:
    if p>1:
        ans = sumsumlist[q-1][q-1] - sumsumlist[q-1][p-2] - sumsumlist[p-2][q-1] + sumsumlist[p-2][p-2]
    elif p==1:
        ans = sumsumlist[q-1][q-1]

    print(ans)

Solution (Python):

from collections import Counter
from itertools import product
import numpy as np

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = np.array([[0 for j in range(n)] for i in range(n)])
for (l,r),i in Counter(rails).items():
    xlist[l-1,r-1]=i

sumsumlist = np.cumsum(np.cumsum(xlist,axis=1),axis=0)


for (p,q) in qs:
    if p>1:
        ans = sumsumlist[q-1][q-1] - sumsumlist[q-1][p-2] - sumsumlist[p-2][q-1] + sumsumlist[p-2][p-2]
    elif p==1:
        ans = sumsumlist[q-1][q-1]

    print(ans)

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

LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]


def rectangle_sum(n):
    table = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for l, r in LR:
        table[l][r] += 1

    for y in range(n + 1):
        for x in range(1, n + 1):
            table[y][x] += table[y][x - 1]

    for y in range(1, n + 1):
        for x in range(n + 1):
            table[y][x] += table[y - 1][x]
    return table


t = rectangle_sum(N)
for p, q in PQ:
    tmp = t[q][q] - t[q][p - 1] - t[p - 1][q] + t[p - 1][p - 1]
    print(tmp)

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

LR = [list(map(int, input().split())) for _ in range(M)]
PQ = [list(map(int, input().split())) for _ in range(Q)]


def rectangle_sum(n):
    table = [[0 for _ in range(n)] for _ in range(n)]

    for l, r in LR:
        table[l - 1][r - 1] += 1

    for y in range(N):
        for x in range(1, N):
            table[y][x] += table[y][x - 1]

    for y in range(1, N):
        for x in range(N):
            table[y][x] += table[y - 1][x]
    return table


t = rectangle_sum(N)
for p, q in PQ:
    if p - 2 >= 0:
        tmp = t[q - 1][q - 1] - t[q - 1][p - 2] - t[p - 2][q - 1] + t[p - 2][p - 2]
    else:
        tmp = t[q - 1][q - 1]

    print(tmp)

Solution (Python):

N, M, Q = map(int, input().split())
rail = []
for i in range(M):
    r = list(map(int, input().split()))
    rail.append(r)
 
query = []
for i in range(Q):
    q = list(map(int, input().split()))
    query.append(q)
 
f = [[0 for i in range(N)] for j in range(N)]
g = [[0 for i in range(N)] for j in range(N)]
 
for i in range(M):
    f[rail[i][0]-1][rail[i][1]-1] += 1
 
for i in range(N):
    j = 0
    while j + i < N:
        if i == 0:
            g[j][j+i] = f[j][j+i]
        else:
            g[j][j+i] = f[j][j+i] + g[j+1][j+i] + g[j][j+i-1] - g[j+1][j+i-1]
        j += 1
 
for i in range(Q):
    print(g[query[i][0]-1][query[i][1]-1])

Solution (Python):


n,m,q = list(map(int,input().split()))
M = [ list(map(int,input().split())) for i in range(m) ]
Q = [ list(map(int,input().split())) for i in range(q) ]

LR = [[0]*(n+1) for _ in range(n+1)]

for m in M:
    LR[m[0]-1][m[1]] += 1 

for l in range(n,-1,-1):
    for r in range(0,n,1):
        LR[l-1][r+1] = LR[l-1][r+1] + LR[l-1][r] + LR[l][r+1] - LR[l][r]

for q in Q:
    print(LR[q[0]-1][q[1]])

Solution (Python):
import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]


def main():
    n, m, q = na()
    lrs = [na() for _ in range(m)]
    pqs = [na() for _ in range(q)]

    table = [[0] * (n+1) for _ in range(n+1)]

    
    for l, r in lrs:
        table[l][r] += 1

    
    for i in range(1, n+1):
        for j in range(1, n+1):
            table[i][j] += table[i][j-1]

    
    for j in range(1, n+1):
        for i in range(1, n+1):
            table[i][j] += table[i-1][j]
            
    for p, q in pqs:
        v = table[q][q] - table[q][p-1] - table[p-1][q] + table[p-1][p-1]
        print(v)
    

main()

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


if __name__ == "__main__":
    N, M, Q = LI()
    LR = [[0]*(N+1) for _ in range(N+1)]
    for i in range(M):
        l, r = LI()
        LR[l][r] += 1

    
    for i in range(1, N+1):
        for j in range(1, 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)

Solution (Python):
N, M, Q = map(int, input().split())
rail = []
for i in range(M):
    r = list(map(int, input().split()))
    rail.append(r)

query = []
for i in range(Q):
    q = list(map(int, input().split()))
    query.append(q)

f = [[0 for i in range(N)] for j in range(N)]
g = [[0 for i in range(N)] for j in range(N)]

for i in range(M):
    f[rail[i][0]-1][rail[i][1]-1] += 1

for i in range(N):
    j = 0
    while j + i < N:
        if i == 0:
            g[j][j+i] = f[j][j+i]
        else:
            g[j][j+i] = f[j][j+i] + g[j+1][j+i] + g[j][j+i-1] - g[j+1][j+i-1]
        j += 1

for i in range(Q):
    print(g[query[i][0]-1][query[i][1]-1])

Solution (Python):
n,m,Q=map(int,input().split())

l=[]
r=[]
for i in range(m):
    a,b=map(int,input().split())
    l.append(a)
    r.append(b)

p=[]
q=[]    
for i in range(Q):
    c,d=map(int,input().split())
    p.append(c)
    q.append(d)

grid=[[0]*(n+1) for i in range(n+1)]

for i in range(m):
    grid[l[i]][r[i]]+=1

for i in range(1,n+1):
    for j in range(1,n+1):
        grid[i][j]+=grid[i-1][j]
        grid[i][j]+=grid[i][j-1]
        grid[i][j]-=grid[i-1][j-1]
    
for i in range(Q):
    print(grid[q[i]][q[i]]-grid[q[i]][p[i]-1]-grid[p[i]-1][q[i]]+grid[p[i]-1][p[i]-1])

Solution (Python):

"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""

n, m, qn = list(map(int, input().split()))

lr = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
    
for i in range(n+1):
    for j in range(n):
        lr[i][j+1] += lr[i][j]
for i in range(n+1):
    for j in range(n):
        lr[j+1][i] += lr[j][i]

for _ in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = lr[qi][qi] - lr[qi][pi-1] - lr[pi-1][qi] +lr[pi-1][pi-1]
    
    print(ans)

Solution (Python):
N,M,Q = map(int,input().split())
memo = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    memo[l][r] += 1
for i in range(N):
    for j in range(N):
        memo[i+1][j+1] += memo[i][j+1] + memo[i+1][j] - memo[i][j]
for i in range(Q):
    p,q = map(int,input().split())
    print(memo[q][q] - memo[p-1][q] - memo[q][p-1] + memo[p-1][p-1])

Solution (Python):
import sys
import numpy as np
def main():
    s = sys.stdin.readlines()
    N, M, _ = map(int, s[0].split())
    X = np.zeros((N, N), dtype=int)
    for L, R in (map(int, e.split()) for e in s[1:M + 1]): X[L - 1][R - 1] += 1
    S = np.cumsum(np.cumsum(X, axis=1)[::-1], axis=0)[::-1]
    print('\n'.join(map(str, (S[p - 1][q - 1] for p, q in (map(int, e.split()) for e in s[M + 1:])))))
if __name__ == '__main__':
    main()

Solution (Python):
import sys
from itertools import accumulate as acc
def main():
    s = sys.stdin.readlines()
    N, M, _ = map(int, s[0].split())
    X = [[0] * N for _ in [0] * N]
    for L, R in (map(int, e.split()) for e in s[1:M + 1]): X[L - 1][R - 1] += 1
    S = [tuple(acc(reversed(s))) for s in zip(*(acc(x) for x in X))]
    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()

Solution (Python):
N, M, Q = map(int,input().split())
senro = [list(map(int,input().split())) for k in range(M)]
query = [list(map(int,input().split())) for k in range(Q)]
S = [[0 for k in range(N+2)] for l in range(N+2)]

for s in senro:
    S[s[0]][s[1]] += 1

for k in range(1,N+2):
    for l in range(1,N+2):
        S[k][l] += S[k][l-1]

for k in range(1,N+2):
    for l in range(1,N+2):
        S[k][l] += S[k-1][l]

for q in query:
    print(S[q[1]][q[1]]-S[q[0]-1][q[0]-1]-S[q[0]-1][q[1]]+S[q[1]][q[0]-1])

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

dp = [[0 for col in range(N)] for row in range(N)]

for i in range(M):
    l, r = map(int, input().split())
    dp[l-1][r-1]+=1

for i in range(N):
    for j in range(N)[:-1]:
        dp[i][j+1] += dp[i][j]
        
for i in range(N)[:0:-1]:
    for j in range(N):
        dp[i-1][j] += dp[i][j]

results = []

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

for result in results:
    print(result)

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

dp = [[0 for col in range(N)] for row in range(N)]

for i in range(M):
    l, r = map(int, input().split())
    dp[l-1][r-1]+=1

for i in range(N):
    for j in range(N)[:-1]:
        dp[i][j+1] += dp[i][j]
        
for i in range(N)[:0:-1]:
    for j in range(N):
        dp[i-1][j] += dp[i][j]

results = []

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

for result in results:
    print(result)

Solution (Python):
import sys
def main():
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    x = [[0] * N for _ in [0] * N]
    for e in s[1:M + 1]:
        L, R = map(int, e.split())
        x[L - 1][R - 1] += 1
    for k in range(1, N):
        for i in range(N - k):
            j = i + k
            x[i][j] += x[i][j - 1] + x[i + 1][j] - x[i + 1][j - 1]
    res = []
    for e in s[M + 1:]:
        p, q = map(int, e.split())
        res.append(x[p - 1][q - 1])
    print('\n'.join(map(str, res)))
if __name__ == '__main__':
    main()

Solution (Python):

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


cnt_tab = [0] * (N ** 2)
for l, r in LR: cnt_tab[(r - 1) * N + (l - 1)] += 1


sum_tab = [None] * (N ** 2) 
for r in range(N):
    newsum = 0
    for l in reversed(range(r + 1)):
        newsum += cnt_tab[r * N + l] 
        if l < r: sum_tab[r * N + l] = sum_tab[(r - 1) * N + l] + newsum
        else: sum_tab[r * N + l] = newsum
        

for p, q in pq: print(sum_tab[(q - 1) * N + (p - 1)])

Solution (Python):
n,m,q = map(int,input().split())
lr = [[0 for _ in range(0,n+1)] for _ in range(0,n+1)]
ans = []
for i in range(0,m):
    L,R = map(int,input().split())
    lr[R][L] += 1
for r in range(0,n+1):
    for l in range(0,n):
        lr[r][n-l-1] += lr[r][n-l]
for l in range(0,n+1):
    for r in range(0,n):
        lr[r+1][l] += lr[r][l]
for i in range(0,q):
    P,Q = map(int,input().split())
    ans.append(lr[Q][P])
for i in range(0,q):
    print(ans[i])

Solution (Python):
N, M, Q = map(int, input().split())
G = [[0] * (N+1) for i in range(N+1)]
for m in range(M):
    l, r = map(int, input().split())
    G[l][r] += 1


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


for q in range(Q):
    p, q = map(int, input().split())
    print(G[q][q] - G[q][p-1] - G[p-1][q] + G[p-1][p-1])

Solution (Python):
N,M,Q=map(int,input().split())
L=[0 for i in range(M)]
R=[0 for i in range(M)]
p=[0 for i in range(Q)]
q=[0 for i in range(Q)]
ans=[0 for i in range(Q)]
B=[[0 for i in range(N+1)] for i in range(N+1)]
C=[[0 for i in range(N+1)] for i in range(N+1)]
D=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
    L[i],R[i]=map(int,input().split())
    L[i]-=1
    R[i]-=1
for i in range(Q):
    p[i],q[i]=map(int,input().split())
    p[i]-=1
    q[i]-=1
for i in range(M):
    B[R[i]][0]+=1
    B[R[i]][L[i]+1]-=1
    B[N][0]-=1
    B[N][L[i]+1]+=1
for i in range(N+1):
    for j in range(N+1):
        if i==0:
            C[i][j]=B[i][j]
        else:
            C[i][j]=B[i][j]+C[i-1][j]
for i in range(N+1):
    for j in range(N+1):
        if j==0:
            D[i][j]=C[i][j]
        else:
            D[i][j]=C[i][j]+D[i][j-1]
for i in range(Q):
    ans[i]=D[q[i]][p[i]]

for line in ans:
    print(line)

Solution (Python):



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


Xi = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    Xi[L][R] += 1


Ci = [[0]*(N+1) for i in range(N+1)]
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp



for r in range(N+1):
    tmp = 0
    for l in range(N+1):
        tmp += Ci[l][r]
        Ci[l][r] = tmp



pqi = []
for i in range(Q):
    p, q = map(int, input().split())
    pqi.append((p,q))

for (p, q) in pqi:
    tmp = Ci[q][q] - Ci[q][p-1]  - Ci[p-1][q] + Ci[p-1][p-1]
    print(tmp)

Solution (Python):
from collections import Counter
from itertools import product

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
sumsumlist = [[0 for j in range(n+1)] for i in range(n+1)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i


for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])

for (i,j) in product(range(n),range(n)):
    sumsumlist[i+1][j+1] = sum(map(lambda x:x[j+1],sumlist[0:i+1]))



for (p,q) in qs:
    ans = sumsumlist[q][q]- sumsumlist[q][p-1] -sumsumlist[p-1][q] + sumsumlist[p-1][p-1]
    print(ans)

Solution (Python):
import sys
from itertools import accumulate, islice

n, m, q = map(int, input().split())
ipt = (map(int, line.split()) for line in sys.stdin.readlines())
rails = [[0] * n for _ in range(n)]
for l, r in islice(ipt, m):
    rails[l - 1][r - 1] += 1
rails = [list(accumulate(reversed(s))) for s in zip(*(accumulate(s) for s in rails))]
print('\n'.join(map(str, (rails[q - 1][n - p] for p, q in ipt))))

Solution (Python):
import sys
from itertools import accumulate, islice

n, m, q = map(int, input().split())
ipt = (map(int, line.split()) for line in sys.stdin.readlines())
rails = [[0] * n for _ in range(n)]
for l, r in islice(ipt, m):
    rails[l - 1][r - 1] += 1
rails = [list(accumulate(reversed(s))) for s in zip(*(accumulate(s) for s in rails))]
print('\n'.join(str(rails[q - 1][n - p]) for p, q in ipt))

Solution (Python):
from collections import Counter
from itertools import product

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i


for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])


for (p,q) in qs:
    ans = 0
    for i in range(p-1,q):
        ans = ans+sumlist[i][q]-sumlist[i][p-1]
    print(ans)