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
from itertools import accumulate

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

Solution (Python):


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

lr = [[0 for i in range(n + 1)] for j in range(n + 1)]

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 j in range(1, n + 1):
    for i in range(1, n + 1):
        lr[i][j] += lr[i-1][j]


res = []
for _ in range(qq):
    ans = 0
    p, q = map(int, input().split())
    ans += lr[q][q] + lr[p-1][p-1] - lr[p-1][q] - lr[q][p-1]
    res.append(ans)

for row in res:
    print(row)

Solution (Python):
n, m, q = map(int, input().split())
mlist = [list(map(int, input().split())) for _ in range(m)]
qlist = [list(map(int, input().split())) for _ in range(q)]

result = [[0] * n for _ in range(n)]
for i in range(m):
    result[0][mlist[i][1] - 1] += 1
    if mlist[i][0] < n:
        result[mlist[i][0]][mlist[i][1] - 1] -= 1

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

for i in range(q):
    print(result[qlist[i][0] - 1][qlist[i][1] - 1])

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

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

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

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

Solution (Python):
import numpy as np
n, m, q = [int(item) for item in input().split(" ")]


end = np.zeros((m,2),dtype=int)
query = np.zeros((q,2),dtype=int)
for i in range(m):
    end[i] = [int(item) for item in input().split(" ")]


for i in range(q):
    query[i] = [int(item) for item in input().split(" ")]


a = np.zeros((n,n), dtype=int)
np.add.at(a, [end[:,0]-1,end[:,1]-1], 1)
b = np.cumsum(a[::-1,:], axis=0)[::-1,:]
c = np.cumsum(b, axis=1)

result = c[query[:,0]-1, query[:,1]-1]
for i in range(q):
    print(result[i])

Solution (Python):



N, M, Q = map(int, input().split(" "))
L = []
R = []
p = []
q = []

for i in range(M):
    _L, _R = map(int, input().split(" "))
    L.append(_L)
    R.append(_R)
    
for i in range(Q):
    _p, _q = map(int, input().split(" "))
    p.append(_p)
    q.append(_q)
    
def buildSumTable(N, L, R):
    ret = [[0 for i in range(N+1)] for i in range(N+1)]
    for i in range(M):
        ret[L[i]][R[i]] += 1
    for i in range(1, N+1):
        for j in range(1, N+1):
            ret[i][j] += ret[i-1][j]
            ret[i][j] += ret[i][j-1]
            ret[i][j] -= ret[i-1][j-1]
    return ret

def getSumRange(table, p, q):
    return table[q][q] - table[q][p-1] - table[p-1][q] + table[p-1][p-1] 

sumTable = buildSumTable(N, L, R)

for i in range(Q):
    ans = getSumRange(sumTable, p[i], q[i])
    print(ans)

Solution (Python):
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M,Q = inpl()
kukan = []

for i in range(M):
	l,r = inpl()
	kukan.append([r,-1,l])


for i in range(Q):
	p,q = inpl()
	kukan.append([q,i,p])

kukan.sort()

bit = [0]*(N+1)
ans = [0]*Q

def BIT_add(a,w):
	global bit
	x = a
	while x <= N:
		bit[x] += w
		x += x & -x

def BIT_sum(a):
	global bit
	tmp = 0
	x = a
	while x > 0:
		tmp += bit[x]
		x -= x & -x
	return tmp

for t,flag,s in kukan:
	if flag == -1: 
		BIT_add(s,1)
	else:
		ans[flag] = BIT_sum(t)-BIT_sum(s-1)

for a in ans:
	print(a)

Solution (Python):
from itertools import accumulate
def a():
    return map(int,input().split())
n,m,q=a()
s=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
    x,y=a()
    s[n-x][y-1]+=1
def f(s):
    for i in range(len(s)):
        s[i]=list(accumulate(s[i]))
f(s)
s=list(zip(*s))
f(s)
for i in range(q):
    x,y=a()
    print(s[y-1][n-x])

Solution (Python):
from itertools import accumulate
n,m,q=map(int,input().split())
s=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    s[n-x][y-1]+=1
def f(s):
    for i in range(len(s)):
        s[i]=list(accumulate(s[i]))
