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

N, M, K = map(int, input().split())

LR = np.zeros(shape=(N + 1, N + 1), dtype=np.int32)
L, R = np.array([input().split() for _ in range(M)], dtype=np.int32).T
np.add.at(LR, (L, R), 1)

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

P, Q = np.array([input().split() for _ in range(K)], dtype=np.int32).T

P -= 1
ans = LR[Q, Q] - LR[P, Q] - LR[Q, P] + LR[P, P]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import numpy as np

N, M, K = map(int, input().split())

LR = np.zeros(shape=(N + 1, N + 1), dtype=np.int32)
for _ in range(M):
    L, R = map(int, input().split())
    LR[L, R] += 1

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

P, Q = np.array([input().split() for _ in range(K)], dtype=np.int32).T

P -= 1
ans = LR[Q, Q] - LR[P, Q] - LR[Q, P] + LR[P, P]
print(*ans, sep='\n')

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
tracks = [[] for i in range(N)]
for i in range(M):
    L, R = map(int, input().split())
    tracks[L-1].append(R-1)
    
for track in tracks: track.sort()

ans = [[None for j in range(N)] for i in range(N)]
for L in range(N):
    cur = 0
    tot = 0
    for R in range(L, N):
        while cur < len(tracks[L]) and tracks[L][cur] <= R:
            cur += 1
            tot += 1
        ans[L][R] = tot

dp =[[None for i in range(N)] for j in range(N)]
for i in range(Q):
    p, q = map(int, input().split())
    if dp[p-1][q-1] == None:
        dp[p-1][q-1] = sum(ans[i][q-1] for i in range(p-1, q))
    print(dp[p-1][q-1])

Submission status: Accepted

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

Submission status: Accepted

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

for d in range(1, N):
    for p in range(N - d):
        q = p + d
        LR[p][q] += LR[p + 1][q] + LR[p][q - 1] - LR[p + 1][q - 1]

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

Submission status: Accepted

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

lr.sort()
t=[[0 for _ in range(n)] for _ in range(n)]

for slr in lr:
    t[slr[0]-1][slr[1]-1] += 1

nt = [[0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        nt[i].append(nt[i][j] + t[i][j])

for spq in pq:
    p,q = spq[0],spq[1]
    res = 0
    for i in range(p-1,q):
        res += nt[i][q] - nt[i][p-1]
    print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
class SegmentTree(object):
    def __init__(self,A,dot,e):
        n=2**((len(A)-1).bit_length())
        self.__n=n
        self.__dot=dot
        self.__e=e
        self.__node=[e]*(2*n)
        for i in range(len(A)):
            self.__node[i+n]=A[i]
        for i in range(n-1,-0,-1):
            self.__node[i]=dot(self.__node[2*i],self.__node[2*i+1])

    def add(self,i,c):
        i+=self.__n
        node=self.__node
        node[i]=self.__dot(node[i],c)
        while(i!=1):
            i//=2
            node[i]=self.__dot(node[2*i],node[2*i+1])

    def sum(self,l,r):
        vl,vr=self.__e,self.__e
        l+=self.__n; r+=self.__n
        while(l<r):
            if(l%2==1):
                vl=self.__dot(vl,self.__node[l])
                l+=1
            l//=2
            if(r%2==1):
                r-=1
                vr=self.__dot(self.__node[r],vr)
            r//=2
        return self.__dot(vl,vr)

def resolve():
    n,m,Q=map(int,input().split())
    X=[0]*(m+Q)
    for i in range(m):
        l,r=map(int,input().split())
        l-=1; r-=1
        X[i]=(0,l,r,i)
    for i in range(Q):
        l,r=map(int,input().split())
        l-=1; r-=1
        X[m+i]=(1,l,r,i)
    X.sort(lambda x:(x[2],x[0])) # 右端の昇順、先に一点追加してからクエリに答える

    from operator import add
    tree=SegmentTree([0]*n,add,0)
    ans=[0]*Q
    for x,l,r,i in X:
        if(x==0):
            tree.add(l,1)
        else:
            ans[i]=tree.sum(l,r+1)

    for a in ans: print(a)
resolve()

Submission status: Accepted

Solution code:
"""
22:40:00

"""
N, M, Q = map(int, input().split())

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

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

for i in range(1,N+1):
    for j in range(1,N+1):
        accs[i][j] = fields[i][j] + accs[i-1][j] + accs[i][j-1] - accs[i-1][j-1]
# print(accs)
ans = []
for i in range(Q):
    p,q = map(int, input().split())
    ans.append(accs[q][q] - accs[p-1][q])
    print(accs[q][q] - accs[p-1][q])
# print(*ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    n,m,q=map(int,input().split())
    A=[[0]*n for _ in range(n)]
    for _ in range(m):
        l,r=map(int,input().split())
        l-=1; r-=1
        A[l][r]+=1
    S=[[0]*(n+1) for _ in range(n+1)]
    from itertools import product
    for i,j in product(range(n),repeat=2):
        S[i+1][j+1]=A[i][j]+S[i][j+1]+S[i+1][j]-S[i][j]
    for _ in range(q):
        l,r=map(int,input().split())
        print(S[r][r]-S[l-1][r]-S[r][l-1]+S[l-1][l-1])
resolve()

Submission status: Accepted

Solution code:
import itertools
import numpy as np
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)]

