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 numpy as np

def resolve():
    N, M, Q = map(int, input().split())
    S = np.zeros(((N + 1), (N + 1)))
    for _ in range(M):
        l, r = map(int, input().split())
        # L,Rの区間にある本数
        S[l, r] += 1

    # ゼータ変換（横縦累積和） axis=1:横, axis=0:縦
    S = np.cumsum(S, axis=1).cumsum(axis=0)

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


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.buffer.readline
inf = float("inf")

N, M, Q = map(int, input().split())
l_left = []
l_right = []
for _ in range(M):
    left, right = map(int, input().split())
    l_left.append(left)
    l_right.append(right)

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

# s[left][right] := [1, left], [1, right] の領域に含まれる列車の数
# s[left][right] = s[left-1][right] + s[left][right-1] - s[left-1][right-1] + a[left][right]

s = [[0 for right in range(N + 1)] for left in range(N + 1)]

for i in range(M):
    left = l_left[i]
    right = l_right[i]
    s[left][right] += 1

for left in range(1, N + 1):
    for right in range(1, N + 1):
        s[left][right] += s[left-1][right] + s[left][right-1] - s[left-1][right-1]

for left, right in l_query:
    res = s[right][right] - s[right][left-1] - s[left-1][right] + s[left-1][left-1]
    print(res)

Submission status: Accepted

Solution code:

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

    # 二次元累積和
    for i in range(1, N+1):
        for j in range(1, N+1):
            cum_A[i][j] += cum_A[i-1][j] + cum_A[i][j-1] - cum_A[i-1][j-1]

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

        print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Accepted

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

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

query = [tuple(map(int, input().split())) for _ in range(Q)]

"""
l~rの間を走ってるやつ
→ {l~l + l~l+1 + l~l+2 + ... + l~r} + {l+1~l+1 + l+1~l+2 + ... + l+1~r} + ... + {r~r}
の発想
"""
accum = [[0 for _ in range(N)] for _ in range(N)]

for l in range(N):
    for r in range(l,N):
        if l == r:
            accum[l][r] = train[l][r]
        else:
            # l始まりでrまでのどこかに行くやつ = l始まりでr-までのどこかに行くやつ + l始まりでrまで行くやつ
            accum[l][r] = accum[l][r-1] + train[l][r]


for p,q in query:
    cnt = 0
    # l~rの間に完全に収まるもの = l始まりでrまでのどこかで止まるもの + l+1始まりでrまでのどこかで止まるもの + ... + r-1始まりでrまでのどこかで止まるもの + r始まりでrまでのどこかで止まるもの
    for i in range(p-1,q):
        cnt += accum[i][q-1]

    print(cnt)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
try:
    from typing import List
except ImportError:
    pass


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    t = [[0] * (N + 1) for _ in range(N + 1)]
    for Li, Ri in zip(L, R):
        Li -= 1
        Ri -= 1
        t[Li + 1][Ri + 1] += 1
    for i in range(N):
        for j in range(N + 1):
            t[i + 1][j] += t[i][j]
    for i in range(N + 1):
        for j in range(N):
            t[i][j + 1] += t[i][j]
    for pi, qi in zip(p, q):
        pi -= 1
        qi -= 1
        print(t[N][qi + 1] - t[pi][qi + 1])


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    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()

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
G = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, input().split())
    G[l][r] += 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        G[i][j] += G[i - 1][j] + G[i][j - 1] - G[i - 1][j - 1]
p = [list(map(int, input().split())) for _ in range(q)]
for u in p:
    s, t = u[0] - 1, u[1]
    print(G[s][s] + G[t][t] - (G[s][t] + G[t][s]))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

n,m,q=map(int,input().split())
T=[]
for i in range(m):
    l,r=map(int,input().split())
    T.append([l-1,r-1])

C=[[0]*n for i in range(n)] #C[始点][終点]=個数
for t in T:
    C[t[0]][t[1]]+=1