f(s)
s=list(zip(*s))
f(s)
for i in range(q):
    x,y=map(int,input().split())
    print(s[y-1][n-x])

Solution (Python):
def run(n, m, qq, l, r, p, q):
    cnt = {}
    sum = {}
    ret = []
    for i in range(n+1):
        for j in range(n+1):
            cnt[i, j] = 0
            sum[i, j] = 0
    for i in range(m):
        cnt[(l[i], r[i])] += 1
    for i in range(1, n+1):
        for j in range(1, n+1):
            sum[i, j] = cnt[i, j] + sum[i-1, j] + sum[i, j-1] - sum[i-1, j-1]
    for i in range(qq):
        ret.append(sum[q[i], q[i]] - sum[p[i]-1, q[i]] - sum[q[i], p[i]-1] + sum[p[i]-1, p[i]-1])
    return ret


def read_line():
    n, m, qq = map(int, input().split())
    l = []
    r = []
    for i in range(m):
        tl, tr = map(int, input().split())
        l.append(tl)
        r.append(tr)
    p = []
    q = []
    for i in range(qq):
        tp, tq = map(int, input().split())
        p.append(tp)
        q.append(tq)
    return (n, m, qq, l, r, p, q)


def main():
    n, m, qq, l, r, p, q = read_line()
    ret = run(n, m, qq, l, r, p, q)
    for i in range(len(ret)):
        print(ret[i])


if __name__ == '__main__':
    main()

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



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


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


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


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

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

LR =[[0 for j in range(N+2)] for i in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    LR[L][R] += 1
    LR[0][R] -= 1
    LR[L][N+1] -= 1
    LR[0][N+1] += 1

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

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

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

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Ruiwa():
    def __init__(self, a):
        self.H = h = len(a)
        self.W = w = len(a[0])
        self.R = r = a
        for i in range(h):
            for j in range(1,w):
                r[i][j] += r[i][j-1]

        for i in range(1,h):
            for j in range(w):
                r[i][j] += r[i-1][j]

    def search(self, x1, y1, x2, y2):
        if x1 > x2 or y1 > y2:
            return 0

        r = self.R
        rr = r[y2][x2]
        if x1 > 0 and y1 > 0:
            return rr - r[y1-1][x2] - r[y2][x1-1] + r[y1-1][x1-1]
        if x1 > 0:
            rr -= r[y2][x1-1]
        if y1 > 0:
            rr -= r[y1-1][x2]

        return rr

def main():
    n,m,q = LI()
    lr = [LI_() for _ in range(m)]
    pq = [LI_() for _ in range(q)]

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

    for l,r in lr:
        a[l][r] += 1

    rui = Ruiwa(a)
    rr = []
    for p,q in pq:
        rr.append(rui.search(p,p,q,q))

    return '\n'.join(map(str, rr))




print(main())

Solution (Python):
a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])
ll = list()
rr = list()

for _ in range(m):
    a = input().split()
    ll.append(int(a[0]))
    rr.append(int(a[1]))

p = list()
q = list()

for _ in range(qq):
    a = input().split()
    p.append(int(a[0]))
    q.append(int(a[1]))

c = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    c[ll[i] - 1][rr[i] - 1] += 1

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

for i in range(qq):
    r = 0

    if 0 < q[i]:
        r += c[q[i] - 1][q[i] - 1]

    if 0 < q[i] and 1 < p[i]:
        r -= c[q[i] - 1][p[i] - 2] + c[p[i] - 2][q[i] - 1]

    if 1 < p[i]:
        r += c[p[i] - 2][p[i] - 2]

    print(r)

Solution (Python):
a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])

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

for _ in range(m):
    a = input().split()
    x[int(a[0]) - 1][int(a[1]) - 1] += 1

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

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

for _ in range(qq):
    r = 0
    a = input().split()
    p = int(a[0])
    q = int(a[1])

    if 0 < q:
        r += x[q - 1][q - 1]

    if 0 < q and 1 < p:
        r -= x[q - 1][p - 2] + x[p - 2][q - 1]

    if 1 < p:
        r += x[p - 2][p - 2]

    print(r)

Solution (Python):
from itertools import accumulate
import sys
sdin = sys.stdin.readline

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

lr = []
for i in range(m):
    l,r = map(int, sdin().split())
    lr.append(tuple([l, r]))
        
