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 bisect
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)]

lr.sort()
t=[[0 for _ in range(n)] for _ in range(n)]

for slr in lr:
    t[slr[0]-1][slr[1]-1] += 1

nt = [[0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        nt[i].append(nt[i][j] + t[i][j])

for spq in pq:
    p,q = spq[0],spq[1]
    res = 0
    for i in range(p-1,q):
        res += nt[i][q] - nt[i][p-1]
    print(res)

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class SegmentTree(object):
    def __init__(self,A,dot,e):
        n=2**((len(A)-1).bit_length())
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__node=[e]*(2*n)
        for i in range(len(A)):
            self.__node[i+n]=A[i]
        for i in range(n-1,-0,-1):
            self.__node[i]=dot(self.__node[2*i],self.__node[2*i+1])

    def add(self,i,c):
        i+=self.__n
        node=self.__node
        node[i]=self.__dot(node[i],c)
        while(i!=1):
            i//=2
            node[i]=self.__dot(node[2*i],node[2*i+1])

    def sum(self,l,r):
        vl,vr=self.__e,self.__e
        l+=self.__n; r+=self.__n
        while(l<r):
            if(l%2==1):
                vl=self.__dot(vl,self.__node[l])
                l+=1
            l//=2
            if(r%2==1):
                r-=1
                vr=self.__dot(self.__node[r],vr)
            r//=2
        return self.__dot(vl,vr)

def resolve():
    n,m,Q=map(int,input().split())
    X=[0]*(m+Q)
    for i in range(m):
        l,r=map(int,input().split())
        l-=1; r-=1
        X[i]=(0,l,r,i)
    for i in range(Q):
        l,r=map(int,input().split())
        l-=1; r-=1
        X[m+i]=(1,l,r,i)
    X.sort(lambda x:(x[2],x[0])) 

    from operator import add
    tree=SegmentTree([0]*n,add,0)
    ans=[0]*Q
    for x,l,r,i in X:
        if(x==0):
            tree.add(l,1)
        else:
            ans[i]=tree.sum(l,r+1)

    for a in ans: print(a)
resolve()

Solution (Python):
"""
22:40:00

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

fields = [[0] * (N+1) for i in range(N+1)]
accs = [[0] * (N+1) for i in range(N+1)]

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

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

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    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
    S=[[0]*(n+1) for _ in range(n+1)]
    from itertools import product
    for i,j in product(range(n),repeat=2):
        S[i+1][j+1]=A[i][j]+S[i][j+1]+S[i+1][j]-S[i][j]
    for _ in range(q):
        l,r=map(int,input().split())
        print(S[r][r]-S[l-1][r]-S[r][l-1]+S[l-1][l-1])
resolve()

Solution (Python):
import itertools
import numpy as np
n,m,q=map(int, input().split())  
a=[list(map(int, input().split())) for i in range(m)]
b=[list(map(int, input().split())) for i in range(q)]

x=[[0]*(501) for i in range(501)]
x=np.array(x)
for i in range(m):
    x[a[i][0],a[i][1]]+=1



for i in range(501):
    x[i] = list(itertools.accumulate(x[i]))
  
for i in range(501):
    x[:,i] = list(itertools.accumulate(x[:,i]))



for i in range(q):
    print(x[b[i][1],b[i][1]]-x[b[i][1],b[i][0]-1]-x[b[i][0]-1,b[i][1]]+x[b[i][0]-1,b[i][0]-1])

Solution (Python):
import numpy as np
import sys

n, m, q = map(int, input().split())
ab = np.array(sys.stdin.read().split(), np.int)
a = ab[:m*2].reshape(m, 2)
b = ab[m*2:].reshape(q, 2)

x=np.zeros((501, 501), dtype=np.int)

np.add.at(x, (a[:, 0], a[:, 1]), 1)

np.cumsum(x, axis=0, out=x)
np.cumsum(x, axis=1, out=x)

ans = x[b[:, 1], b[:, 1]] - x[b[:, 1], b[:, 0]-1] - x[b[:, 0]-1, b[:, 1]] + x[b[:, 0]-1, b[:, 0]-1]
for i in range(q):
    print(ans[i])

Solution (Python):
import numpy as np
import sys

n, m, q = map(int, input().split())
ab = np.array(sys.stdin.read().split(), np.int)
a = ab[:m*2].reshape(m, 2)
b = ab[m*2:].reshape(q, 2)

x=np.zeros((501, 501), dtype=np.int)

np.add.at(x, (a[:, 0], a[:, 1]), 1)

np.cumsum(x, axis=0, out=x)
np.cumsum(x, axis=1, out=x)

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2, v2]
    a2=x[v2, v1-1]
    a3=x[v1-1, v2]
    a4=x[v1-1, v1-1]
    print(a1-a2-a3+a4)

Solution (Python):
import numpy as np

n,m,q=map(int, input().split())  
a=np.array([list(map(int, input().split())) for i in range(m)])
b=[list(map(int, input().split())) for i in range(q)]

x=np.zeros((501, 501), dtype=np.int)

np.add.at(x, (a[:, 0], a[:, 1]), 1)

np.cumsum(x, axis=0, out=x)
np.cumsum(x, axis=1, out=x)

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2, v2]
    a2=x[v2, v1-1]
    a3=x[v1-1, v2]
    a4=x[v1-1, v1-1]
    print(a1-a2-a3+a4)

Solution (Python):
import numpy as np

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

x=np.zeros((501, 501), dtype=np.int)

for i in range(m):
    x[a[i][0], a[i][1]]+=1

np.cumsum(x, axis=0, out=x)
np.cumsum(x, axis=1, out=x)

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2, v2]
    a2=x[v2, v1-1]
    a3=x[v1-1, v2]
    a4=x[v1-1, v1-1]
    print(a1-a2-a3+a4)

Solution (Python):
import numpy as np

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

x=np.zeros((501, 501), dtype=np.int)

for i in range(m):
    x[a[i][0], a[i][1]]+=1

x = np.cumsum(x, axis=0)
x = np.cumsum(x, axis=1)

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2, v2]
    a2=x[v2, v1-1]
    a3=x[v1-1, v2]
    a4=x[v1-1, v1-1]
    print(a1-a2-a3+a4)

Solution (Python):
import itertools
import numpy as np
n,m,q=map(int, input().split())  
a=[list(map(int, input().split())) for i in range(m)]
b=[list(map(int, input().split())) for i in range(q)]

x=[[0]*(501) for i in range(501)]

for i in range(m):
    x[a[i][0]][a[i][1]]+=1



for i in range(501):
    x[i] = list(itertools.accumulate(x[i]))
  
x=np.array(x)
for i in range(501):
    x[:,i] = list(itertools.accumulate(x[:,i]))



for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2,v2]
    a2=x[v2,v1-1]
    a3=x[v1-1,v2]
    a4=x[v1-1,v1-1]
    print(a1-a2-a3+a4)

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

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

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

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

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

N,M,Q = map(int,readline().split())
lines = readlines()
L,R = np.array([line.split() for line in lines[:M]],np.int32).T
P,Q = np.array([line.split() for line in lines[M:]],np.int32).T

cnt = np.zeros((N+1,N+1),dtype=np.int32)
np.add.at(cnt,(L,R),1)

np.cumsum(cnt,axis=0,out=cnt)
np.cumsum(cnt,axis=1,out=cnt)
P -= 1
x = cnt[Q,Q] - cnt[Q,P] - cnt[P,Q] + cnt[P,P]
print(*x,sep="\n")

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

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


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

Solution (Python):


import numpy as np
import sys

N, M, Q = map(int, sys.stdin.buffer.readline().split())
LRpq = np.array(sys.stdin.buffer.read().split(), np.int64)
L = LRpq[:2*M:2]
R = LRpq[1:2*M:2]
p = LRpq[2*M::2]
q = LRpq[2*M+1::2]
    
train = np.zeros((N+1, N+1))
np.add.at(train, (L,R), 1)

np.cumsum(train, axis = 0, out = train)
np.cumsum(train, axis = 1, out = train)
    
ans = train[q,q] - train[p-1,q] - train[q,p-1] + train[p-1,p-1]
for i in range(Q):
    print(int(ans[i]))

Solution (Python):


import numpy as np
import sys

N, M, Q = map(int, input().split())
LRpq = np.array(sys.stdin.read().split(), np.int64)
L = LRpq[:2*M:2]
R = LRpq[1:2*M:2]
p = LRpq[2*M::2]
q = LRpq[2*M+1::2]
    
train = np.zeros((N+1, N+1))
np.add.at(train, (L,R), 1)

np.cumsum(train, axis = 0, out = train)
np.cumsum(train, axis = 1, out = train)
    
ans = train[q,q] - train[p-1,q] - train[q,p-1] + train[p-1,p-1]
for i in range(Q):
    print(int(ans[i]))

Solution (Python):


import numpy as np

N, M, Q = map(int, input().split())
LR = np.zeros((N+1, N+1))

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

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

Solution (Python):

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

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

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

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

    """
    C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
    C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
    """
    C =  [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = C[i][j-1] + X[i][j]


    """
    print("---------------")
    for a in C:
        print(a)
    """

    for p,q in query:
        cnt = 0
        for r in range(p-1,q):
            cnt += C[r][q-1]
        print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):

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

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

    query = [tuple(map(int, input().split())) for _ in range(Q)]

    """
    C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
    C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
    """
    C =  [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = C[i][j-1] + X[i][j]


    """
    print("---------------")
    for a in C:
        print(a)
    """

    for p,q in query:
        cnt = 0
        for r in range(p-1,q):
            cnt += C[r][q-1]
        print(cnt)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
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)]
x=[[0]*n for i in range(n)]
for i in range(m):
    x[lr[i][0]-1][lr[i][1]-1]+=1

rui=[[0]*(n+1) for i in range(n+1)]
for i in range(n):
    for j in range(n):
        rui[i+1][j+1]=rui[i][j+1]+rui[i+1][j]-rui[i][j]+x[i][j]

for i in range(q):
    print(rui[pq[i][1]][pq[i][1]] - rui[pq[i][0]-1][pq[i][1]] - rui[pq[i][1]][pq[i][0]-1] + rui[pq[i][0]-1][pq[i][0]-1])

Solution (Python):
n,m,q=map(int,input().split())
s=[[0 for i in range(n+1)] for j in range(n+1)]

a=list()

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

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

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

for i in range(q):
  l,r=map(int,input().split())
  t = s[r][r] - s[l-1][r] - s[r][l-1] + s[l-1][l-1]
  a.append(t)

for i in range(q):
  print(a[i])

Solution (Python):
import numpy as np

def main():
	n, m, q, *L = map(int, open(0).read().split())
	lr = L[:2 * m]
	pq = L[2 * m:]
	arr = np.zeros((n + 1, n + 1), int)
	for l, r in zip(*[iter(lr)] * 2):
		arr[l, r] += 1
	arr = np.cumsum(arr, 0)
	arr = np.cumsum(arr, 1)
	for p, q in zip(*[iter(pq)] * 2):
		print(arr[q, q] - arr[p - 1, q] - arr[p, p - 1] + arr[p - 1, p - 1])


if __name__ == "__main__":
	main()

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

N, M, Q = map(int, buf.readline().split())
city = np.zeros((N + 1, N + 1), np.int32)
LRpq = np.array(buf.read().split(), np.int32)

L = LRpq[:2 * M:2]
R = LRpq[1:2 * M:2]
p = LRpq[2 * M::2]
q = LRpq[2 * M + 1::2]

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

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

N, M, Q = map(int, buf.readline().split())
city = np.zeros((N + 1, N + 1), np.int32)
LRpq = np.array(buf.read().split(), np.int32)

LR = LRpq[:2 * M]
L = LR[::2]
R = LR[1::2]

pq = LRpq[2 * M:]
p = pq[::2]
q = pq[1::2]

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

Solution (Python):
import numpy as np
import sys
line = sys.stdin.readlines()

N, M, Q = map(int, line[0].split())
city = np.zeros((N + 1, N + 1), dtype='int32')
L, R = np.array(list(map(str.split, line[1:M + 1])), np.int32).T
p, q = np.array(list(map(str.split, line[M + 1:])), np.int32).T

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

Solution (Python):
import numpy as np
import sys
readlines = sys.stdin.readlines()

N, M, Q = map(int, readlines[0].split())
city = np.zeros((N + 1, N + 1), dtype='int32')
L, R = np.array([i.split() for i in readlines[1:M + 1]], dtype='int32').T
p, q = np.array([i.split() for i in readlines[M + 1:]], dtype='int32').T

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

Solution (Python):
import numpy as np
import sys


def main():
    readlines = sys.stdin.readlines()

    N, M, Q = map(int, readlines[0].split())
    city = np.zeros((N + 1, N + 1), dtype=int)
    L, R = np.array([i.split() for i in readlines[1:M + 1]], dtype=int).T
    p, q = np.array([i.split() for i in readlines[M + 1:]], dtype=int).T

    np.add.at(city, (L, R), 1)
    np.cumsum(city, axis=0, out=city)
    np.cumsum(city, axis=1, out=city)

    p -= 1
    answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
    print('\n'.join(answer.astype(str)))


if __name__ == '__main__':
    main()

Solution (Python):
import numpy as np
import sys
readlines = sys.stdin.readlines()

N, M, Q = map(int, readlines[0].split())
city = np.zeros((N + 1, N + 1), dtype=int)
L, R = np.array([i.split() for i in readlines[1:M + 1]], dtype=int).T
p, q = np.array([i.split() for i in readlines[M + 1:]], dtype=int).T

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

Solution (Python):
import numpy as np
import sys
readlines = sys.stdin.readlines()

N, M, Q = map(int, readlines[0].split())
city = np.zeros((N + 2, N + 1), dtype=int)
L, R = np.array([i.split() for i in readlines[1:M + 1]], dtype=int).T
pq = [map(int, i.split()) for i in readlines[M + 1:]]

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

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

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

N, M, Q = map(int, input().split())
city = np.zeros((N + 2, N + 1), dtype=np.int)

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

np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

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

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

    N, M, Q = map(int, input().split())
    
    city = [[0] * (N + 1) for _ in range(N + 2)]

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

    city = np.array(city).reshape(N + 2, N + 1)
    np.cumsum(city, axis=0, out=city)
    np.cumsum(city, axis=1, out=city)

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

if __name__ == '__main__':
    main()

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

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

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

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

city = np.array(city).reshape(N + 2, N + 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

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

Solution (Python):
n,m,Q=map(int,input().split())
d=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    l,r=map(int,input().split())
    d[l][r]+=1
for i in range(1,n+1):
    for j in range(1,n+1):
        d[i][j]+=d[i][j-1]
pq=[list(map(int,input().split())) for i in range(Q)]
for u in pq:
    p,q=u
    ans=0
    for i in range(p,q+1):
        ans+=d[i][q]
    print(ans)

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

Solution (Python):
N, M, Q = [int(str) for str in input().strip().split()]
LR = [[int(str) for str in input().strip().split()] for _ in range(M)]
pq = [[int(str) for str in input().strip().split()] for _ in range(Q)]

LRmap = [[0] * N for _ in range(N)]
for l, r in LR:
    LRmap[l - 1][r - 1] += 1

sums = [[0] * (N + 1) for _ in range(N + 1)]
sums[0][0] = 0
for l in range(1, N + 1):
    for r in range(1, N + 1):
        sums[l][r] = sums[l - 1][r] + sums[l][r - 1] - sums[l - 1][r - 1] + LRmap[l - 1][r - 1]

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

Solution (Python):
from collections import  Counter
n,m,q=map(int,input().split())
h=[[0]*(n) for _ in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    l-=1
    r-=1
    h[n-1-l][r]+=1
ans=0
for i in range(n):
    for j in range(n-1):
        h[i][j+1] += h[i][j]
 
for j in range(n):
    for i in range(n-1):
        h[i+1][j] += h[i][j]

for i in range(q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(h[n-1-x][y])

Solution (Python):

def build_2dcum(A: "Array[Array[int]]") -> "Array[Array[int]]":
    from itertools import accumulate as acc

    return [list(acc(a)) for a in zip(*[acc(a) for a in A])]


def respond_2dcum(l: int, r: int, A: "Array[Array[int]]") -> int:
    return A[r][r] - A[l - 1][r] - A[r][l - 1] + A[l - 1][l - 1]


def main():
    
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    imos = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        imos[l][r] += 1
    imos = build_2dcum(imos)
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        x = respond_2dcum(p, q, imos)
        ans.append(x)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

from itertools import accumulate as acc


def main():
    
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    imos = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        imos[l][r] += 1
    imos = [list(acc(a[::-1]))[::-1] for a in zip(*[acc(a) for a in imos])]
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        ans.append(imos[q][p])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

from itertools import accumulate as acc


def main():
    
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    imos = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        imos[l][r] += 1
    imos = [list(acc(a)) for a in zip(*[acc(a) for a in imos])]
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        cur = imos[q][q] - imos[p - 1][q] - imos[q][p - 1] + imos[p - 1][q - 1]
        ans.append(cur)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

from itertools import accumulate as acc


def main():
    
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    rails = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        rails[l][r] += 1
    rails = [list(acc(a)) for a in rails]
    rails = [list(acc(a[::-1]))[::-1] for a in zip(*rails)]
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        ans.append(rails[q][p])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

from itertools import accumulate as acc


def main():
    
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    rails = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        rails[l][r] += 1
    rails = tuple(tuple(acc(a)) for a in rails)
    rails = tuple(tuple(acc(a[::-1]))[::-1] for a in zip(*rails))
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        ans.append(rails[q][p])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Solution (Python):

from itertools import accumulate as acc


def main():
    
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    rails = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        rails[l][r] += 1
    rails = [tuple(acc(a)) for a in rails]
    rails = [tuple(acc(a[::-1]))[::-1] for a in zip(*rails)]
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        ans.append(rails[q][p])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

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)]

Sumtable = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l,r in LR:
  Sumtable[l][r] += 1

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


for p,q in PQ:
  print(Sumtable[q][q] - Sumtable[p-1][q] - Sumtable[q][p-1] + Sumtable[p-1][p-1])

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

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

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

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

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

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

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

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

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

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

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

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

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

City = [[0]*N for i in range(N)]
Accum = [[0]*(N+1) for i in range(N+1)]

for train in Train:
  City[train[0]-1][train[1]-1] += 1

for i in range(N):
  for j in range(N):
    Accum[i+1][j+1] = Accum[i+1][j] + City[i][j]
for j in range(N):
  for i in range(N):
    Accum[i+1][j+1] += Accum[i][j+1]

for query in Query:
  print(
    Accum[query[1]][query[1]]
  - Accum[query[1]][query[0]-1]
  - Accum[query[0]-1][query[1]]
  + Accum[query[0]-1][query[0]-1]
    )

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

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

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

for _ in range(Q):
    l, r = map(int, input().split())
    res = 0
    for i in range(l, r+1):
        res += ans[i][r]
    print(res)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


def main():
	N, M, Q = MAP()
	LR = [LIST() for _ in range(M)]

	x = [[0]*N for _ in range(N)]
	for L, R in LR:
		x[L-1][R-1] += 1

	pq = [LIST() for _ in range(Q)]

	C = [[0]*N for _ in range(N)]

	for i in range(N):
		tmp = 0
		C[i] = list(accumulate(x[i]))

	for p, q in pq:
		p = p-1
		q = q-1
		ans = 0
		for i in range(p, q+1):
			if p-1 <= -1:
				ans += C[i][q]
			else:
				ans += C[i][q]-C[i][p-1]
		print(ans)

if __name__ == "__main__":
	main()

Solution (Python):
N,M,Q=map(int,input().split())
A=[[0 for y in range(N+2)] for x in range(N+2)]
for i in range(M):
    L,R=map(int,input().split())
    A[L][R]+=1
B=[[0 for y in range(N+2)] for x in range(N+2)]
for x in range(N+2):
    for y in range(N+1):
        B[x][y+1]=B[x][y]+A[x][y]
C=[[0 for y in range(N+2)] for x in range(N+2)]
for y in range(N+2):
    for x in range(N+1):
        C[x+1][y]=C[x][y]+B[x][y]
for i in range(Q):
    p,q=map(int,input().split())
    print(C[q+1][q+1]-C[p][q+1]-C[q+1][p]+C[p][p])

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

Solution (Python):
def getlist():
	return list(map(int, input().split()))


N, M, Q = getlist()
List = [[0] * (N + 1) for i in range(N + 1)]
for i in range(M):
	L, R = getlist()
	List[R][L] += 1


for i in range(N):
	for j in range(N + 1):
		List[i + 1][j] += List[i][j]
for i in range(N + 1):
	for j in range(N):
		List[i][j + 1] += List[i][j]


for i in range(Q):
	p, q = getlist()
	print(List[q][q] - List[q][p - 1])

Solution (Python):
import sys

input = sys.stdin.readline

n, m, q = map(int, input().split())
ls = [[0] * (n + 1) for _ in range(n + 1)]
for _ 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):
    l, r = map(int, input().split())
    print(ls[r][r] - ls[l - 1][r] - ls[r][l - 1] + ls[l - 1][l - 1])

Solution (Python):
import sys

input = sys.stdin.readline

n, m, q = map(int, input().split())
ls = [[0] * (n + 1) for _ in range(n + 1)]
for _ 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):
    l, r = map(int, input().split())
    print(ls[r][r] - ls[l - 1][r] - ls[r][l - 1] + ls[l - 1][l - 1])

Solution (Python):
import itertools
import sys

input = sys.stdin.readline

n, m, q = map(int, input().split())
ls = [[0] * n for _ in range(n)]
for _ in range(m):
    l, r = map(int, input().split())
    ls[l - 1][r - l] += 1
for i in range(n):
    ls[i] = list(itertools.accumulate(ls[i]))
for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    res = 0
    for i in range(r - l + 1):
        res += ls[l + i][r - l - i]
    print(res)