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):
import sys
input = sys.stdin.readline

N, M, Q = [int(x) for x in input().split()]
L = [0] * M
R = [0] * M
p = [0] * Q
q = [0] * Q
for i in range(M):
    L[i], R[i] = [int(x) for x in input().split()]
for j in range(Q):
    p[j], q[j] = [int(x) for x in input().split()]

train = [[0 for i in range(N + 1)] for _ in range(N + 2)]

for i in range(M): 
    train[L[i]][R[i]] += 1

for col in range(1, N + 1):
    for row in range(col, 0, -1):
        train[row][col] += train[row][col - 1] + train[row + 1][col] - train[row + 1][col - 1]

for j in range(Q):
    print(train[p[j]][q[j]])

Solution (Python):
import sys
input = sys.stdin.readline

N, M, Q = [int(x) for x in input().split()]
L = [0] * M
R = [0] * M
p = [0] * Q
q = [0] * Q
for i in range(M):
    L[i], R[i] = [int(x) for x in input().split()]
for j in range(Q):
    p[j], q[j] = [int(x) for x in input().split()]

train = [[0 for i in range(N + 1)] for _ in range(N + 1)]
seg = [[0 for i in range(N + 1)] for _ in range(N + 2)]

for i in range(M): 
    train[L[i]][R[i]] += 1

for col in range(1, N + 1):
    for row in range(col, 0, -1):
        seg[row][col] = train[row][col] + seg[row][col - 1] + seg[row + 1][col] - seg[row + 1][col - 1]

for j in range(Q):
    print(seg[p[j]][q[j]])

Solution (Python):
N, M, Q = [int(x) for x in input().split()]
L = [0] * M
R = [0] * M
p = [0] * Q
q = [0] * Q
for i in range(M):
    L[i], R[i] = [int(x) for x in input().split()]
for j in range(Q):
    p[j], q[j] = [int(x) for x in input().split()]

train = [[0 for i in range(N + 1)] for _ in range(N + 1)]
seg = [[0 for i in range(N + 1)] for _ in range(N + 2)]

for i in range(M): 
    train[L[i]][R[i]] += 1

for col in range(1, N + 1):
    for row in range(col, 0, -1):
        seg[row][col] = train[row][col] + seg[row][col - 1] + seg[row + 1][col] - seg[row + 1][col - 1]

for j in range(Q):
    print(seg[p[j]][q[j]])

Solution (Python):
N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if i == 0:
            r[i][j] = p[i][j] + r[i][j-1]      
        elif j == 0:
            r[i][j] = p[i][j] +r[i-1][j]
        else:
            r[i][j] = r[i-1][j] + r[i][j-1] - r[i-1][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    if Qlist[i][0] == 1:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1]
    else:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1] - r[Qlist[i][0]-2][Qlist[i][1]-1]
    print(b)

Solution (Python):
import itertools as itr

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

	cnt = [[0 for _ in range(N+10)] for _ in range(N+10)]
	for L, R in LR:
		cnt[L][R] += 1
	
	for i, j in itr.product(range(N+1), repeat = 2):
		cnt[i+1][j] += cnt[i][j]
	for i, j in itr.product(range(N+1), repeat = 2):
		cnt[i][j+1] += cnt[i][j]

	for p, q in pq:
		print( cnt[q][q] - cnt[p-1][q] - cnt[q][p-1] + cnt[p-1][p-1] )

	return


main()

Solution (Python):
from collections import Counter

n,m,q = map(int,input().split())
c = [[0] * (n+1) for i in range(n+1)]
da = [[0] * (n+1) for i in range(n+1)]
for i in range(m):
    l,r = map(int,input().split())
    c[l][r] += 1

da[1][1] = c[1][1]
        
for i in range(2,n+1):
    da[1][i] = da[1][i-1] + c[1][i]    
for i in range(2,n+1):
    co = 0
    for j in range(1,n+1):
        co += c[i][j]
        da[i][j] = da[i-1][j] + co
    
for i in range(q):
    pp,qq =  map(int,input().split())
    ans = 0
    ans = da[qq][qq] - da[pp-1][qq] - da[qq][pp-1] + da[pp-1][pp-1]
    
    print(ans)

Solution (Python):