A=[[0]*n for i in range(n)] #A[始点][終点]=区間内の合計
for i in range(1,n+1): #iは区間の長さ
    for j in range(n-i+1): #jからj+i-1まで
        if i==1:
            A[j][j]=C[j][j]
        elif i==2:
            A[j][j+1]=A[j][j]+A[j+1][j+1]+C[j][j+1]
        else:
            A[j][j+i-1]=A[j][j+i-2]+A[j+1][j+i-1]-A[j+1][j+i-2]+C[j][j+i-1]

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

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
l = [[0]*(n) for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    l[a-1][b-1] += 1


for i in range(n):
    for j in range(n):
        if i != 0:
            l[i][j] += l[i-1][j]
        if j != 0:
            l[i][j] += l[i][j-1]
        if i!= 0 and j != 0:
            l[i][j] -= l[i-1][j-1]
    

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n, m, q = map(int, readline().split())
lr = [list(map(int, readline().split())) for _ in range(m)]
cnt = [[0] * (n + 1) for _ in range(n + 1)]
for l, r in lr:
    cnt[l][r] += 1
cnt = np.cumsum(cnt, axis=0).cumsum(axis=1).tolist()
for _ in range(q):
    p, q = map(int, readline().split())
    p -= 1
    ans = cnt[q][q] + cnt[p][p]
    ans -= cnt[q][p] + cnt[p][q]
    print(ans)

Submission status: Accepted

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

# for i in range(N):
#     for j in range(N):
#         X[i+1][j+1] += X[i][j+1] + X[i+1][j]
# print(*X, sep='\n')
# print('')

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

for i in range(N+1):
    for j in range(N):
        X[j+1][i] += X[j][i]
# print(*X, sep='\n')

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

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

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
s = [[0 for j in range(501)] for i in range(501)]

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

# 二次元累積和
for i in range(1,501):
    for j in range(1,501):
        s[i][j] += s[i-1][j] + s[i][j-1] - s[i-1][j-1]

# クエリに対してO(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:
N,M,Q = map(int,input().split())
s = [[0 for j in range(501)] for i in range(501)]

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

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

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


for i in range(1,Q+1):
  print(m[q[i]][q[i]]+m[p[i]-1][p[i]-1]-m[q[i]][p[i]-1]-m[p[i]-1][q[i]])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

n, m, q_ = map(int, input().split())
acc = [[0]*(n+1) for _ in range(n+1)] # 最初に[0]を足しとく

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

#ヨコに累積和
for i in range(1,n+1):
    for j in range(1,n+1):
        acc[i][j] += acc[i-1][j]
#タテに累積和
for i in range(1,n+1):
    for j in range(1,n+1):
        acc[i][j] += acc[i][j-1]

ans = [0]*q_

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

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

Submission status: Accepted

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

N, M, Q = map(int, input().split())
city = np.zeros((N + 2, N + 1), dtype=np.int)

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

np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

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

Submission status: Accepted

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

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):
    p,q = map(int,input().split())
    ans[i] = S[q][q] - S[p-1][q] - S[q][p-1] + S[p-1][p-1]

print("\n".join(map(str,ans)))

Submission status: Accepted

Solution code:
n,m,Q = map(int,input().split())
lr = [list(map(int,input().split())) for _ in range(m)]
lr.sort(key=lambda x:(x[0],x[1]))
ans = [[0]*(n+1) for _ in range(n+1)]
now = 0
for i in range(1,n+1):
  j = 1
  while True:
    if now < m:
      if lr[now][1] == j and lr[now][0] == i:
        ans[i][j] += (ans[i][j]==0)*(ans[i][j-1]) + 1
        now += 1
      else:
        j += 1
        if j <= n:
          ans[i][j] = ans[i][j-1]
        else:
          break
    else:
      j += 1
      if j <= n:
        ans[i][j] = ans[i][j-1]
      else:
        break
ans2 = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
  for j in range(1,n+1):
    if i == 1:
      ans2[i][j] = ans[i][j]
    else:
      ans2[i][j] = ans2[i-1][j] + ans[i][j]
for i in range(Q):
  p,q = map(int,input().split())
  print(ans2[q][q]-ans2[p-1][q])

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
def ruiseki(a):
    l=[0]
    for i in range(len(a)):
        l.append(l[i]+a[i])
    del l[0]
    return l
l=[]
def niruiseki(a):
    l.append(ruiseki(a[0]))
    for i in range(1,len(a)):
        p=[l[i-1][0]+a[i][0]]
        q=[a[i][0]]
        for j in range(1,len(a[i])):
            q.append(q[j-1]+a[i][j])
            p.append(q[j]+l[i-1][j])
        l.append(p)
ll=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    ll[a][b]+=1
niruiseki(ll)
for i in range(q):
    a,b=map(int,input().split())
    print(l[b][b]+l[a-1][a-1]-l[a-1][b]-l[b][a-1])

