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



Sample input:
2 3 1
1 1
1 2
2 2
1 2


Sample output:
3

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
import numpy as np
n, m, q = map(int, input().split())
dp = np.zeros((n+1, n+1), dtype=np.int64)
for _ in range(m):
  l, r = map(int, input().split())
  dp[l, r] += 1
dp = np.cumsum(dp, axis=1)
dp[::-1] = np.cumsum(dp[::-1], axis=0)
for _ in range(q):
  p, q = map(int, input().split())
  print(dp[p, q])

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())  # N個の駅, M本の電車, Q個のクエリ
X = [[0]*501 for _ in range(501)]
C = [[0]*501 for _ in range(501)]
for _ in range(M):
    left, right = map(lambda x: int(x)-1, input().split())
    X[left][right] += 1

for i in range(N):
    for j in range(N):
        # 累積和
        C[i][j] = C[i][j-1] + X[i][j]  # 横方向に累積されていく
for _ in range(Q):
    p, q = map(lambda x: int(x)-1, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += C[i][q] - C[i][p-1]
    print(ans)

Submission status: Accepted

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


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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!
N,M,Q=map(int,input().split())

dia=[[0 for i in range(N)] for j in range(N)]

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

ans=[[0 for i in range(N)] for j in range(N)]
for i in range(N):
    for j in range(i,N):
        ans[i][j]=(ans[i][j-1] if j!=0 else 0) + dia[i][j]
#print(ans)

shin=[[0 for i in range(N)] for j in range(N)]

for j in range(N):
    temp=0
    for i in range(j+1)[::-1]:
        #print(i,j)
        temp+=ans[i][j]
        shin[i][j]=temp

for _ in range(Q):
    p,q=map(int,input().split())
    print(shin[p-1][q-1])
#print(shin)
"""
for _ in range(Q):
    p,q=map(int,input().split())
    temp=0
    for i in range(p,q+1):
        #print(i,q)
        temp+=ans[i-1][q-1]
        

    print(temp)
"""

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d
# どうやったら高速に区間[p,q]に完全に入っている区間の数を取得できるか？
# p,qを二次元座標として捉えると電車1本の線は二次元平面上の1点として表せる
# このときp,qの区間に完全に入っている電車の本数というのは、x軸、y軸の両方において[p,q]となる四角形内にある電車の本数
# queryに高速に答えるために二次元累積和を構築する
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret




# クラスで実装してみる
class cumsum2d:
    def __init__(self, ls: list):
        '''
        2次元のリストを受け取る
        '''
        import numpy as np
        self.ls = np.array(ls)
        H, W = self.ls.shape
        self.ls_accum = np.zeros((H + 1, W + 1))
        self.ls_accum[1:, 1:] = self.ls.cumsum(axis=0).cumsum(axis=1)

    def total(self, i1, j1, i2, j2):
        '''
        点(i1,j1),(i1,j2),(i2,j1),(i2,j2)の4点が成す四角の中の合計を取り出す
        ただし i1<=i2, j1<=j2
        ただし、i軸に関しては[i1,i2),j軸に関しては[j1,j2)の半開区間である
        '''
        return self.ls_accum[i2, j2] - self.ls_accum[i1, j2] \
            - self.ls_accum[i2, j1] + self.ls_accum[i1, j1]


N, M, Q = read_ints()
LR = read_tuple(M)
pq = read_tuple(Q)

# numpy使わずに再実装 #入れるときはpythonのほうが速いので
LR2d = [[0] * (N + 1) for _ in range(N + 1)]
for L, R in LR:
    LR2d[L][R] += 1

LR2d_accum = cumsum2d(LR2d)

# queryに答えていく
ans = []
for p, q in pq:
    ans.append(int(LR2d_accum.total(p, p, q + 1, q + 1)))

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d
# どうやったら高速に区間[p,q]に完全に入っている区間の数を取得できるか？
# p,qを二次元座標として捉えると電車1本の線は二次元平面上の1点として表せる
# このときp,qの区間に完全に入っている電車の本数というのは、x軸、y軸の両方において[p,q]となる四角形内にある電車の本数
# queryに高速に答えるために二次元累積和を構築する
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


import numpy as np

N, M, Q = read_ints()
LR = read_tuple(M)
pq = read_tuple(Q)

# numpy使わずに再実装 #入れるときはpythonのほうが速いので
LR2d = [[0] * (N + 1) for _ in range(N + 1)]
for L, R in LR:
    LR2d[L][R] += 1
LR2d = np.array(LR2d, np.int64)

LR2d_accum = np.zeros((N + 2, N + 2), np.int64)
LR2d_accum[1:, 1:] = LR2d.cumsum(axis=0).cumsum(axis=1)  # 1次元累積和同様半開区間で考える
# つまりインデックスi,jとはもとの配列においてi,jを含まない四角形の領域の合計を出す

# queryに答えていく
ans = []
for p, q in pq:
    ans.append(LR2d_accum[q + 1, q + 1] - LR2d_accum[q + 1, p] -
               LR2d_accum[p, q + 1] + LR2d_accum[p, p])

print(*ans, sep='\n')

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d
# どうやったら高速に区間[p,q]に完全に入っている区間の数を取得できるか？
# p,qを二次元座標として捉えると電車1本の線は二次元平面上の1点として表せる
# このときp,qの区間に完全に入っている電車の本数というのは、x軸、y軸の両方において[p,q]となる四角形内にある電車の本数
# queryに高速に答えるために二次元累積和を構築する
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


import numpy as np

N, M, Q = read_ints()
LR = read_tuple(M)
pq = read_tuple(Q)

# numpy使わずに再実装 #入れるときはpythonのほうが速いので
LR2d = [[0] * (N + 1) for _ in range(N + 1)]
for L, R in LR:
    LR2d[L][R] += 1
LR2d = np.array(LR2d, np.int64)

LR2d_accum = np.zeros((N + 2, N + 2), np.int64)
LR2d_accum[1:, 1:] = LR2d.cumsum(axis=0).cumsum(axis=1)  # 1次元累積和同様半開区間で考える
# つまりインデックスi,jとはもとの配列においてi,jを含まない四角形の領域の合計を出す

# queryに答えていく
for p, q in pq:
    print(LR2d_accum[q + 1, q + 1] - LR2d_accum[q + 1, p] -
          LR2d_accum[p, q + 1] + LR2d_accum[p, p])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d
# どうやったら高速に区間[p,q]に完全に入っている区間の数を取得できるか？
# p,qを二次元座標として捉えると電車1本の線は二次元平面上の1点として表せる
# このときp,qの区間に完全に入っている電車の本数というのは、x軸、y軸の両方において[p,q]となる四角形内にある電車の本数
# queryに高速に答えるために二次元累積和を構築する
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


import numpy as np

N, M, Q = read_ints()

# numpy使わずに再実装 #入れるときはpythonのほうが速いので
LR2d = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    L, R = read_ints()
    LR2d[L][R] += 1

LR2d = np.array(LR2d)

LR2d_accum = np.zeros((N + 2, N + 2), np.int64)
LR2d_accum[1:, 1:] = LR2d.cumsum(axis=0).cumsum(axis=1)  # 1次元累積和同様半開区間で考える
# つまりインデックスi,jとはもとの配列においてi,jを含まない四角形の領域の合計を出す

# pq = read_tuple(Q)

for _ in range(Q):
    p, q = read_ints()
    print(LR2d_accum[q + 1, q + 1] - LR2d_accum[q + 1, p] -
          LR2d_accum[p, q + 1] + LR2d_accum[p, p])


'''
以下numpyを使わずに実装してみる
'''

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d
# どうやったら高速に区間[p,q]に完全に入っている区間の数を取得できるか？
# p,qを二次元座標として捉えると電車1本の線は二次元平面上の1点として表せる
# このときp,qの区間に完全に入っている電車の本数というのは、x軸、y軸の両方において[p,q]となる四角形内にある電車の本数
# queryに高速に答えるために二次元累積和を構築する
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


import numpy as np

N, M, Q = read_ints()
LR = read_tuple(M)
pq = read_tuple(Q)

# # 二次元座標上へのプロット
# LR2d = np.zeros((N + 1, N + 1), np.int64)
# for L, R in LR:
#     LR2d[L, R] += 1 #ここがボトルネック


# numpy使わずに再実装
LR2d = [[0] * (N + 1) for _ in range(N + 1)]
for L, R in LR:
    LR2d[L][R] += 1
LR2d = np.array(LR2d)

# LR2d_accum = np.zeros((N + 2, N + 2), np.int64)
LR2d_accum = LR2d.cumsum(axis=0).cumsum(axis=1)  # 1次元累積和同様半開区間で考える
# つまりインデックスi,jとはもとの配列においてi,jを含まない四角形の領域の合計を出す

# queryに答えていく
for p, q in pq:
    print(LR2d_accum[q, q] - LR2d_accum[q, p - 1] -
          LR2d_accum[p - 1, q] + LR2d_accum[p - 1, p - 1])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d
# どうやったら高速に区間[p,q]に完全に入っている区間の数を取得できるか？
# p,qを二次元座標として捉えると電車1本の線は二次元平面上の1点として表せる
# このときp,qの区間に完全に入っている電車の本数というのは、x軸、y軸の両方において[p,q]となる四角形内にある電車の本数
# queryに高速に答えるために二次元累積和を構築する
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


import numpy as np

N, M, Q = read_ints()
LR = read_tuple(M)
pq = read_tuple(Q)

# # 二次元座標上へのプロット
# LR2d = np.zeros((N + 1, N + 1), np.int64)
# for L, R in LR:
#     LR2d[L, R] += 1 #ここがボトルネック


# numpy使わずに再実装
LR2d = [[0] * (N + 1) for _ in range(N + 1)]
for L, R in LR:
    LR2d[L][R] += 1
LR2d = np.array(LR2d)

LR2d_accum = np.zeros((N + 2, N + 2), np.int64)
LR2d_accum[1:, 1:] = LR2d.cumsum(axis=0).cumsum(axis=1)  # 1次元累積和同様半開区間で考える
# つまりインデックスi,jとはもとの配列においてi,jを含まない四角形の領域の合計を出す

# queryに答えていく
for p, q in pq:
    print(LR2d_accum[q + 1, q + 1] - LR2d_accum[q + 1, p] -
          LR2d_accum[p, q + 1] + LR2d_accum[p, p])

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d
# どうやったら高速に区間[p,q]に完全に入っている区間の数を取得できるか？
# p,qを二次元座標として捉えると電車1本の線は二次元平面上の1点として表せる
# このときp,qの区間に完全に入っている電車の本数というのは、x軸、y軸の両方において[p,q]となる四角形内にある電車の本数
# queryに高速に答えるために二次元累積和を構築する
import sys
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


def read_tuple(H):
    '''
    H is number of rows
    '''
    ret = []
    for _ in range(H):
        ret.append(tuple(map(int, read().split())))
    return ret


import numpy as np

N, M, Q = read_ints()
LR = read_tuple(M)
pq = read_tuple(Q)

# 二次元座標上へのプロット
LR2d = np.zeros((N + 1, N + 1), np.int64)
for L, R in LR:
    LR2d[L, R] += 1

LR2d_accum = np.zeros((N + 2, N + 2), np.int64)
LR2d_accum[1:, 1:] = LR2d.cumsum(axis=0).cumsum(axis=1)  # 1次元累積和同様半開区間で考える
# つまりインデックスi,jとはもとの配列においてi,jを含まない四角形の領域の合計を出す

# queryに答えていく
for p, q in pq:
    print(LR2d_accum[q + 1, q + 1] - LR2d_accum[q + 1, p] -
          LR2d_accum[p, q + 1] + LR2d_accum[p, p])

Submission status: Accepted

Solution code:
import collections
import heapq
import bisect
import sys
input = sys.stdin.readline

N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]
LR.sort(key=lambda x: x[1])
table = collections.defaultdict(list)
for l, r in LR:
    table[l].append(r)