from itertools import accumulate
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M,Q,*lr = map(int, read().split())

    LR = [[0]*(N+1) for _ in range(N+1)]
    query = []
    for i, (l, r) in enumerate(zip(*[iter(lr)]*2)):
        if i < M:
            LR[l][r] += 1
        else:
            query.append((l, r))
    
    for i in range(1,N+1):
        LR[1][i] += LR[1][i-1]
        LR[i][1] += LR[i-1][1]
    
    for i in range(2, N+1):
        for j in range(2,N+1):
            LR[i][j] += LR[i-1][j] + LR[i][j-1] - LR[i-1][j-1]
    
    for p, q in query:
        ans = LR[q][q] - LR[p-1][q] - LR[q][p-1] + LR[p-1][p-1]
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

from itertools import accumulate
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M,Q,*lr = map(int, read().split())

    LR = [[0]*(N+1) for _ in range(N+1)]
    query = []
    for i, (l, r) in enumerate(zip(*[iter(lr)]*2)):
        if i < M:
            LR[l][r] += 1
        else:
            query.append((l, r))
    
    for i in range(1,N+1):
        LR[1][i] += LR[1][i-1]
        LR[i][1] += LR[i-1][1]
    
    for i in range(2, N+1):
        for j in range(2,N+1):
            LR[i][j] += LR[i-1][j] + LR[i][j-1] - LR[i-1][j-1]
    
    for p, q in query:
        ans = LR[q][q] - LR[p-1][q] - LR[q][p-1] + LR[p-1][p-1]
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline
import numpy as np

def main():
    N,M,Q = map(int,input().split())
    cum = np.zeros((N+1,N+1),dtype=int)
    
    for i in range(M):
        l,r = map(int,input().split())
        cum[l,r] += 1

    cum = np.cumsum(np.cumsum(cum,axis=1),axis=0)
    
    for _ in range(Q):
        p,q = map(int,input().split())
        print(cum[q,q]-cum[p-1,q]-cum[q,p-1]+cum[p-1,p-1])

if __name__ == "__main__":
    main()

Solution (Python):

from itertools import accumulate
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M,Q,*lr = map(int, read().split())

    LR = [[0]*(N+1) for _ in range(N+1)]
    query = []
    for i, (l, r) in enumerate(zip(*[iter(lr)]*2)):
        if i < M:
            LR[l][r] += 1
        else:
            query.append((l, r))
    
    LR_acc = []
    for L in LR:
        LR_acc.append(list(accumulate(L)))
    
    for p, q in query:
        ans = 0
        for i in range(p,q+1):
            ans += LR_acc[i][q] - LR_acc[i][p-1]
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
N, M, Q = map(int, input().split())
num = [[0]*500 for _ in range(500)]

for i in range(M):
  L,R = map(int, input().split())
  num[R-1][L-1] += 1

cum = [[0]*500 for _ in range(500)]
for r in range(500):
  cum[r][r] = num[r][r]
for r in range(1,500):
  for l in range(r-1,-1,-1):
    cum[r][l] = cum[r-1][l]+cum[r][l+1]-cum[r-1][l+1]+num[r][l]

ans = []
for i in range(Q):
  P,Q = map(int, input().split())
  ans.append(cum[Q-1][P-1])
print(*ans,sep='\n')

Solution (Python):
N, M, Q = map(int, input().split())
num = [[0]*500 for _ in range(500)]

for i in range(M):
  L,R = map(int, input().split())
  num[R-1][L-1] += 1

cum = [[0]*500 for _ in range(500)]
for r in range(500):
  cum[r][r] = num[r][r]
for r in range(1,500):
  for l in range(r-1,-1,-1):
    cum[r][l] = cum[r-1][l]+cum[r][l+1]-cum[r-1][l+1]+num[r][l]

ans = []
for i in range(Q):
  P,Q = map(int, input().split())
  ans.append(cum[Q-1][P-1])
print(*ans,sep='\n')

Solution (Python):
n, m, k = map(int, input().split())
R = [[0]*n for _ in range(n)]
for _ in range(m):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  R[r][l] += 1

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


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

Solution (Python):
n, m, k = map(int, input().split())
R = [[0]*n for _ in range(n)]
for _ in range(m):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  R[r][l] += 1

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


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

Solution (Python):
NN = 202020
MOD = 10**9+7
INF = float("inf")