pq = []
for _ in range(q):
    p,q = map(int, sdin().split())
    pq.append(tuple([p, q]))
    

field = [[0 for _ in range(n+1)] for _ in range(n+1)]
for l, r in lr:
    field[l][r] += 1
    

field_cum = [list(accumulate(field[i])) for i in range(n+1)]    


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

        

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

Solution (Python):
from itertools import accumulate
import sys
sdin = sys.stdin.readline

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

lr = []
for i in range(m):
    l,r = map(int, sdin().split())
    lr.append(tuple([l-1, r-1]))
        
pq = []
for _ in range(q):
    p,q = map(int, sdin().split())
    pq.append(tuple([p-1, q-1]))

    

field = [[0 for _ in range(n)] for _ in range(n)]
for l, r in lr:
    field[l][r] += 1
    

field_cum = [list(accumulate(field[i])) for i in range(n)]    


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

        

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

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class RectangleSum():
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.s = [[0] * (M+1) for _ in range(N+1)]

    def add(self, i, j, v):
        self.s[i+1][j+1] += v

    def build(self):
        for i in range(self.N+1):
            for j in range(self.M):
                self.s[i][j+1] += self.s[i][j]

        for i in range(self.N):
            for j in range(self.M+1):
                self.s[i+1][j] += self.s[i][j]

    def sum(self, i, j, h, w):
        ret = self.s[i][j]
        ret += self.s[i+h][j+w]
        ret -= self.s[i+h][j]
        ret -= self.s[i][j+w]

        return ret


@mt
def slv(N, M, Q, LR, PQ):
    rs = RectangleSum(N+1, N+1)
    for l, r in LR:
        rs.add(l, r, 1)

    rs.build()

    for p, q in PQ:
        print(rs.sum(p, p, q-p+1, q-p+1))


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class RectangleSum():
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.s = [[0] * (M+1) for _ in range(N+1)]

    def add(self, i, j, v):
        self.s[i+1][j+1] += v

    def build(self):
        for i in range(self.N+1):
            for j in range(self.M):
                self.s[i][j+1] += self.s[i][j]

        for i in range(self.N):
            for j in range(self.M+1):
                self.s[i+1][j] += self.s[i][j]

    def sum(self, i, j, h, w):
        ret = self.s[i][j]
        ret += self.s[i+h][j+w]
        ret -= self.s[i+h][j]
        ret -= self.s[i][j+w]

        return ret


@mt
def slv(N, M, Q, LR, PQ):
    rs = RectangleSum(N+1, N+1)
    for l, r in LR:
        rs.add(l, r, 1)

    rs.build()

    for p, q in PQ:
        print(rs.sum(p, p, q-p+1, q-p+1))


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate
import sys
sdin = sys.stdin.readline

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

lr = []
for i in range(m):
    l,r = map(int, sdin().split())
    lr.append(tuple([l-1, r-1]))
        
pq = []
for _ in range(q):
    p,q = map(int, sdin().split())
    pq.append(tuple([p-1, q-1]))



field = [[0 for _ in range(n)] for _ in range(n)]
for l, r in lr:
    field[l][r] += 1
    

field_cum = [list(accumulate(field[i])) for i in range(n)]    


for p,q in pq:
    ans = 0
    for i in range(p,q+1):
        ans += field_cum[i][q]
    print(ans)

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

x = [[0] * (N+1) for i in range(N+1)]
for l, r in LR:
    x[l][r] += 1

from itertools import accumulate

t = [list(accumulate(row)) for row in x]
s = [list(accumulate(row)) for row in zip(*t)]

for p, q in PQ:
    result = s[q][q] -s[q][p-1] - s[p-1][q] + s[p-1][p-1]
    print(result)

Solution (Python):
import itertools

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

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

acc_lr = []
for l in lr:
    acc_lr.append([0] + list(itertools.accumulate(l)))

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

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

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

Solution (Python):
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]

N,M,Q = Is()
lis = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = Is()
    lis[l][r] += 1

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

for _ in range(Q): 
    p,q = Is()
    t = 0
    for i in range(p,q+1):
        t += cs[i][q] - cs[i][i-1]
    print(t)

Solution (Python):
import sys
from bisect import bisect_left