ss = [[0]*(N+1) for i in range(N+1)]
s = [[0]*(N+1) for i in range(N+1)]
for i in range(1, N+1):
    for x in table[i]:
        ss[i][x] += 1
    for j in range(i, N+1):
        s[i][j] = s[i][j-1] + ss[i][j]


for i in range(Q):
    p, q = map(int, input().split())
    ret = 0
    for j in range(p, q+1):
        ret += s[j][q]
    print(ret)

Submission status: Accepted

Solution code:
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())
  l, r = l-1, r-1
  x[l][r] += 1
  
s = [[0]*(n+1) for _ in range(n+1)]
for i in range(n):
  for j in range(n):
    s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + x[i][j]

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

Submission status: Accepted

Solution code:
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)]

# 二次元累積和
rui = [[0] * (n + 1) for _ in range(n + 1)]
for l, r in LR:
  rui[l][r] += 1

for i in range(n):
  for j in range(n+1):
    rui[i+1][j] += rui[i][j]

for i in range(n+1):
  for j in range(n):
    rui[i][j+1] += rui[i][j]

for i, j in PQ:
  print(rui[j][j] + rui[i-1][i-1] - rui[j][i-1] - rui[i-1][j])

Submission status: Accepted

Solution code:
# 2次元imos法

N,M,Q = map(int,input().split())
T = [ [ 0 for _ in range(N+2) ] for _ in range(N+2) ]
for i in range(M):
  L,R = map(int,input().split())
  T[0][R] += 1
  T[L+1][R] -= 1
  T[0][N+1] -= 1
  T[L+1][N+1] += 1