n, m, q = map(int, input().split())
train = [list(map(int, input().split())) for _ in range(m)]
query = [list(map(int, input().split())) for _ in range(q)]

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

for i in range(m):
    trains[train[i][0]][train[i][1]] += 1

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



for i in range(q):
    start, end = query[i]
    ans = cum[end][end] - cum[end][start-1] - cum[start-1][end] + cum[start-1][start-1]
    print(ans)

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

for q in range(n):
    for p in reversed(range(1, n)):
        M[q][p-1] += M[q][p]
for p in range(n):
    for q in range(n-1):
        M[q+1][p] += M[q][p]

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

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

for q in range(n):
    for p in reversed(range(1,n)):
        M[q][p-1]+=M[q][p]
for p in range(n):
    for q in range(n-1):
        M[q+1][p]+=M[q][p]        

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

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

for q in range(n):
    for p in reversed(range(1,n)):
        M[q][p-1]+=M[q][p]
for p in range(n):
    for q in range(n-1):
        M[q+1][p]+=M[q][p]        

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

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

Solution (Python):
n,m,q=map(int,input().split())
ans=[[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    l,r=map(int,input().split())
    ans[l][r]+=1

for l in range(2,n+1):
    for i in range(1,n+1):
        j=i+l-1
        if j>n or i+1>n:
            continue
        if i+1<=j-1:
            ans[i][j]+=ans[i][j-1]+ans[i+1][j]-ans[i+1][j-1]
        else:
            ans[i][j]+=ans[i][j-1]+ans[i+1][j]

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

Solution (Python):
import sys
from collections import defaultdict

input=sys.stdin.readline

N,M,Q=map(int,input().split())
rail=defaultdict(int)
for i in range(0,M):
    l,r=map(int,input().split())
    rail[(l,r)]+=1


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

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

ans=[[0 for i in range(0,N)] for j in range(0,N)]

for i in range(0,N):
    ans[i][i]=dp[i][i]

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

x=[]
for i in range(0,Q):
    p,q=map(int,input().split())
    x.append(ans[p-1][q-1])

for i in range(0,Q):
    print(x[i])

Solution (Python):
n,m,q=map(int,input().split())
line=[[0]*(n+1) for i in range(n+1)]
for _ in range(m):
  l,r=map(int,input().split())
  line[l][r]+=1
for i in range(n+1):
  for j in range(n):
    line[i][j+1]+=line[i][j]
for i in range(n+1):
  for j in range(n):
    line[j+1][i]+=line[j][i]
for _ in range(q):
  l,r=map(int,input().split())
  print(line[r][r]-line[r][l-1]-line[l-1][r]+line[l-1][l-1])

Solution (Python):
class BIT_2D():
    def __init__(self,h,w):
        self.h=h
        self.w=w 
        self.table=[[0]*(w+1) for _ in range(h+1)]

    def add(self,i,j,x):
        init_j=j
        while i<=self.h:
            while j<=self.w:
                self.table[i][j]+=x
                j+=(j&-j)
            j=init_j
            i+=(i&-i)
        return None

    def sum(self,i,j):
        s=0
        init_j=j
        while i>0:
            while j>0:
                s+=self.table[i][j]
                j-=(j&-j)
            j=init_j
            i-=(i&-i)
        return s
      
n,m,q=map(int,input().split())
bit2d=BIT_2D(n,n)
for i in range(m):
  i,j=map(int,input().split())
  bit2d.add(i,j,1)
for i in range(q):
  i,j=map(int,input().split())
  ans=bit2d.sum(j,j)-bit2d.sum(j,i-1)-bit2d.sum(i-1,j)+bit2d.sum(i-1,i-1)
  print(ans)

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

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

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

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

Solution (Python):



import numpy

def main():
  n, m, q = map(int, input().split())
  counts = numpy.zeros((n+1, n+1), dtype=numpy.int)
  for _ in range(m):
    l, r = map(int, input().split())
    counts[l, r] += 1
  
  cusum = counts.cumsum(0).cumsum(1)
  for _ in range(q):
    p, q = map(int, input().split())
    
    if p-1 < 1:
      print(cusum[q, q])
    else:
      print(cusum[q, q] - cusum[p-1, q] - cusum[q, p-1] + cusum[p-1, p-1])

if __name__=='__main__':
  main()

Solution (Python):



import numpy

def main():
  n, m, q = map(int, input().split())
  counts = numpy.zeros((n+1, n+1), dtype=numpy.int)
  for _ in range(m):
    l, r = map(int, input().split())
    counts[l, r] += 1
  
  cusum = counts.cumsum(0).cumsum(1)
  for _ in range(q):
    p, q = map(int, input().split())
    
    if p-1 < 1:
      print(cusum[q, q])
    else:
      print(cusum[q, q] - cusum[p-1, q] - cusum[q, p-1] + cusum[p-1, p-1])

if __name__=='__main__':
  main()

Solution (Python):



import numpy

def main():
  n, m, q = map(int, input().split())
  counts = numpy.zeros((n, n), dtype=numpy.int)
  llr = [], []
  for _ in range(m):
    l, r = map(int, input().split())
    counts[l-1, r-1] += 1
  
  cusum = counts.cumsum(0).cumsum(1)
  for _ in range(q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    
    if p-1 < 0:
      print(cusum[q, q])
    else:
      print(cusum[q, q] - cusum[p-1, q] - cusum[q, p-1] + cusum[p-1, p-1])

if __name__=='__main__':
  main()

Solution (Python):
import numpy as np
N,M,Q = map(int,input().split())


table = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    table[l][r]+=1


table = np.array(table)
table = table.cumsum(axis=0).cumsum(axis=1)

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

Solution (Python):



import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


class cumsum2d:  
    def __init__(self, ls: list):
        '''
        2次元のリストを受け取る
        '''
        from itertools import product
        H = len(ls)
        W = len(ls[0])
        self.ls_accum = [[0] * (W + 1)]
        for l in ls:
            self.ls_accum.append([0] + l)

        
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i - 1][j]
        
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i][j - 1]

    def total(self, i1, j1, i2, j2):
        '''
        点(i1,j1),(i1,j2),(i2,j1),(i2,j2)の4点が成す四角の中の合計を取り出す
        ただし i1<=i2, j1<=j2
        ただし、i軸に関しては[i1,i2),j軸に関しては[j1,j2)の半開区間である
        '''
        return self.ls_accum[i2][j2] - self.ls_accum[i1][j2] \
            - self.ls_accum[i2][j1] + self.ls_accum[i1][j1]


N, M, Q = read_ints()


table = [[0] * N for _ in range(N)]  
for _ in range(M):
    L, R = read_ints()
    table[L - 1][R - 1] += 1


table = cumsum2d(table)


for _ in range(Q):
    p, q = read_ints()
    p -= 1
    q -= 1
    print(table.total(p, p, q + 1, q + 1))

Solution (Python):



import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, M, Q = read_ints()


table = [[0] * N for _ in range(N)]  
for _ in range(M):
    L, R = read_ints()
    table[L - 1][R - 1] += 1


import numpy as np
table_ = np.array(table)
table = np.zeros((N + 1, N + 1), dtype='int')
table[1:, 1:] = table_.cumsum(axis=0).cumsum(axis=1)



for _ in range(Q):
    p, q = read_ints()
    print(table[q, q] - table[p - 1, q] -
          table[q, p - 1] + table[p - 1, p - 1])

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    N, M, Q = map(int, input().split())
    L = [0]*M
    R = [0]*M
    p = [0]*Q
    q = [0]*Q
    for i in range(M):
        L[i], R[i] = map(int, input().split())
    for i in range(Q):
        p[i], q[i] = map(int, input().split())

    temp = [[0]*N for _ in range(N)]
    
    s = [[0]*(N+1) for _ in range(N)]
    for m in range(M):
        temp[L[m]-1][R[m]-1] += 1
    for i in range(N):
        for j in range(N):
            s[i][j+1] = s[i][j] + temp[i][j]

    for i in range(Q):
        ans = 0
        for j in range(p[i]-1, q[i]):
            ans += s[j][q[i]]-s[j][p[i]-1]
        print(ans)

if __name__ == '__main__':
    resolve()

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

xmat,cmat=[],[]
for i in range(N+1):
  xmat.append([0]*(N+1))
  cmat.append([0]*(N+1))

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


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


for i in range(Q):
  p,q=map(int,input().split())
  ans=0
  for k in range(p,q+1):
    ans+=cmat[k][q]-cmat[k][p-1]
  print(ans)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import accumulate

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

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

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

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

for _ in range(Q):
    p,q = map(int, input().split())

    print(train[q][q] - train[p-1][q] - train[q][p-1] + train[p-1][p-1])

Solution (Python):
n, m, q = [int(i) for i in input().split()]

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

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

for i in range(n + 1):
    for j in range(n):
        a[i][j + 1] += a[i][j]
for i in range(n + 1):
    for j in range(n):
        a[j + 1][i] += a[j][i]

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

Solution (Python):



N, M, Q = list(map(int, input().split()))
LR = [[0] * 501 for _ in range(501)]
for _ in range(M):
    l, r = list(map(int, input().split()))
    LR[l][r] += 1
pq = [list(map(int, input().split())) for _ in range(Q)]


def main():
    dp = [[0] * 501 for _ in range(501)]
    for i in range(1, 501):
        for j in range(1, 501):
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + LR[i][j]
    
    for p, q in pq:
        ans = dp[q][q] - dp[q][p-1] - dp[p-1][q] + dp[p-1][p-1]
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
def f(h,w,a):
    da = [[0]*(w+1)for _ in range(h+1)]
    da[0][0] = a[0][0]
    for i in range(1, w+1):
        da[0][i] = da[0][i-1] + a[0][i]
    for i in range(1, h+1):
        cnt_w = 0
        for j in range(w+1):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j] + cnt_w
    return da

