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):
N,M,Q = map(int,input().split())

data = []

for i in range(M):
    l,r = map(int, input().split())
    data.append((0,l-1,r-1,0))
for i in range(Q):
    l,r = map(int, input().split())
    data.append((1,l-1,r-1,i))

data.sort()
data.sort(key=lambda x:x[2])

n0 = 2**(N-1).bit_length()
segdata = [0]*(2*n0-1)

def add(k):
    k += n0-1
    segdata[k] += 1
    while k > 0:
        k = (k-1)//2
        segdata[k] += 1

def getsum(a,b,k=0,l=0,r=n0):
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return segdata[k]
    vl = getsum(a,b,2*k+1,l,(l+r)//2)
    vr = getsum(a,b,2*k+2,(l+r)//2, r)
    return vr + vl

ans = []

for q, a, b,i in data:
    if q:
        ans.append((i, getsum(a,b+1)))
    else:
        add(a)

ans.sort()
for i, j in ans:
    print(j)

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

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

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

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

Solution (Python):



import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))




def main_lte(N, M, Q, LRm, PQq):
    for p, q in PQq:
        ans = 0
        for l, r in LRm:
            if p <= l and r <= q:
                ans += 1
        print(ans)

def main_lte2(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            for j in range(i, q+1):
                ans += table[i][j]
        print(ans)

def main_lte3(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    
    table2 = [[0] * (N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, N+1):
            table2[i][j] = table2[i][j-1] + table[i][j]
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            ans += table2[i][q] - table2[i][p-1]
        print(ans)

def main(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        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 i in range(1, N+1):
        for j in range(1, N+1):
            table[i][j] += table[i-1][j]
    for p, q in PQq:
        ans = table[q][q] + table[p-1][p-1] - table[p-1][q] - table[q][p-1]
        print(ans)

N, M, Q = i2nn()
LRm = ii2nnn(M)
PQq = ii2nnn(Q)
main(N, M, Q, LRm, PQq)

Solution (Python):
import numpy as np

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


trains = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for m in range(M):
    L, r = map(int, input().split())
    trains[L][r] += 1

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


def solve(L, r):
    
    
    return cumsum[r][r] - cumsum[r][L - 1] - cumsum[L - 1][r] + cumsum[L - 1][L - 1]


for q in range(Q):
    print(solve(*map(int, input().split())))

Solution (Python):
from functools import lru_cache

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


trains = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for m in range(M):
    L, r = map(int, input().split())
    trains[L][r] += 1














dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for length in range(N + 1):
    L = 1
    r = L + length
    while r <= N:
        if length == 0:
            dp[L][r] = trains[L][r]
        elif length == 1:
            dp[L][r] = dp[L][L] + dp[r][r] + trains[L][r]
        else:
            dp[L][r] = dp[L + 1][r] + dp[L][r - 1] - dp[L + 1][r - 1] + trains[L][r]
        L += 1
        r += 1


def solve(L, r):
    return dp[L][r]


for q in range(Q):
    print(solve(*map(int, input().split())))

Solution (Python):
N, M ,Q = map(int, input().split())
train = [list(map(int, input().split())) for i in range(M)]
qs = [list(map(int, input().split())) for i in range(Q)]
ns = []
for i in range(N+1):
    ns.append([0]*(N+1))
for l, r in train:
    for i in range(r, N+1):
        ns[l][i] += 1
for p, q in qs:
    ans = 0
    for i in range(p, q+1):
        ans += ns[i][q]
    print(ans)

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

import numpy as np
from itertools import combinations

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

for l, r in LR:
  trains[l-1][r-1] +=1
  
trains = np.array(trains)


row_sum = trains.cumsum(axis=1)
matrix_sum = row_sum.cumsum(axis=0)

answer = {}

for p,q in PQ:
  if (p,q) not in answer:
    if p==1:
      answer[(p,q)] = matrix_sum[q-1, q-1]
    else:
      answer[(p,q)] = matrix_sum[q-1,q-1] - matrix_sum[p-2,q-1]
  print(answer[(p,q)])

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

import numpy as np

trains = np.array([[0]*N for _ in range(N)])

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


row_sum = trains.cumsum(axis=1)
matrix_sum = row_sum.cumsum(axis=0)

for p,q in PQ:
  if p==1:
    print(matrix_sum[q-1, q-1])
  else:
    print(matrix_sum[q-1,q-1] - matrix_sum[p-2,q-1])

Solution (Python):

import sys
import pprint


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    mem = [[0] * N for i in range(N)]
    mem2 = [[0] * N for i in range(N)]
    for i in range(M):
        mem[L[i] - 1][R[i] - 1] += 1
    for h in range(N):
        for w in range(N):
            sum = mem[h][w]
            if h == 0 and w > 0:
                sum += mem2[h][w-1]
            elif w == 0 and h > 0:
                sum += mem2[h-1][w]
            elif h > 0 and w > 0:
                sum += mem2[h][w-1] + mem2[h-1][w] - mem2[h-1][w-1]
            mem2[h][w] = sum
    for i in range(Q):
        pc = p[i]-1
        qc = q[i]-1
        low = mem2[pc-1][qc] + mem2[qc][pc-1] - \
            mem2[pc-1][pc-1] if pc > 0 else 0
        sum = mem2[qc][qc] - low
        print(sum)
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    Q = int(next(tokens))  
    L = [int()] * (M)  
    R = [int()] * (M)  
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  
    q = [int()] * (Q)  
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


if __name__ == '__main__':
    main()

Solution (Python):
def main():
	N, M, Q = map(int, input().split())
	LR = [[0 for _ in range(N+1)] for _ in range(N+1)]
	ans = [0]*Q
	for _ in range(M):
		l, r = map(int, input().split())
		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]
	for i in range(1, N+1):
		for j in range(1, N+1):
			LR[i][j] += LR[i-1][j]

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


if __name__ == '__main__':
    main()

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

for i in range(m):
    l, r = (int(i) for i in input().split())
    city[l][r] += 1
for i in range(1, n+1):
    for j in range(1, n+1):
        city[i][j] += city[i][j-1]
for i in range(1, n+1):
    for j in range(1, n+1):
        city[i][j] += city[i-1][j]


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

Solution (Python):
import itertools

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

route = [[0 for i in range(N+1)] for j in range(N+1)]

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

for i in range(1, N):
    route[i] = list(itertools.accumulate(route[i]))

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

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

Solution (Python):
from itertools import accumulate

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=[list(accumulate(a[i])) for i in range(N+1)]
k=[[b[j][i] for j in range(i+1) ] for i in range(N+1)]

ans=[list(accumulate(reversed(k[i])))[::-1] for i in range(N+1)]


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

Solution (Python):
import sys

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(i,N+1):
        b[i][j]=a[i][j]+b[i][j-1]

ans=[[0]*(N+2) for i in range(N+2)]
for q in range(1,N+1):
    for p in range(q,0,-1):
        ans[p][q]=ans[p+1][q]+b[p][q]

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

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

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

for i in range(M):
    l, r = map(int, input().split())

    count[l][r] += 1


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


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

Solution (Python):

import sys
import itertools
import collections
import functools
import math
from queue import Queue

INF = float("inf")


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    a = [[0]*(N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        a[l][r] += 1

    a = [list(itertools.accumulate(x)) for x in a]
    a = [list(itertools.accumulate(s[::-1]))[::-1] for s in zip(*a)]

    for pp, qq in zip(p, q):
        
        print(a[qq][pp])
    

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    Q = int(next(tokens))  
    L = [int()] * (M)  
    R = [int()] * (M)  
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  
    q = [int()] * (Q)  
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


if __name__ == '__main__':
    main()

Solution (Python):

import sys
import itertools
import collections
import functools
import math
from queue import Queue

INF = float("inf")


class Bit:
    def __init__(self, n, m):
        self.size = [n, m]
        self.tree = [[0] * (n + 1) for _ in range(m+1)]

    def sum(self, i, j):
        s = 0
        while i > 0:
            jj = j
            while jj > 0:
                s += self.tree[i][jj]
                jj -= jj & -jj
            i -= i & -i
        return s

    def add(self, i, j, x):
        while i <= self.size[0]:
            jj = j
            while jj <= self.size[1]:
                self.tree[i][jj] += x
                jj += jj & -jj
            i += i & -i


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    b = Bit(N, N)

    for l, r in zip(L, R):
        b.add(N-l+1, r, 1)

    for pp, qq in zip(p, q):
        print(b.sum(N-pp+1, qq))

    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    Q = int(next(tokens))  
    L = [int()] * (M)  
    R = [int()] * (M)  
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  
    q = [int()] * (Q)  
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)


if __name__ == '__main__':
    main()

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

ans = [[0 for _ in range(n)] for __ in range(n)]

data = [list(map(int, input().split())) for _ in range(m)]

questions = [list(map(int, input().split())) for _ in range(q)]

for (l, r) in data:
    ans[l-1][r-1] += 1
for sub in ans:
    for i in range(n-1):
        sub[i+1] += sub[i]
for i in range(n-2, -1, -1):
    for j in range(n):
        ans[i][j] += ans[i+1][j]
for (l, r) in questions:
    print(ans[l-1][r-1])

Solution (Python):
import numpy as np
N,M,Q = map(int,input().split())
c = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    c[l][r] += 1
c = np.cumsum(np.cumsum(c,axis=0),axis=1)
for i in range(Q):
    p,q = map(int,input().split())
    print(c[q][q]-c[q][p-1]-c[p-1][q]+c[p-1][p-1])

Solution (Python):

def main():
    N, M, Q = [int(n) for n in input().split()]
    imos = [[0] * N for _ in range(N)]
    for i in range(M):
        l, r = [int(i)-1 for i in input().split()]
        imos[l][r]+=1
    
    for h in range(N):
        for w in range(1, N):
            imos[h][w] += imos[h][w-1]
    for h in reversed(list(range(1, N))):
        for w in range(N):
            imos[h-1][w] += imos[h][w]
    
    ans = [0]*Q
    for q in range(Q):
        ql, qr = [int(i)-1 for i in input().split()]
        ans[q] = imos[ql][qr]
    for a in ans:
        print(a)



if __name__ == "__main__":
    main()

Solution (Python):
N,M,Q = map(int,input().split())
toshi = []
for i in range(M):
  toshi.append(tuple(map(int,input().split())))
query = []
for i in range(Q):
  query.append(tuple(map(int,input().split())))
grid = []
for i in range(N+1):
  grid.append([0]*(N+1))
for i in range(M):
  grid[toshi[i][1]][toshi[i][0]] += 1
for i in range(1,N+1):
  for j in range(1,N+1):
    grid[i][j] += grid[i][j-1]
for i in range(Q):
  ans = 0
  for j in range(query[i][1]-query[i][0]+1):
    ans += (grid[query[i][0]+j][query[i][1]]-grid[query[i][0]+j][query[i][0]-1])
  print(ans)

Solution (Python):
import numpy as np
n,m,q=map(int,input().split())
s=np.zeros((n,n))
for i in range(m):
    l,r=map(int,input().split())
    s[n-l][r-1]+=1
s=np.cumsum(np.cumsum(s,axis=0),axis=1)
for i in range(q):
    d,t=map(int,input().split())
    print(int(s[n-d][t-1]))

Solution (Python):
from collections import Counter
from functools import lru_cache
import sys
sys.setrecursionlimit(2*10**5)

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

c = Counter(zip(L, R))


@lru_cache(maxsize=None)
def f(x, y):
    return (
        0 if x > y else
        c[x, y] + f(x + 1, y) + f(x, y - 1) - f(x + 1, y - 1)
    )


ans = '\n'.join(map(str, (f(x, y) for x, y in zip(p, q))))
print(ans)

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

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

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

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

    ans  = sum_v[q][q]
    ans -= sum_v[q][p-1]
    ans -= sum_v[p-1][q]
    ans += sum_v[p-1][p-1]

    print(ans)

Solution (Python):

import numpy as np
n,m,q=map(int,input().split())
a=np.zeros((n+2,n+2))
for i in range(m):
  s,e=map(int,input().split())
  a[s,e]+=1

b=a.cumsum(1)

b=np.flipud(b)

b=b.cumsum(0)

b=np.flipud(b)

for i in range(q):
  s,e=map(int,input().split())
  print(int(b[s,e]))

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

lr = [[int(item) for item in input().split()] for _ in range(m)]
pq = [[int(item) for item in input().split()] for _ in range(q)]

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

for item in lr:
  field[item[0]][item[1]] += 1
  
for i in range(1,n+1):
  for j in range(1,n+1):
    cumsum[i][j] = field[i][j] + cumsum[i][j-1]

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

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

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

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

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

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

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

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


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

Solution (Python):
n,m,q = map(int,input().split())
dist = [list(map(int,input().split())) for i in range(m)]
query = [list(map(int,input().split())) for i in range(q)]

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

for i in range(m):
  coord[dist[i][0]][dist[i][1]] += 1

ruiseki = [[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,n+1):
    ruiseki[i][j] = coord[i][j] + ruiseki[i-1][j]
 
for i in range(1,n+1):
  for j in range(1,n+1):
    ruiseki[i][j] = ruiseki[i][j]+ ruiseki[i][j-1]


for i,j in query:
  ans = ruiseki[j][j]-ruiseki[i-1][j]-ruiseki[j][i-1]+ruiseki[i-1][i-1]
  print(ans)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


def A():
    return


def B():
    return


def C():
    s = S()
    k = I()
    for i in range(k):
        if s[i] != "1":
            print(s[i])
            quit()
    print(1)


def D():
    n,m,q = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        l,r = LI()
        v[l-1].append(r-1)
    for i in range(n):
        v[i].sort()
    f = [[bisect.bisect_right(v[i],j) for j in range(n)] for i in range(n)]
    for i in range(q):
        p,q = LI()
        p -= 1
        q -= 1
        ans = 0
        for j in range(p,q+1):
            ans += f[j][q]
        print(ans)

def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    D()

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
    
for i in range(1, N + 1):
    for j in range(1, N + 1):
        A[i][j] += A[i - 1][j] + A[i][j - 1] - A[i - 1][j -1]
        
for i in range(Q):
    p, q = map(int, input().split())
    print(A[q][q] - A[q][p - 1] - A[p - 1][q] + A[p - 1][p - 1])

Solution (Python):
N,M,Q=map(int,input().split())
c=[[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
  a,b=map(int,input().split())
  c[a][b]+=1
for i in range(1,N):
  for j in range(1,N+1-i):
    c[j][i+j]+=c[j+1][i+j]+c[j][i+j-1]-c[j+1][i+j-1]
for i in range(Q):
  a,b=map(int,input().split())
  print(c[a][b])

Solution (Python):
N,M,Q=map(int,input().split())
dp=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
    a=list(map(int,input().split()))
    dp[a[0]][a[1]]+=1
for i in range(N,0,-1):
    count=0
    for j in range(1,N+1):
        count+=dp[i][j]
        if i==N:
            dp[i][j]=count
        else:
            dp[i][j]=dp[i+1][j]+count
p=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
    print(dp[p[i][0]][p[i][1]])

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

for _ in range(M):
    a = list(map(int, input().split()))
    N_Map[a[0]][a[1]] += 1

for i in range(N, 0, -1):
    count = 0
    for j in range(1, N  + 1):
        count += N_Map[i][j]
        if i < N:
            N_Map[i][j] = N_Map[i + 1][j] + count
        else:
            N_Map[i][j] = count

Pi = []
for _ in range(Q):
    a = list(map(int, input().split()))
    Pi.append(a)

for p in Pi:
    print(N_Map[p[0]][p[1]])

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

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

Solution (Python):
N, M, Q = map(int, input().split())
Data = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        
        for x, y in points:
            self.G[x][y] += 1

    def load_imos(self, points):
        
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  
            if j2 + 1 < self.W:  
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  
            if j2 + 1 < self.W and i2 + 1 < self.H:  
                self.G[i2+1][j2+1] += 1

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]



R2D = Ruisekiwa2D(N, N)
R2D.load(Data)
R2D.calc()



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

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

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

for p, q in pq:
    ans = RcntL[q, q] - RcntL[q, p - 1]
    print(ans)

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

N, M, Q = inpl()
cumsum = [0]*((N+1)**2)
ans = [0]*((N+1)**2)

for i in range(M):
    L, R = inpl()
    cumsum[L*(N+1)+R] += 1

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

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

for i in range(Q):
    p, q = inpl()
    print(ans[p*(N+1)+q])

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

for i in range(0, m):
    l, r = [int(j) for j in input().split(" ")]
    c[1 + n - l][r] += 1

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

for i in range(0, q):
    pi, qi = [int(j) for j in input().split(" ")]
    print(s[1 + n - pi][qi])

Solution (Python):
class Sum2D:
    def __init__(self,h,w):
        self.height=h
        self.width=w
        self.data=[[0]*(self.width+1) for _ in range(self.height+1)]
    def add(self,x,y,v):
        self.data[x][y]+=v
    def build(self):
        for x in range(self.height):
            for y in range(self.width):
                self.data[x+1][y+1]+=self.data[x+1][y]
                self.data[x+1][y+1]+=self.data[x][y+1]
                self.data[x+1][y+1]-=self.data[x][y]
    def query(self,p,q):
        return self.data[q][q]+self.data[p][p]-self.data[p][q]-self.data[q][p]

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m,q=map(int,input().split())
S=Sum2D(n,n)
for _ in range(m):
    l,r=map(int,input().split())
    S.add(l,r,1)
S.build()
for _ in range(q):
    l,r=map(int,input().split())
    print(S.query(l-1,r))

Solution (Python):
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m,q=map(int, input().split())
Num2D=[[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    l,r=map(int,input().split())
    Num2D[l][r]+=1
for i in range(n):
    for j in range(n):
        Num2D[i+1][j+1]+=Num2D[i+1][j]
        Num2D[i+1][j+1]+=Num2D[i][j+1]
        Num2D[i+1][j+1]-=Num2D[i][j]
for _ in range(q):
    l,r=map(int,input().split())
    print(Num2D[r][r]+Num2D[l-1][l-1]-Num2D[l-1][r]-Num2D[r][l-1])

Solution (Python):
import sys
input = sys.stdin.readline
n,m,q = map(int,input().split())

res = [[0]*n for i in range(n)]
for i in range(m):
    L,r = map(int,input().split())
    L -= 1
    r -= 1
    res[r][0] += 1
    if L != n-1:
        res[r][L+1] -= 1

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

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

table = []
for i in range(n+1):
    table.append([0]*(n+1))
for i in range(m):
    a,b = map(int,input().split())
    table[b][a] += 1


for i in range(2,n+1):

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

for _ in range(q):
    start,end = map(int,input().split())
    print(table[end][start])

Solution (Python):
class CumulativeSum2D:
    def __init__(self, size: int):
        self.size = size
        self.data = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

    def add(self, l: int, r: int, v: int):
        self.data[l][r] += v

    def build(self):
        for l in range(self.size):
            for r in range(self.size):
                self.data[l + 1][r + 1] += self.data[l + 1][r]
                self.data[l + 1][r + 1] += self.data[l][r + 1]
                self.data[l + 1][r + 1] += -self.data[l][r]

    def query(self, l: int, r: int) -> int:
        """(l, r] x (l, r]
        """
        return self.data[r][r] + self.data[l][l] - self.data[l][r] - self.data[r][l]


def atcoder_express2(
        N: int, M: int, Q: int, data: list, queries: list) -> list:
    
    S = CumulativeSum2D(N)
    for l, r in data:
        S.add(l, r, 1)
    S.build()

    return [S.query(p-1, q) for p, q in queries]


if __name__ == "__main__":
    M, Q = 0, 0
    N, M, Q = map(int, input().split())
    data = [tuple(int(s) for s in input().split()) for _ in range(M)]
    queries = [tuple(int(s) for s in input().split()) for _ in range(Q)]
    ans = atcoder_express2(N, M, Q, data, queries)
    for a in ans:
        print(a)

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

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

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


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