for i in range(N+1):
  for j in range(N+1):
    T[j+1][i] += T[j][i]
for j in range(N+1):
  for i in range(N+1):
    T[j][i+1] += T[j][i]
for i in range(Q):
  p,q = map(int,input().split())
  print(T[p][q])

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
A=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
  a,b=map(int,input().split())
  A[a][b]+=1
B=[[0]*(n+1) for i in range(n+1)]
for i in range(n+1):
  for j in range(n+1):
    if i!=0 and j!=0:
      B[i][j]=B[i-1][j]+B[i][j-1]+A[i][j]-B[i-1][j-1]
    elif i!=0:
      B[i][j]=B[i-1][j]+A[i][j]
    elif j!=0:
      B[i][j]=B[i][j-1]+A[i][j]
    else:
      B[i][j]=A[i][j]
for i in range(q):
  a,b=map(int,input().split())
  print(B[b][b]-B[a-1][b]-B[b][a-1]+B[a-1][a-1])

Submission status: Accepted

Solution code:
def resolve():
    N,M,Q=map(int,input().split())
    mp=[[0 for i in range(N+2)] for i in range(N+1)]
    for _ in range(M):
        L,R=map(int,input().split())

        mp[L][R]+=1
    for i in range(1,N+1):
        for j in range(1,N+1):
            mp[i][j]+=mp[i][j-1]
        #print(i,mp[i])
    for _ in range(Q):
        p,q=map(int,input().split())
        sm=0
        for i in range(p,q+1):
            sm+=mp[i][q]
        print(sm)