def Calc(p,q,x,y, da):
    if p>x  or q>y:
        return 0
    if p==0 or q==0:
        return da[x][y]
    if p==0:
        return da[x][y] - da[x][q-1]
    if q==0:
        return da[x][y] - da[p-1][y]
    return da[x][y] - da[x][q-1] - da[p-1][y] + da[p-1][q-1]

N,M,Q = map(int,input().split())
t = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l,r = map(int,input().split())
    t[l][r] += 1

d = f(N,N,t)
for _ in range(Q):
    p,q = map(int,input().split())
    print(Calc(p,p,q,q,d))

Solution (Python):
n,m,Q = map(int,input().split())
D = [[0]*(n+1) for _ in range(n+1)]

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

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

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

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

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

Solution (Python):
import numpy as np
N,M,Q = map(int,input().split())
grid = np.zeros((N+1,N+1))
for _ in range(M):
    l,r = map(int,input().split())
    grid[l,r] += 1

grid = grid.cumsum(axis=0).cumsum(axis=1)

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

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

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

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


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

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

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

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

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

for i in range(Q):
    L, R = map(int, input().split())
    ans = sum[R][R]
    ans -= sum[R][L - 1]
    ans -= sum[L - 1][R]
    ans += sum[L - 1][L - 1]
    print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n, m, Q = [int(x) for x in input().split()]

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