INDATA = sys.stdin.read().split('\n')
idx = -1
def input():
    global idx
    idx += 1
    return INDATA[idx]

n, m, q = map(int, input().split())
LR = [0]*m
for i in range(m):
    LR[i] = list(map(int, input().split()))
P = [0]*q
Q = [0]*q
for i in range(q):
    P[i], Q[i] = map(int, input().split())
 
LR.sort(key=lambda x: (x[0], x[1]))
L = list(map(lambda x: x[0], LR))

 
C = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    l = bisect_left(L, i)
    r = bisect_left(L, i+1)-1
    R2 = list(map(lambda x: x[1], LR[l:r+1]))
    
    for j in range(i,n+1):
        C[i][j] = bisect_left(R2, j+1)
    
 
for i in range(q):
    ans = 0
    for j in range(P[i], Q[i]+1):
        ans += C[j][Q[i]]
    print(ans)

Solution (Python):
N, M, Q = map(int, input().split())
s = [[0 for j in range(N+1)] for i in range(N+1)]
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-1][j] + s[i][j-1] - s[i-1][j-1]

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

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

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

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

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

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

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

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

from collections import defaultdict
from itertools import accumulate

C = [[0]*(N+1) for i in range(N+2)]

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



T = [list(accumulate(row)) for row in C]
T = [list(accumulate(row)) for row in zip(*T)]



for p, q in PQ:
    print(T[q][p])

Solution (Python):
def d_atcoder_express_2(N, M, Q, Train, Query):
    x = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in Train:
        x[l][r] += 1
    
    for r in range(1, N + 1):
        for c in range(1, N + 1):
            x[r][c] += x[r - 1][c] + x[r][c - 1] - x[r - 1][c - 1]

    tmp = []
    for p, q in Query:
        
        tmp.append(str(x[q][q] - x[p - 1][q] - x[q][p - 1] + x[p - 1][p - 1]))
    ans = '\n'.join(tmp)
    return ans

N, M, Q = [int(i) for i in input().split()]
Train = [[int(i) for i in input().split()] for j in range(M)]
Query = [[int(i) for i in input().split()] for j in range(Q)]
print(d_atcoder_express_2(N, M, Q, Train, Query))

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

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

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

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

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

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

Solution (Python):
from copy import deepcopy

N, M, Q = [int(elem) for elem in input().split(' ')]
lines = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
queries = [[int(elem) for elem in input().split(' ')] for _ in range(Q)]


def cuml_1d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1

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

    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        num_lines = 0
        for l in range(p, max(q + 1, N)):
            if p == 0:
                num_lines += cuml_coords[l][q]
            else:
                num_lines += cuml_coords[l][q] - cuml_coords[l][p - 1]
        print(num_lines)




def cuml_2d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1
    cuml_l = deepcopy(coords)
    for r in range(N):
        for l in range(1, N):
            cuml_l[l][r] = cuml_l[l - 1][r] + coords[l][r]
    cuml_2d = deepcopy(cuml_l)
    for l in range(N):
        for r in range(1, N):
            cuml_2d[l][r] = cuml_2d[l][r - 1] + cuml_l[l][r]
    
    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        if p != 0:
            num_lines = cuml_2d[q][q] - cuml_2d[q][p-1] - cuml_2d[p-1][q] + cuml_2d[p-1][p-1]
        else:
            num_lines = cuml_2d[q][q]
        print(num_lines)

cuml_2d(N, lines, queries)

Solution (Python):
from copy import deepcopy

N, M, Q = [int(elem) for elem in input().split(' ')]
lines = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
queries = [[int(elem) for elem in input().split(' ')] for _ in range(Q)]


def cuml_1d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1

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

    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        num_lines = 0
        for l in range(p, max(q + 1, N)):
            if p == 0:
                num_lines += cuml_coords[l][q]
            else:
                num_lines += cuml_coords[l][q] - cuml_coords[l][p - 1]
        print(num_lines)