if __name__ == "__main__":
    resolve()
    #unittest.main()

Submission status: Accepted

Solution code:

import numpy as np
import sys
sys.setrecursionlimit(100000)



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



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N,M,Q=acinput()

A=np.zeros([N+1,N+1])

for i in range(M):
    tmp=acinput()
    A[tmp[0],tmp[1]]+=1
Acs=np.cumsum(A,axis=1 )
Acs=np.cumsum(Acs,axis=0)

for i in range(Q):
    tmp=acinput()
    print(int(Acs[tmp[1], tmp[1]]-Acs[tmp[1],tmp[0]-1]-Acs[tmp[0]-1,tmp[1]]+Acs[tmp[0]-1, tmp[0]-1]))

Submission status: Accepted

Solution code:
from bisect import bisect_left, bisect_right

n, m, Q = map(int, input().split())
lr = [tuple(map(lambda x: int(x)-1, input().split())) for _ in range(m)]
lr.sort(reverse=True)

fin = []
offset = 0
ans = [[0] * n for _ in range(n)]

for i in range(n)[::-1]:
    while i == lr[offset][0]:
        fin.append(lr[offset][1])
        offset += 1
        if offset == m: break
    fin.sort()
    for j in range(i, n):
        ans[i][j] = bisect_right(fin, j)

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

Submission status: Accepted

Solution code:
from bisect import *
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)]
data=[[] for i in range(N+1)]
for l,r in LR:
    data[l].append(r)
for i in range(1,N):
    data[i].sort()

data2=[[0] for i in range(N+1)]
for i in range(1,N+1):
    for c in range(1,N+1):
        data2[i].append(bisect_right(data[i],c))
#print(data2)
for p,q in PQ:
    count=0
    for i in range(p,q+1):
        count+=data2[i][q]
    print(count)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
train=[[0]*(N+1) for _ in range(N+1)]#iから始まってjで終わる電車の本数
for i in range(M):
    l,r=map(int,input().split())
    train[l][r]+=1

#2次元累積和
for i in range(N):
    for j in range(N):
        train[i+1][j+1]+=train[i][j+1]+train[i+1][j]-train[i][j]
    