for _ in range(m):
    l, r = [int(x) for x in input().split()]
    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 _ in range(Q):
    p, q = [int(x) for x in input().split()]
    res = 0
    for i in range(p, n + 1):
        res += table[i][q]
    print(res)

Solution (Python):
n,m,q=map(int,input().split())
a=[[0]*n for _ in range(n)]
for _ in range(m):
  l,r=map(int,input().split())
  l-=1
  r-=1
  a[l][r]+=1

def da_generate(h,w,a):
    da = [[0]*w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1,w):
        da[0][i] = da[0][i-1]+a[0][i]
    for i in range(1,h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j]+cnt_w
    return da


def da_calc(p,q,x,y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y]-da[x][q-1]
    if q == 0:
        return da[x][y]-da[p-1][y]
    return da[x][y]-da[p-1][y]-da[x][q-1]+da[p-1][q-1]
da=da_generate(n,n,a)
for _ in range(q):
  p,q=map(int,input().split())
  p-=1
  q-=1
  print(da_calc(p,p,q,q))

Solution (Python):
def main():
    N, M, Q, *X = map(int, open(0).read().split())
    L = [0]*M
    R = [0]*M
    p = [0]*Q
    q = [0]*Q
    for i in range(M):
        L[i], R[i] = X[2*i], X[2*i + 1]
    for i in range(Q):
        p[i], q[i] = X[2*M + 2*i], X[2*M + 2*i + 1]
    
    S = [[0]*(N+1) for i in range(N+1)]
    for i in range(M):
        S[L[i]][R[i]] += 1
    
    
    S2 = [[0]*(N+1) for i in range(N+1)]
    for i in range(N+1):
        S2[i][0] = S[i][0]
        for j in range(1, N+1):
            S2[i][j] = S2[i][j-1] + S[i][j]
    
    
    S3 = [[0]*(N+1) for i in range(N+1)]
    for i in range(N+1):
        S3[0][i] = S2[0][i]
        for j in range(1, N+1):
            S3[j][i] = S3[j-1][i] + S2[j][i]
    for i in range(Q):
        pi, qi = p[i], q[i]
        ans = S3[qi][qi] - S3[qi][pi-1]
        ans -= S3[pi-1][qi] - S3[pi-1][pi-1]
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
    N, M, Q, *X = map(int, open(0).read().split())
    L = [0]*M
    R = [0]*M
    p = [0]*Q
    q = [0]*Q
    for i in range(M):
        L[i], R[i] = X[2*i], X[2*i + 1]
    for i in range(Q):
        p[i], q[i] = X[2*M + 2*i], X[2*M + 2*i + 1]
    
    S = [[0]*(N+1) for i in range(N+1)]
    for i in range(M):
        S[L[i]][R[i]] += 1
    
    
    S2 = [[0]*(N+1) for i in range(N+1)]
    for i in range(N+1):
        S2[i][0] = S[i][0]
        for j in range(1, N+1):
            S2[i][j] = S2[i][j-1] + S[i][j]
    
    
    for i in range(Q):
        pi, qi = p[i], q[i]
        ans = 0
        for j in range(pi, qi + 1):
            ans += (S2[j][qi] - S2[j][pi-1])
        print(ans)

