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
sys.setrecursionlimit(10010010)

def abc106_d():
    n, m, q = map(int, input().split())
    table = [[0]*(n+1) for _ in range(n+1)]
    for _ in range(m):
        l, r = map(int, input().split())
        table[l][r] += 1
    query = [tuple(map(int, input().split())) for _ in range(q)]

    dp = [[-1]*(n+1) for _ in range(n+1)]

    def calc(l, r):
        nonlocal dp
        if l == 0 or r == 0: return 0
        if dp[l][r] != -1: return dp[l][r]
        res = calc(l-1, r) + calc(l, r-1) - calc(l-1, r-1) + table[l][r]
        dp[l][r] = res
        return res

    for p, q in query:
        ans = calc(q, q) - calc(q, p-1) - calc(p-1, q) + calc(p-1, p-1)
        print(ans)

if __name__ == '__main__':
    abc106_d()

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

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

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

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

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


def main():
    n, m, q = map(int, input().split())
    counts = np.zeros((n+1, n+1), dtype=np.int32)
    for _ in range(m):
        from_, to = map(int, input().split())
        counts[:from_+1, to] += 1

    counts = np.cumsum(counts, axis=1)

    queries = np.array([list(map(int, input().split())) for _ in range(q)])
    ps = queries[:, 0]
    qs = queries[:, 1]
    res = counts[ps, qs]
    print(*res, sep="\n")


if __name__ == "__main__":
    main()

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

for m in range(M):
  L, R = map(int, input().split())
  S[L][R] += 1
for l in range(1, N+1):
  for r in range(1, N+1):
    S[l][r] += S[l-1][r] + S[l][r-1] - S[l-1][r-1]

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

Solution (Python):







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

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


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

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

grid_acc[0][0] = grid[0][0]
for i in range(1, n):
    grid_acc[i][0] = grid_acc[i-1][0] + grid[i][0]
    grid_acc[0][i] = grid_acc[0][i-1] + grid[0][i]

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

for i in range(Q):
    p, q = [int(i) for i in input().split()]
    if p == 1:
        print(grid_acc[q-1][q-1])
    else:
        print(grid_acc[q-1][q-1] - grid_acc[p-2][q-1] - grid_acc[q-1][p-2] + grid_acc[p-2][p-2])

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


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

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


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

Solution (Python):

import sys
input = sys.stdin.readline
from itertools import accumulate

N, M, Q = [int(x) for x in input().split()]
train = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for i in range(M):
    L, R = [int(x) for x in input().split()]
    train[L][R] += 1

cum = [list(accumulate(train[i])) for i in range(N + 1)]
del train
cum = list(zip(*cum))
cum = [list(accumulate(cum[j])) for j in range(N + 1)]

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

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

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

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

for i in range(M):
  L,R = map(int,readline().split())
  train[L][R] += 1
  
for i in range(N + 1):
  for j in range(1, N + 1):
    train[i][j] += train[i][j - 1]
    
for j in range(N + 1):
  for i in range(1, N + 1):
    train[i][j] += train[i - 1][j]

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

Solution (Python):

n,m,q=(int(i) for i in input().strip().split(" "))
from collections import defaultdict
d=defaultdict(int)
for _ in range(m):
    a,b=(int(i) for i in input().strip().split(" "))
    d[(a,b)]+=1
for i in range(1,n+1):
    for j in range(1,n+1):
        d[(i,j)]+=d[(i,j-1)]

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

for i in range(q):
    l,r = (int(i) for i in input().strip().split(" "))
    print(d[(r,r)]+d[(l-1,l-1)]-d[(l-1,r)]-d[(r,l-1)])

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

lr=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    li,ri=map(int,input().split())
    lr[li][ri]+=1
    
for i in range(n+1):
    asum=0
    for j in range(n+1):
        asum+=lr[i][j]
        lr[i][j]=asum
            
for i in range(q):
    pi,qi=map(int,input().split())


    asum=0
    for j in range(pi,qi+1):

        asum+=lr[j][qi]-lr[j][j-1]
    print(asum)

Solution (Python):
n,m,q=list(map(int,input().split()))
lr=[[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()))
  lr[l][r]=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]+lr[i][j]


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

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

Solution (Python):
n , m , q = map(int, input().split())
table = [[0]*n for i in range(n)]

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

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

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

for i in range(q):
    l , r = map(int, input().split())
    l-=1
    r-=1
    if l!=0:
        ans=table[r][r]-table[r][l-1]
    else:
        ans=table[r][r]
    print(ans)

Solution (Python):
n , m , q = map(int, input().split())
table = [[0]*n for i in range(n)]

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

table_sum = table.copy()

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

for i in range(q):
    l , r = map(int, input().split())
    l-=1
    r-=1
    ans=0
    for j in range(l,r+1):
        if l!=0:
            ans+=table_sum[j][r]-table_sum[j][l-1]
        else:
            ans+=table_sum[j][r]
    print(ans)

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

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

for L in range(N):
    for R in range(1, N):
        mem[L][R] += mem[L][R-1]

for R in range(N):
    for L in range(1, N):
        mem[L][R] += mem[L-1][R]