x=[[0]*(501) for i in range(501)]
x=np.array(x)
for i in range(m):
    x[a[i][0],a[i][1]]+=1



for i in range(501):
    x[i] = list(itertools.accumulate(x[i]))
  
for i in range(501):
    x[:,i] = list(itertools.accumulate(x[:,i]))



for i in range(q):
    print(x[b[i][1],b[i][1]]-x[b[i][1],b[i][0]-1]-x[b[i][0]-1,b[i][1]]+x[b[i][0]-1,b[i][0]-1])

Submission status: Accepted

Solution code:
import numpy as np
import sys

n, m, q = map(int, input().split())
ab = np.array(sys.stdin.read().split(), np.int)
a = ab[:m*2].reshape(m, 2)
b = ab[m*2:].reshape(q, 2)

x=np.zeros((501, 501), dtype=np.int)

np.add.at(x, (a[:, 0], a[:, 1]), 1)

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

ans = x[b[:, 1], b[:, 1]] - x[b[:, 1], b[:, 0]-1] - x[b[:, 0]-1, b[:, 1]] + x[b[:, 0]-1, b[:, 0]-1]
for i in range(q):
    print(ans[i])

Submission status: Accepted

Solution code:
import numpy as np
import sys

n, m, q = map(int, input().split())
ab = np.array(sys.stdin.read().split(), np.int)
a = ab[:m*2].reshape(m, 2)
b = ab[m*2:].reshape(q, 2)

x=np.zeros((501, 501), dtype=np.int)

np.add.at(x, (a[:, 0], a[:, 1]), 1)

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

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2, v2]
    a2=x[v2, v1-1]
    a3=x[v1-1, v2]
    a4=x[v1-1, v1-1]
    print(a1-a2-a3+a4)

Submission status: Accepted

Solution code:
import numpy as np

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

x=np.zeros((501, 501), dtype=np.int)

np.add.at(x, (a[:, 0], a[:, 1]), 1)

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

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2, v2]
    a2=x[v2, v1-1]
    a3=x[v1-1, v2]
    a4=x[v1-1, v1-1]
    print(a1-a2-a3+a4)

Submission status: Accepted

Solution code:
import numpy as np

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

x=np.zeros((501, 501), dtype=np.int)

for i in range(m):
    x[a[i][0], a[i][1]]+=1

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

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2, v2]
    a2=x[v2, v1-1]
    a3=x[v1-1, v2]
    a4=x[v1-1, v1-1]
    print(a1-a2-a3+a4)

Submission status: Accepted

Solution code:
import numpy as np

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

x=np.zeros((501, 501), dtype=np.int)

for i in range(m):
    x[a[i][0], a[i][1]]+=1

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

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2, v2]
    a2=x[v2, v1-1]
    a3=x[v1-1, v2]
    a4=x[v1-1, v1-1]
    print(a1-a2-a3+a4)

Submission status: Accepted

Solution code:
import itertools
import numpy as np
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)]

x=[[0]*(501) for i in range(501)]

for i in range(m):
    x[a[i][0]][a[i][1]]+=1



for i in range(501):
    x[i] = list(itertools.accumulate(x[i]))
  
x=np.array(x)
for i in range(501):
    x[:,i] = list(itertools.accumulate(x[:,i]))



for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2,v2]
    a2=x[v2,v1-1]
    a3=x[v1-1,v2]
    a4=x[v1-1,v1-1]
    print(a1-a2-a3+a4)

Submission status: Accepted

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

for _ 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+1][j] + X[i][j+1] - X[i][j]

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