if __name__ == '__main__':
    main()

Solution (Python):
import itertools

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

tr = [[0]*n for _ in range(n)]

for i in range(m):
    l, r = map((lambda x:int(x)-1), input().split())
    tr[l][r] += 1

for i in range(n):
    tr[i] = list(itertools.accumulate(tr[i]))

for i in range(q):
    p, q = map((lambda x:int(x)-1), input().split())
    ans = 0
    for j in tr[p:q+1]:
        ans += (j[q] - j[p-1]) if p>0 else j[q]

    print(ans)

Solution (Python):
n, m, q = map(int, input().split())
trains = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    trains[l][r] += 1

for i in range(n):
    for j in range(n):
        trains[i][j + 1] += trains[i][j]
for i in range(n):
    for j in range(n):
        trains[i + 1][j + 1] += trains[i][j + 1]

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

Solution (Python):
N,M,Q=map(int,input().split())
A=[[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
  L,R=map(int,input().split())
  A[L][R]+=1
  
for i in range(1,N+1):
  for j in range(1,N+1):
    A[i][j]+=A[i][j-1]
for i in range(1,N+1):
  for j in range(1,N+1):
    A[i][j]+=A[i-1][j]

for i in range(Q):
  L,R=map(int,input().split())
  ans=A[R][R]-A[L-1][R]-A[R][L-1]+A[L-1][L-1]
  print(ans)

Solution (Python):
N,M,Q=map(int,input().split())
A=[[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
  L,R=map(int,input().split())
  A[L][R]+=1
  
for i in range(1,N+1):
  for j in range(1,N+1):
    A[i][j]+=A[i][j-1]
for i in range(1,N+1):
  for j in range(1,N+1):
    A[i][j]+=A[i-1][j]

for i in range(Q):
  L,R=map(int,input().split())
  ans=A[R][R]-A[L-1][R]-A[R][L-1]+A[L-1][L-1]
  print(ans)

Solution (Python):
N,M,Q=map(int,input().split())
L,R=[],[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i][j-1]
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i-1][j]
for i in range(Q):
  ans=c[Ql[i]][Ql[i]]-c[Pl[i]-1][Ql[i]]-c[Ql[i]][Pl[i]-1]+c[Pl[i]-1][Pl[i]-1]
  print(ans)

Solution (Python):
n, m, q = map(int, input().split())
cities = [[0] * (n + 1) for _ in range(n + 1)]
trains = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    trains[l][r] += 1

for i in range(n):
    for j in range(n):
        cities[i + 1][j + 1] = cities[i + 1][j] + trains[i + 1][j + 1]
for _ in range(q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q + 1):
        ans += cities[i][q] - cities[i][p - 1]
    print(ans)