Submission status: Accepted

Solution code:
def main():
    N,M,Q=map(int,input().split())
    p=[[0 for i in range(509)] for j in range(509)]

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

main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

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

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

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

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

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

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
N,M,Q=list(map(int,input().split()))
t=[list(map(int,input().split())) for _ in range(M)]
query=[list(map(int,input().split())) for _ in range(Q)]

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

for l,r in t:
    train[l][r]+=1

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

for p,q in query:
    tmp=0
    for l in range(p,q+1):
        tmp+=c[l][q]-c[l][p-1]
    
    print(tmp)

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]
Y = [list(map(int, input().split())) for _ in range(Q)]

grid = [[0] * (N + 1) for _ in range(N + 1)]
for l, r in X:
    grid[l][r] += 1

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

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

for p, q in Y:
    print(grid[q][q] + grid[p - 1][p - 1] - grid[p - 1][q] - grid[q][p - 1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

n,m,q= map(int, input().split())
a= [list(map(int, input().split())) for i in range(m)]
b= [list(map(int, input().split())) for i in range(q)]


# ２次元累積和
c=[[0]*(n+1) for i in range(n+1)]
for i,j in a:
    c[i][j]+=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]-c[i-1][j-1]

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

Submission status: Accepted

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

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

# cum
for i in range(n + 1):
    for j in range(n):
        trains[i][j + 1] += trains[i][j]

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

class TwoDimSum():
    def __init__(self, h, w):
        self.h = h
        self.w = w
        self.counts = [[0 for _ in range(w+1)] for _ in range(h+1)]
        self.s = [[0 for _ in range(w+1)] for _ in range(h+1)]

    def add_count(self, x, y):
        # 1-indexed
        self.counts[y][x] += 1

    def build(self):
        for i in range(self.h):
            for j in range(self.w):
                self.s[i+1][j+1] = self.s[i][j+1] + self.s[i+1][j] - self.s[i][j] + self.counts[i+1][j+1]

    def solve(self, x1, y1, x2, y2):
        # 1-indexed
        # (x1, y1): left up
        # (x2, y2): right down
        return self.s[x2][y2] - self.s[x1-1][y2] - self.s[x2][y1-1] + self.s[x1-1][y1-1]

counts = TwoDimSum(n, n)
for _ in range(m):
    l, r = map(int, input().split())
    counts.add_count(l, r)
counts.build()

ans = []
for i in range(q):
    x, y = map(int, input().split())
    ans.append(str(counts.solve(x, x, y, y)))
print("\n".join(ans))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline

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

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

s = [[0 for _ in range(n+1)] for _ in range(n+1)]
# 横方向
for i in range(n+1):
    v = 0
    for j in range(n+1):
        v += counts[i][j]
        s[i][j] = v
# 縦方向
cs = [[0 for _ in range(n+1)] for _ in range(n+1)]
for i in range(n+1):
    v = 0
    for j in range(n+1):
        v += s[j][i]
        cs[j][i] = v


ans = []
for i in range(q):
    p, q = map(int, input().split())
    t = 0
    for i in range(p, q+1):
        t += s[i][q] - s[i][p-1]
    ans.append(str(t))
print("\n".join(ans))

Submission status: Accepted

Solution code:
def submit():
    n, m, q = map(int, input().split())
    rng = {i: [0 for _ in range(n + 1 - i)] for i in range(1, n + 1)}
    for _ in range(m):
        l, r = map(int, input().split())
        rng[l][r - l] += 1
    
    for i in range(1, n + 1):
        for j in range(n - i):
            rng[i][j + 1] += rng[i][j]

    ans = []
    for _ in range(q):
        pl, pr = map(int, input().split())
        # plから始まり, pr - pl以下で終わる列車を数える
        cnt = 0
        for i, ppl in enumerate(range(pl, pr + 1)):
            cnt += rng[ppl][pr - pl - i]
        ans.append(cnt)

    for a in ans:
        print(a)
            

submit()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M, Q = [int(x) for x in input().split()]
L = [0] * M
R = [0] * M
p = [0] * Q
q = [0] * Q
for i in range(M):
    L[i], R[i] = [int(x) for x in input().split()]
for j in range(Q):
    p[j], q[j] = [int(x) for x in input().split()]

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

for i in range(M): # すべての列車について
    train[L[i]][R[i]] += 1

for col in range(1, N + 1):
    for row in range(col, 0, -1):
        train[row][col] += train[row][col - 1] + train[row + 1][col] - train[row + 1][col - 1]

for j in range(Q):
    print(train[p[j]][q[j]])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M, Q = [int(x) for x in input().split()]
L = [0] * M
R = [0] * M
p = [0] * Q
q = [0] * Q
for i in range(M):
    L[i], R[i] = [int(x) for x in input().split()]
for j in range(Q):
    p[j], q[j] = [int(x) for x in input().split()]

train = [[0 for i in range(N + 1)] for _ in range(N + 1)]
seg = [[0 for i in range(N + 1)] for _ in range(N + 2)]

for i in range(M): # すべての列車について
    train[L[i]][R[i]] += 1

for col in range(1, N + 1):
    for row in range(col, 0, -1):
        seg[row][col] = train[row][col] + seg[row][col - 1] + seg[row + 1][col] - seg[row + 1][col - 1]

for j in range(Q):
    print(seg[p[j]][q[j]])

Submission status: Accepted

Solution code:
N, M, Q = [int(x) for x in input().split()]
L = [0] * M
R = [0] * M
p = [0] * Q
q = [0] * Q
for i in range(M):
    L[i], R[i] = [int(x) for x in input().split()]
for j in range(Q):
    p[j], q[j] = [int(x) for x in input().split()]

train = [[0 for i in range(N + 1)] for _ in range(N + 1)]
seg = [[0 for i in range(N + 1)] for _ in range(N + 2)]

for i in range(M): # すべての列車について
    train[L[i]][R[i]] += 1

for col in range(1, N + 1):
    for row in range(col, 0, -1):
        seg[row][col] = train[row][col] + seg[row][col - 1] + seg[row + 1][col] - seg[row + 1][col - 1]

for j in range(Q):
    print(seg[p[j]][q[j]])

Submission status: Accepted

Solution code:
N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if i == 0:
            r[i][j] = p[i][j] + r[i][j-1]      
        elif j == 0:
            r[i][j] = p[i][j] +r[i-1][j]
        else:
            r[i][j] = r[i-1][j] + r[i][j-1] - r[i-1][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    if Qlist[i][0] == 1:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1]
    else:
        b = r[Qlist[i][1]-1][Qlist[i][1]-1] - r[Qlist[i][0]-2][Qlist[i][1]-1]
    print(b)

Submission status: Accepted

Solution code:
import itertools as itr

def main():
	N, M, Q = list(map(int, input().split()))
	LR      = [map(int, input().split()) for _ in range(M)]
	pq      = [map(int, input().split()) for _ in range(Q)]

	cnt = [[0 for _ in range(N+10)] for _ in range(N+10)]
	for L, R in LR:
		cnt[L][R] += 1
	
	for i, j in itr.product(range(N+1), repeat = 2):
		cnt[i+1][j] += cnt[i][j]
	for i, j in itr.product(range(N+1), repeat = 2):
		cnt[i][j+1] += cnt[i][j]

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

	return


main()

Submission status: Accepted

Solution code:
from collections import Counter

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

da[1][1] = c[1][1]
        
for i in range(2,n+1):
    da[1][i] = da[1][i-1] + c[1][i]    
for i in range(2,n+1):
    co = 0
    for j in range(1,n+1):
        co += c[i][j]
        da[i][j] = da[i-1][j] + co
    
for i in range(q):
    pp,qq =  map(int,input().split())
    ans = 0
    ans = da[qq][qq] - da[pp-1][qq] - da[qq][pp-1] + da[pp-1][pp-1]
    
    print(ans)

Submission status: Accepted

Solution code:
# 累積和(2次元)を用いた解法
from itertools import accumulate
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M,Q,*lr = map(int, read().split())

    LR = [[0]*(N+1) for _ in range(N+1)]
    query = []
    for i, (l, r) in enumerate(zip(*[iter(lr)]*2)):
        if i < M:
            LR[l][r] += 1
        else:
            query.append((l, r))
    
    for i in range(1,N+1):
        LR[1][i] += LR[1][i-1]
        LR[i][1] += LR[i-1][1]
    
    for i in range(2, N+1):
        for j in range(2,N+1):
            LR[i][j] += LR[i-1][j] + LR[i][j-1] - LR[i-1][j-1]
    
    for p, q in query:
        ans = LR[q][q] - LR[p-1][q] - LR[q][p-1] + LR[p-1][p-1]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    N,M,Q = map(int,input().split())
    cum = np.zeros((N+1,N+1),dtype=int)
    
    for i in range(M):
        l,r = map(int,input().split())
        cum[l,r] += 1

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
num = [[0]*500 for _ in range(500)]

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

cum = [[0]*500 for _ in range(500)]
for r in range(500):
  cum[r][r] = num[r][r]
for r in range(1,500):
  for l in range(r-1,-1,-1):
    cum[r][l] = cum[r-1][l]+cum[r][l+1]-cum[r-1][l+1]+num[r][l]
#print(cum)
ans = []
for i in range(Q):
  P,Q = map(int, input().split())
  ans.append(cum[Q-1][P-1])
print(*ans,sep='\n')

Submission status: Accepted

Solution code:
n, m, k = map(int, input().split())
R = [[0]*n for _ in range(n)]
for _ in range(m):
  l, r = map(int, input().split())
  l -= 1
  r -= 1
  R[r][l] += 1

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

#[print(R[i]) for i in range(n)]
for _ in range(k):
  p, q = map(int, input().split())
  print(R[q-1][p-1])

Submission status: Accepted

Solution code:
NN = 202020
MOD = 10**9+7
INF = float("inf")


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

trains = [[0]*(n+1) for _ in range(n+1)]
cum = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    trains[train[i][0]][train[i][1]] += 1

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

# print(trains)
# print(cum)
for i in range(q):
    start, end = query[i]
    ans = cum[end][end] - cum[end][start-1] - cum[start-1][end] + cum[start-1][start-1]
    print(ans)

Submission status: Accepted

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

for q in range(n):
    for p in reversed(range(1, n)):
        M[q][p-1] += M[q][p]
for p in range(n):
    for q in range(n-1):
        M[q+1][p] += M[q][p]

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

Submission status: Accepted

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

for q in range(n):
    for p in reversed(range(1,n)):
        M[q][p-1]+=M[q][p]
for p in range(n):
    for q in range(n-1):
        M[q+1][p]+=M[q][p]        

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

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
ans=[[0 for _ in range(n+1)] for _ in range(n+1)]
for _ in range(m):
    l,r=map(int,input().split())
    ans[l][r]+=1
#print(ans)
for l in range(2,n+1):
    for i in range(1,n+1):
        j=i+l-1
        if j>n or i+1>n:
            continue
        if i+1<=j-1:
            ans[i][j]+=ans[i][j-1]+ans[i+1][j]-ans[i+1][j-1]
        else:
            ans[i][j]+=ans[i][j-1]+ans[i+1][j]
#print(ans)
for _ in range(q):
    p,q=map(int,input().split())
    print(ans[p][q])

Submission status: Accepted

Solution code:
import sys
from collections import defaultdict

input=sys.stdin.readline

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

#dp[i][j]:i+1<=l,r==j+1となるものの個数
dp=[[0 for i in range(0,N)] for j in range(0,N)]
for i in range(0,N):
    dp[i][i]=rail[(i+1,i+1)]

for j in range(0,N):
    for i in range(0,j):
        k=j-1-i
        dp[k][j]=dp[k+1][j]+rail[(k+1,j+1)]

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

for i in range(0,N):
    ans[i][i]=dp[i][i]

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

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

for i in range(0,Q):
    print(x[i])

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
line=[[0]*(n+1) for i in range(n+1)]
for _ 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 _ in range(q):
  l,r=map(int,input().split())
  print(line[r][r]-line[r][l-1]-line[l-1][r]+line[l-1][l-1])

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
MAP = [[0] * N for i in range(N)]
for i in range(M):
  L, R = map(int, input().split())
  MAP[L-1][R-1] += 1

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

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

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

Submission status: Accepted

Solution code:
#!/usr/bin/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, m, q = map(int, input().split())
  counts = numpy.zeros((n+1, n+1), dtype=numpy.int)
  for _ in range(m):
    l, r = map(int, input().split())
    counts[l, r] += 1
  
  cusum = counts.cumsum(0).cumsum(1)
  for _ in range(q):
    p, q = map(int, input().split())
    
    if p-1 < 1:
      print(cusum[q, q])
    else:
      print(cusum[q, q] - cusum[p-1, q] - cusum[q, p-1] + cusum[p-1, p-1])

if __name__=='__main__':
  main()