res = []
for _ in range(Q):
    QL, QR = map(int, input().split())
    if QL == 1:
        r = mem[QR-1][QR-1]
    else:
        r = mem[QR-1][QR-1] - mem[QL-2][QR-1]
    res.append(r)

for r in res:
    print(r)

Solution (Python):
import sys
import numpy as np

read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7


def main():
    N, M, Q = map(int, readline().split())
    LR = [[0] * (N + 1) for _ in range(N + 1)]

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

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

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


if __name__ == '__main__':
    main()

Solution (Python):


MAX_N = 505
n, m, q = map(int, input().split())
P = [[0] * MAX_N for _ in range(MAX_N)]


for _ in range(m):
    li, ri = map(int, input().split())
    P[li][ri] += 1
for i in range(1, MAX_N):
    for j in range(1, MAX_N):
        P[i][j] += P[i][j - 1]
for i in range(1, MAX_N):
    for j in range(1, MAX_N):
        P[i][j] += P[i - 1][j]


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

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

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

Solution (Python):

from itertools import accumulate
import numpy as np

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

data = [[0]*500 for i in range(500)]


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
















data = np.array(data)

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


for p, q in pq:
    ans = 0
    if p == 1:
        ans = data[q-1][q-1]
    else:
        ans = data[q-1][q-1]-data[p-1-1][q-1]
    print(ans)

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

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

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

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

Solution (Python):



import numpy as np
n, m, q = map(int, input().split())
x = np.zeros((n,n), dtype = int)
for _ in range(m):
    l, r = map(int, input().split())
    x[r-1][l-1] += 1
x.cumsum(out = x, axis = 0)
for i in range(n):
    x[i] = np.cumsum(x[i][::-1])[::-1]

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

Solution (Python):
from itertools import accumulate
 
N,M,Q=map(int, input().split())
a=[[0]*N for i in range(N)]

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

for i in range(N):
  a[i]=list(accumulate(a[i]))

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

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

Solution (Python):


from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)


N, M, Q = map(int, input().split())
trains = []
for _ in range(M):
    l, r = map(int, input().split())
    
    trains.append([l-1, r-1])

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




s = [[0 for r in range(N+1)] for l in range(N+1)]

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

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



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

Solution (Python):


import math

import itertools
from collections import deque
from collections import Counter
import heapq
from fractions  import gcd


n,m,q=map(int,input().split())
x=[[0]*n for _ in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    x[l-1][r-1]+=1
res=[[0]*n for _ in range(n)]
for i in range(n):
    res[i][0]=x[i][0]
    for j in range(1,n):
        res[i][j]=res[i][j-1]+x[i][j]
for i in range(q):
    p,q=map(int,input().split())
    ans=0
    for k in range(p-1,q):
        ans=ans+res[k][q-1]-res[k][p-2] if p!=1 else ans+res[k][q-1]
    print(ans)

Solution (Python):
import numpy as np

def main():
    n,m,q=map(int,input().split())
    lst=np.zeros((n,n),dtype=int)

    for _ in range(m):
        s,t=map(int,input().split())
        lst[s-1][t-1]+=1
    lst=lst.cumsum(axis=1)[::-1].cumsum(axis=0)[::-1]

    for _ in range(q):
        s,t=map(int,input().split())
        print(lst[s-1][t-1])

main()

Solution (Python):

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

A = [[0 for _ in range(n+1)] for _ in range(n+1)]
for x in X:
    l, r = x
    A[l][r] += 1

B = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(1, n+1):
    for j in range(1, n+1):
        B[i][j] += B[i][j-1] + A[i][j]
    for j in range(1, n+1):
        B[i][j] += B[i-1][j]

for q in Q:
    a, b = q
    result = B[b][b] - B[b][a-1] - B[a-1][b] + B[a-1][a-1]
    print(result)

Solution (Python):
import numpy as np
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
T = np.zeros((N, N), dtype=np.int32)
for _ in [0]*M:
    l, r = map(int, input().split())
    T[l-1, r-1] += 1
T = T[::-1].cumsum(axis=0).cumsum(axis=1)[::-1]
for _ in [0]*Q:
    p, q = map(int, input().split())
    print(T[p-1, q-1])

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M,Q=mi()
    
    count = [[0] * (N+1) for _ in range(N+1)]
    for i in range(M):
        L,R=mi()
        count[L][R] += 1
    
    
    dp = [[0] * (N+1) for _ in range(N+1)]

    for w in range(1,N+1):
        for h in range(1,N+1):
            l,r=N+1-w,h
            dp[w][h] += dp[w][h-1] + dp[w-1][h] - dp[w-1][h-1] + count[l][r]


    
    for i in range(Q):
        p,q=mi()
        w,h=N+1-p,q
        
        print(dp[w][h])

            






if __name__ == "__main__":
    main()

Solution (Python):
n,m,q=map(int,input().split())
table=[[0]*(n+1)for i in range(n+1)]
for i in range(m):
    a,s=map(int,input().split())
    table[a][s]+=1
from itertools import accumulate
for i,v  in enumerate(table):
    table[i]=list(accumulate(v))

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