for i in range(Q):
    p,q=map(int,input().split())
    print(train[q][q]-train[p-1][q]-train[q][p-1]+train[p-1][p-1])

Submission status: Accepted

Solution code:
import sys
import numpy as np
input = sys.stdin.readline

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

    check = np.zeros((N+1, N+1))

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

    # print(check)
    for i in range(1, N+1):
        check[i] += check[i-1]
    for i in range(1, N+1):
        check[:,i] += check[:,i-1]
    # print(check)

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

#C[i][j]= i==LかつR<=jなる列車の総数(1-indexed)
C=[[0 for _ in range(N+1)] for __ in range(N+1)]

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

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

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
Arr = []
for i in range(n+1):
  Arr.append([0] * (n+1))
for i in range(m):
  l, r = map(int, input().split())
  Arr[l][r] += 1
#print(Arr)

B = []
for i in range(n+1):
  B_line = [0]
  for j in range(1, n+1):
    B_line.append(B_line[-1] + Arr[i][j])
  B.append(B_line)
#print(B)
  
for x in range(q):
  left, right = map(int, input().split())
  train_num = 0
  for i in range(left, right+1):
    train_num += B[i][right] - B[i][left-1]
  print(train_num)

Submission status: Accepted

Solution code:
from itertools import accumulate
N,M,Q = map(int, input().split())
tr = [list(map(int, input().split())) for i in range(M)]
num = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
  a,b = tr[i]
  num[a][b] += 1
acc = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(1,N+1):
    acc[i][j] += acc[i-1][j]+num[i][j]
for i in range(1,N+1):
  for j in range(1,N+1):
    acc[i][j] += acc[i][j-1]
query = [list(map(int,input().split())) for i in range(Q)]
for l,r in query:
  print(acc[r][r]-acc[l-1][r]-acc[r][l-1]+acc[l-1][l-1])

Submission status: Accepted

Solution code:
N, M, K = map(int, input().split())
L = []
R = []
for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
P = []
Q = []
for i in range(K):
    p, q = map(int, input().split())
    P.append(p)
    Q.append(q)

def build_table(L, R):
    s = [[0] * (N+1) for i in range(N+1)]
    for i in range(M):
        s[L[i]][R[i]] += 1
    for i in range(N):
        for j in range(N):
            s[i+1][j+1] += s[i+1][j]
            s[i+1][j+1] += s[i][j+1]
            s[i+1][j+1] -= s[i][j]
    return s

s = build_table(L, R)
for i in range(K):
    p, q = P[i], Q[i]
    ans = s[q][q] - s[q][p-1] - s[p-1][q] + s[p-1][p-1]
    print(ans)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
n, m, Q = map(int, input().split())
memo = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    memo[l][r] += 1

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

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
N,M,Q = map(int,input().split())
num = [[0 for i in range(N)] for j in range(N)]
lr = [list(map(int,input().split())) for i in range(M)]
for l,r in lr:
    num[l-1][r-1] += 1

for j in range(N):
    for i in range(N-1,0,-1):
        num[i-1][j] += num[i][j]
for i in range(N):
    for j in range(N-1):
        num[i][j+1] += num[i][j]
pq = [list(map(int,input().split())) for i in range(Q)]
ans = []
for p,q in pq:
    ans.append(num[p-1][q-1])
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
num = [[0 for i in range(N)] for j in range(N)]
lr = [list(map(int,input().split())) for i in range(M)]
for l,r in lr:
    num[l-1][r-1] += 1

for j in range(N):
    for i in range(N-1,0,-1):
        num[i-1][j] += num[i][j]
for i in range(N):
    for j in range(N-1):
        num[i][j+1] += num[i][j]
pq = [list(map(int,input().split())) for i in range(Q)]
ans = []
for p,q in pq:
    ans.append(num[p-1][q-1])
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
num = [[0 for i in range(N)] for j in range(N)]
lr = [list(map(int,input().split())) for i in range(M)]
for l,r in lr:
    num[l-1][r-1] += 1

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

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
num = [[0 for i in range(N)] for j in range(N)]
lr = [list(map(int,input().split())) for i in range(M)]
for l,r in lr:
    num[l-1][r-1] += 1

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,q = [int(i) for i in input().split()]
lr = [[int(x)-1 for x in input().split()] for i in range(m)]
pq = [[int(x)-1 for x in input().split()] for i in range(q)]
m = [[0]*501 for _ in range(501)]
for l,r in lr:
    m[0][r]+=1
    m[l+1][r]-=1