def cuml_2d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1
    cuml_l = deepcopy(coords)
    for r in range(N):
        for l in range(1, N):
            cuml_l[l][r] = cuml_l[l - 1][r] + coords[l][r]
    cuml_2d = deepcopy(cuml_l)
    for l in range(N):
        for r in range(1, N):
            cuml_2d[l][r] = cuml_2d[l][r - 1] + cuml_l[l][r]
    
    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        if p != 0:
            num_lines = cuml_2d[q][q] - cuml_2d[q][p-1] - cuml_2d[p-1][q] + cuml_2d[p-1][p-1]
        else:
            num_lines = cuml_2d[q][q]
        print(num_lines)

cuml_2d(N, lines, queries)

Solution (Python):
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]

N,M,Q = Is()
lis = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = Is()
    lis[l][r] += 1

cs = [[0]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        cs[i][j] = cs[i][j-1] + sum(lis[i][:j+1])

for _ in range(Q): 
    p,q = Is()
    t = 0
    for i in range(p,q+1):
        t += cs[i][q] - cs[i][q-1]
    print(t)

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

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

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

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

Solution (Python):
n,m,q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
p = [list(map(int, input().split()))+ [i] for i in range(q)]
l.extend(p)
l = sorted(l,key= lambda x:x[1])
ka = [0] * n
ans = []
for i in l:
  if len(i) == 2:
    ka[i[0]-1] += 1
  else:
    ans.append([i[2],sum(ka[i[0]-1:i[1]])])
ans = sorted(ans)
for i in range(len(ans)):
  print(ans[i][1])

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

l=[]
r=[]
for j in range(m):
    l_tmp, r_tmp = list(map(int, input().split()))
    l.append(l_tmp)
    r.append(r_tmp)

p=[]
q=[]
for k in range(Q):
    p_tmp, q_tmp = list(map(int, input().split()))
    p.append(p_tmp)
    q.append(q_tmp)
    
su = [[0 for _ in range(n+1)] for __ in range(n+1)]

def sumTable(L, R):
    for i in range(m):
        su[L[i]][R[i]] += 1
    
    for i in range(1,n+1):
        for j in range(1, n+1):
            su[i][j] += su[i-1][j]
            su[i][j] += su[i][j-1]
            su[i][j] -= su[i-1][j-1]

def getSum(ll,rr):
    ans = su[rr][rr] - su[rr][ll-1] -su[ll-1][rr] + su[ll-1][ll-1]
    return ans
  
sumTable(l,r)

import copy
ss = copy.copy(su)

for qi in range(Q):
    su = copy.copy(ss)
    print(getSum(p[qi], q[qi]))

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


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

for i in range(1, N+1):
    LR_sum[1][i] = LR_sum[1][i-1] + LR[1][i]
    LR_sum[i][1] = LR_sum[i-1][1] + LR[i][1]

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

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

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

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

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

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

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

    ans = x[N][q] - x[p - 1][q]
    print(ans)

Solution (Python):
a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])

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

for _ in range(m):
    a = input().split()
    x[int(a[0]) - 1][int(a[1]) - 1] += 1

c = list()

for i in range(n):
    c.append(list())
    for j in range(n):
        a = x[i][j]

        if 0 < j:
            a += c[i][j - 1]

        c[i].append(a)

z = list()

for i in range(n):
    z.append(list())
    for j in range(n):
        a = c[i][j]

        if 0 < i:
            a += z[i - 1][j]

        z[i].append(a)

for _ in range(qq):
    r = 0
    a = input().split()
    p = int(a[0])
    q = int(a[1])

    if 0 < q:
        r += z[q - 1][q - 1]

    if 0 < q and 1 < p:
        r -= z[q - 1][p - 2] + z[p - 2][q - 1]

    if 1 < p:
        r += z[p - 2][p - 2]

    print(r)

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

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

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

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

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

    ans = x[N][q] - x[p - 1][q]
    print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(500000)

def memoize(f):
    table = {}

    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func


@memoize
def memo(a, b):
    if a == b:
        return e[a].count(a)
    elif b - a == 1:
        return memo(b, b) + memo(a, a) + e[a].count(b)
    else:
        return memo(a+1, b)+memo(a, b-1) + e[a].count(b) - memo(a+1, b-1)


n, m, q = map(int, input().split())
e = []
for i in range(n+1):
    e.append([])
for i in range(m):
    x, y = map(int, input().split())
    e[x].append(y)
for i in range(q):
    x, y = map(int, input().split())
    print(memo(x, y))