Submission status: Accepted

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

N,M,Q = map(int,readline().split())
lines = readlines()
L,R = np.array([line.split() for line in lines[:M]],np.int32).T
P,Q = np.array([line.split() for line in lines[M:]],np.int32).T

cnt = np.zeros((N+1,N+1),dtype=np.int32)
np.add.at(cnt,(L,R),1)

np.cumsum(cnt,axis=0,out=cnt)
np.cumsum(cnt,axis=1,out=cnt)
P -= 1
x = cnt[Q,Q] - cnt[Q,P] - cnt[P,Q] + cnt[P,P]
print(*x,sep="\n")

Submission status: Accepted

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

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


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

Submission status: Accepted

Solution code:
# D - AtCoder Express 2

import numpy as np
import sys

N, M, Q = map(int, sys.stdin.buffer.readline().split())
LRpq = np.array(sys.stdin.buffer.read().split(), np.int64)
L = LRpq[:2*M:2]
R = LRpq[1:2*M:2]
p = LRpq[2*M::2]
q = LRpq[2*M+1::2]
    
train = np.zeros((N+1, N+1))
np.add.at(train, (L,R), 1)

np.cumsum(train, axis = 0, out = train)
np.cumsum(train, axis = 1, out = train)
    
ans = train[q,q] - train[p-1,q] - train[q,p-1] + train[p-1,p-1]
for i in range(Q):
    print(int(ans[i]))

Submission status: Accepted

Solution code:
# D - AtCoder Express 2

import numpy as np
import sys

N, M, Q = map(int, input().split())
LRpq = np.array(sys.stdin.read().split(), np.int64)
L = LRpq[:2*M:2]
R = LRpq[1:2*M:2]
p = LRpq[2*M::2]
q = LRpq[2*M+1::2]
    
train = np.zeros((N+1, N+1))
np.add.at(train, (L,R), 1)

np.cumsum(train, axis = 0, out = train)
np.cumsum(train, axis = 1, out = train)
    
ans = train[q,q] - train[p-1,q] - train[q,p-1] + train[p-1,p-1]
for i in range(Q):
    print(int(ans[i]))

Submission status: Accepted

Solution code:
# D - AtCoder Express 2

import numpy as np

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

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

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

Submission status: Accepted

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
inf=float("inf")
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)]
x=[[0]*n for i in range(n)]
for i in range(m):
    x[lr[i][0]-1][lr[i][1]-1]+=1
# print(x)
rui=[[0]*(n+1) for i in range(n+1)]
for i in range(n):
    for j in range(n):
        rui[i+1][j+1]=rui[i][j+1]+rui[i+1][j]-rui[i][j]+x[i][j]
# print(rui)
for i in range(q):
    print(rui[pq[i][1]][pq[i][1]] - rui[pq[i][0]-1][pq[i][1]] - rui[pq[i][1]][pq[i][0]-1] + rui[pq[i][0]-1][pq[i][0]-1])

Submission status: Accepted

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

a=list()

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][j-1] 

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

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

for i in range(q):
  print(a[i])

Submission status: Accepted

Solution code:
import numpy as np

def main():
	n, m, q, *L = map(int, open(0).read().split())
	lr = L[:2 * m]
	pq = L[2 * m:]
	arr = np.zeros((n + 1, n + 1), int)
	for l, r in zip(*[iter(lr)] * 2):
		arr[l, r] += 1
	arr = np.cumsum(arr, 0)
	arr = np.cumsum(arr, 1)
	for p, q in zip(*[iter(pq)] * 2):
		print(arr[q, q] - arr[p - 1, q] - arr[p, p - 1] + arr[p - 1, p - 1])


if __name__ == "__main__":
	main()

Submission status: Accepted

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

N, M, Q = map(int, buf.readline().split())
city = np.zeros((N + 1, N + 1), np.int32)
LRpq = np.array(buf.read().split(), np.int32)

L = LRpq[:2 * M:2]
R = LRpq[1:2 * M:2]
p = LRpq[2 * M::2]
q = LRpq[2 * M + 1::2]

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

Submission status: Accepted

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

N, M, Q = map(int, buf.readline().split())
city = np.zeros((N + 1, N + 1), np.int32)
LRpq = np.array(buf.read().split(), np.int32)

LR = LRpq[:2 * M]
L = LR[::2]
R = LR[1::2]