for i in range(500):
    for j in range(1,500):
        m[j][i]+=m[j-1][i]
for i in range(500):
    for j in range(1,500):
        m[i][j]+=m[i][j-1]
for p,q in pq:
    print(m[p][q])

Submission status: Accepted

Solution code:
###########################################
class Bit():
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
        return
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i
        return
def programer1B():
    N, K = LI()
    A = LI()
    bit = Bit(max(A))
    cur = 0
    for i, a in enumerate(A):
        bit.add(a, 1)
        cur += i + 1 - bit.sum(a)
    As = 0
    A.sort()
    now = 0
    for i in range(1,N):
        if A[i]!=A[i-1]:
            now = i
        As += now
#    print(cur,As)
    ans = (As*(K**2) - (As-2*cur)*K)//2
    ans %=mod
    print(ans)
    return

def ABC106():
    N, M, Q = LI()
    R = []
    for i in range(M):
        l, r = LI()
        R.append([l,r,0])
    for i in range(Q):
        p, q = LI()
        R.append([p,q,i+1])
    R.sort(key=lambda x:x[1])
#    print(R)
    B = Bit(N+1)
    ans = [0]*Q
    for x,y,t in R:
        if t==0:
            B.add(x,1)
        else:
            cur = B.sum(y+1) - B.sum(x-1)
            ans[t-1] = cur
    for v in ans:
        print(v)
    return

####################################################################
import sys, copy, bisect, itertools, heapq, math
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LSI(): return list(map(str, sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod, mod2, inf
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18

if __name__ == '__main__':
#    programer1B()
    ABC106()

Submission status: Accepted

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

# 二次元累積和
# A[i1, j1] -> A[i2, j2] :=
# Acum[i2 + 1][j2 + 1] - Acum[i1][j2 + 1] - Acum[i2 + 1][j1] + Acum[i1][j1]
def two_dim_accumulate(a) -> list:
  h, w = len(a), len(a[0])
  acum = [[0 for _ in range(h + 1)] for _ in range(w + 1)]
  for i in range(h):
    for j in range(w):
      acum[i + 1][j + 1] = a[i][j]
  for i in range(1, h + 1):
    for j in range(1, w + 1):
      acum[i][j] += acum[i][j - 1]
  for j in range(1, w + 1):
    for i in range(1, h + 1):
      acum[i][j] += acum[i - 1][j]
  return acum

A = [[0 for _ in range(N)] for _ in range(N)]
for l, r in LR:
  A[l - 1][r - 1] += 1
Acum = two_dim_accumulate(A)
  
for p, q in PQ:
  print(Acum[q][q] - Acum[p - 1][q] - Acum[q][p - 1] + Acum[p - 1][p - 1])

Submission status: Accepted

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

Acum = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for l, r in LR:
  Acum[l][r] += 1
for i in range(1, N + 1):
  for j in range(1, N + 1):
    Acum[i][j] += Acum[i][j - 1]
for j in range(1, N + 1):
  for i in range(1, N + 1):
    Acum[i][j] += Acum[i - 1][j]
#for i in range(N + 1):
#  print(Acum[i])
  
for p, q in PQ:
  print(Acum[q][q] - Acum[p - 1][q] - Acum[q][p - 1] + Acum[p - 1][p - 1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def main():
    import sys

    input = sys.stdin.readline

    def build_table(h, w, a):
        ret = [[0] * (w + 1) for _ in range(h + 1)]
        for r in range(h):
            for c in range(w):
                ret[r + 1][c + 1] = ret[r + 1][c] + ret[r][c + 1] - ret[r][c] + a[r][c]
        return ret

    def get(p, q, t):
        return t[q][q] - t[p - 1][q] - t[q][p - 1] + t[p - 1][p - 1]

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

    t = [[0] * (n + 1) for _ in range(n + 1)]  # 0-indexed
    for _ in range(m):
        l, r = (int(x) - 1 for x in input().split())  # 0-indexed
        t[l][r] += 1

    t = build_table(n, n, t)  # 1-indexed

    ret = []
    for _ in range(q):
        p, q = map(int, input().split())  # 1-indexed
        ret.append(get(p, q, t))

    print(*ret, sep='\n')


if __name__ == '__main__':
    main()