Problem: In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east. A company called _AtCoder Express_ possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i). Takahashi the king is interested in the following Q matters:    * The number of the trains that runs **strictly within** the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.  Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Submission attempts (in order):
import 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
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

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
	for j in range(N):
		tmp += x[i][j]
		C[i][j] = tmp

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)



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


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
import numpy as np
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()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

x = np.zeros((N+1, N+1), dtype=np.int64)
for L, R in LR:
    x[L, R] += 1
x = x.cumsum(axis=0).cumsum(axis=1)

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


Verdicts: Time Limit Exceeded

Time Limit Exceeded

Accepted