pq = LRpq[2 * M:]
p = pq[::2]
q = pq[1::2]

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
import numpy as np
import sys
line = sys.stdin.readlines()

N, M, Q = map(int, line[0].split())
city = np.zeros((N + 1, N + 1), dtype='int32')
L, R = np.array(list(map(str.split, line[1:M + 1])), np.int32).T
p, q = np.array(list(map(str.split, line[M + 1:])), np.int32).T

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
import numpy as np
import sys
readlines = sys.stdin.readlines()

N, M, Q = map(int, readlines[0].split())
city = np.zeros((N + 1, N + 1), dtype='int32')
L, R = np.array([i.split() for i in readlines[1:M + 1]], dtype='int32').T
p, q = np.array([i.split() for i in readlines[M + 1:]], dtype='int32').T

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
import numpy as np
import sys


def main():
    readlines = sys.stdin.readlines()

    N, M, Q = map(int, readlines[0].split())
    city = np.zeros((N + 1, N + 1), dtype=int)
    L, R = np.array([i.split() for i in readlines[1:M + 1]], dtype=int).T
    p, q = np.array([i.split() for i in readlines[M + 1:]], dtype=int).T

    np.add.at(city, (L, R), 1)
    np.cumsum(city, axis=0, out=city)
    np.cumsum(city, axis=1, out=city)

    p -= 1
    answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
    print('\n'.join(answer.astype(str)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
readlines = sys.stdin.readlines()

N, M, Q = map(int, readlines[0].split())
city = np.zeros((N + 1, N + 1), dtype=int)
L, R = np.array([i.split() for i in readlines[1:M + 1]], dtype=int).T
p, q = np.array([i.split() for i in readlines[M + 1:]], dtype=int).T

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
import numpy as np
import sys
readlines = sys.stdin.readlines()

N, M, Q = map(int, readlines[0].split())
city = np.zeros((N + 2, N + 1), dtype=int)
L, R = np.array([i.split() for i in readlines[1:M + 1]], dtype=int).T
pq = [map(int, i.split()) for i in readlines[M + 1:]]

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

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

Submission status: Accepted

Solution code:
def main():
    import numpy as np
    import sys
    input = sys.stdin.readline

    N, M, Q = map(int, input().split())
    # city[L][R]
    city = [[0] * (N + 1) for _ in range(N + 2)]

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

    city = np.array(city).reshape(N + 2, N + 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])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

N, M, Q = map(int, input().split())
# city[L][R]
city = [[0] * (N + 1) for _ in range(N + 2)]

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

city = np.array(city).reshape(N + 2, N + 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())
d=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    l,r=map(int,input().split())
    d[l][r]+=1
for i in range(1,n+1):
    for j in range(1,n+1):
        d[i][j]+=d[i][j-1]
pq=[list(map(int,input().split())) for i in range(Q)]
for u in pq:
    p,q=u
    ans=0
    for i in range(p,q+1):
        ans+=d[i][q]
    print(ans)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
b=[501*[0]for i in range(501)]
for i in range(m):
  r,l=map(int,input().split())
  b[r][l]+=1
for i in range(501):
  for j in range(1,501):b[i][j]+=b[i][j-1]
for i in range(1,501):
  for j in range(501):b[i][j]+=b[i-1][j]
for i in range(q):
  l,r=map(int,input().split())
  print(b[r][r]-b[l-1][r]-b[r][l-1]+b[l-1][l-1])
#  >>優しい言葉を投げかければそのコードはACする<<

Submission status: Accepted

Solution code:
N, M, Q = [int(str) for str in input().strip().split()]
LR = [[int(str) for str in input().strip().split()] for _ in range(M)]
pq = [[int(str) for str in input().strip().split()] for _ in range(Q)]

LRmap = [[0] * N for _ in range(N)]
for l, r in LR:
    LRmap[l - 1][r - 1] += 1

sums = [[0] * (N + 1) for _ in range(N + 1)]
sums[0][0] = 0
for l in range(1, N + 1):
    for r in range(1, N + 1):
        sums[l][r] = sums[l - 1][r] + sums[l][r - 1] - sums[l - 1][r - 1] + LRmap[l - 1][r - 1]

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

Submission status: Accepted

Solution code:
from collections import  Counter
n,m,q=map(int,input().split())
h=[[0]*(n) for _ in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    l-=1
    r-=1
    h[n-1-l][r]+=1
ans=0
for i in range(n):
    for j in range(n-1):
        h[i][j+1] += h[i][j]
 
for j in range(n):
    for i in range(n-1):
        h[i+1][j] += h[i][j]

for i in range(q):
    x,y=map(int,input().split())
    x-=1
    y-=1
    print(h[n-1-x][y])

Submission status: Accepted

Solution code:
# ABC106D - AtCoder Express 2
def build_2dcum(A: "Array[Array[int]]") -> "Array[Array[int]]":
    from itertools import accumulate as acc

    return [list(acc(a)) for a in zip(*[acc(a) for a in A])]


def respond_2dcum(l: int, r: int, A: "Array[Array[int]]") -> int:
    return A[r][r] - A[l - 1][r] - A[r][l - 1] + A[l - 1][l - 1]


def main():
    # 2D cumulative sum (naive ver.)
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    imos = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        imos[l][r] += 1
    imos = build_2dcum(imos)
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        x = respond_2dcum(p, q, imos)
        ans.append(x)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC106D - AtCoder Express 2
from itertools import accumulate as acc


def main():
    # 2D cumulative sum
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    imos = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        imos[l][r] += 1
    imos = [list(acc(a[::-1]))[::-1] for a in zip(*[acc(a) for a in imos])]
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        ans.append(imos[q][p])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC106D - AtCoder Express 2
from itertools import accumulate as acc


def main():
    # 2D cumulative sum
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    imos = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        imos[l][r] += 1
    imos = [list(acc(a)) for a in zip(*[acc(a) for a in imos])]
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        cur = imos[q][q] - imos[p - 1][q] - imos[q][p - 1] + imos[p - 1][q - 1]
        ans.append(cur)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC106D - AtCoder Express 2
from itertools import accumulate as acc


def main():
    # 2D cumulative sum
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    rails = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        rails[l][r] += 1
    rails = [list(acc(a)) for a in rails]
    rails = [list(acc(a[::-1]))[::-1] for a in zip(*rails)]
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        ans.append(rails[q][p])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC106D - AtCoder Express 2
from itertools import accumulate as acc


def main():
    # 2D cumulative sum
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    rails = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        rails[l][r] += 1
    rails = tuple(tuple(acc(a)) for a in rails)
    rails = tuple(tuple(acc(a[::-1]))[::-1] for a in zip(*rails))
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        ans.append(rails[q][p])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# ABC106D - AtCoder Express 2
from itertools import accumulate as acc


def main():
    # 2D cumulative sum
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    rails = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        rails[l][r] += 1
    rails = [tuple(acc(a)) for a in rails]
    rails = [tuple(acc(a[::-1]))[::-1] for a in zip(*rails)]
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        ans.append(rails[q][p])
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

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

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

for p,q in PQ:
  print(Sumtable[q][q] - Sumtable[p-1][q] - Sumtable[q][p-1] + Sumtable[p-1][p-1])

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):
    l,r = map(int, input().split())
    a[l][r]+=1

b = [[0]*(n+1) for i in range(n+1)]

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

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

Submission status: Accepted

Solution code:
from bisect import bisect_left
import sys
input = sys.stdin.readline

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

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

for i in range(N + 1) :
    for j in range(N + 1) :
        if 0 <= i - 1 :
            dp[i][j] += dp[i-1][j]
        if 0 <= j - 1 :
            dp[i][j] += dp[i][j-1]
        if 0 <= i - 1 and 0 <= j - 1 :
            dp[i][j] -= dp[i-1][j-1]

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
Train = [list(map(int,input().split())) for i in range(M)]
Query = [list(map(int,input().split())) for i in range(Q)]

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

for train in Train:
  City[train[0]-1][train[1]-1] += 1

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

for query in Query:
  print(
    Accum[query[1]][query[1]]
  - Accum[query[1]][query[0]-1]
  - Accum[query[0]-1][query[1]]
  + Accum[query[0]-1][query[0]-1]
    )

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
def getlist():
	return list(map(int, input().split()))

#初期化
N, M, Q = getlist()
List = [[0] * (N + 1) for i in range(N + 1)]
for i in range(M):
	L, R = getlist()
	List[R][L] += 1

#累積和前処理
for i in range(N):
	for j in range(N + 1):
		List[i + 1][j] += List[i][j]
for i in range(N + 1):
	for j in range(N):
		List[i][j + 1] += List[i][j]

#クエリ処理
for i in range(Q):
	p, q = getlist()
	print(List[q][q] - List[q][p - 1])

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

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