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:
from array import array
from itertools import accumulate, repeat, starmap
from operator import add, itemgetter


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [array('L', repeat(0, city_count + 1))
                 for _ in range(city_count + 1)]

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

    for city_index in range(1, city_count + 1):
        city_list[city_index] = array('L', accumulate(city_list[city_index]))

    for city_index in range(2, city_count + 1):
        city_list[city_index] = array('L', starmap(
            add, zip(*(city_list[city_index + i] for i in (-1, 0)))))

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy

n,m,q=map(int,input().split())
M=[]
Q=[]
for i in range(m):
    M.append(list(map(int,input().split())))
for i in range(q):
    Q.append(list(map(int,input().split())))

#print(M)
#print(Q)

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

for i in range(m):
    A[M[i][0]][M[i][1]]+=1

#B=[[0 for i in range(n+1)] for j in range(n+1)] #Aの累積和のリスト

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

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

#print(A)
#print(B)

A = numpy.cumsum(A,axis=0)
A = numpy.cumsum(A,axis=1)
#A.cumsum(axis=0)
#A.cumsum(axis=1)
#C=A
#print(C)

for i in range(q):
    lem1=Q[i][0]-1
    ri=Q[i][1]
    print(A[ri][ri]-A[ri][lem1]-A[lem1][ri]+A[lem1][lem1])

Submission status: Accepted

Solution code:
import numpy

n,m,q=map(int,input().split())
M=[]
Q=[]
for i in range(m):
    M.append(list(map(int,input().split())))
for i in range(q):
    Q.append(list(map(int,input().split())))

#print(M)
#print(Q)

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

for i in range(m):
    A[M[i][0]][M[i][1]]+=1

B=[[0 for i in range(n+1)] for j in range(n+1)] #Aの累積和のリスト

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

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

#print(A)
#print(B)

B = numpy.cumsum(A,axis=0)
C = numpy.cumsum(B,axis=1)

#print(C)

for i in range(q):
    le=Q[i][0]
    ri=Q[i][1]
    print(C[ri][ri]-C[ri][le-1]-C[le-1][ri]+C[le-1][le-1])

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
 
a = [[0 for i in range(509)] for j in range(509)]
sum = [[0 for i in range(509)] for j in range(509)]
 
for i in range(M):
  p, q = map(int, input().split())
  a[p][q] += 1
 
for i in range(1,N+1):
  for j in range(i,N+1):
    sum[i][j] = sum[i][j-1] + a[i][j]
 
 
for i in range(Q):
  p, q = map(int, input().split())
  ans = 0
  for j in range(p,q+1):
    ans += sum[j][q] - sum[j][p-1]
  print(ans)

Submission status: Accepted

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

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

for i in range(q):
    p_i,q_i = map(int,input().split(" "))
    ans = LR_2dsum[p_i-1][p_i-1] - LR_2dsum[p_i-1][q_i] - LR_2dsum[q_i][p_i-1] + LR_2dsum[q_i][q_i]
    print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
N, M, Q = map(int, sys.stdin.readline().split())
 
LR = [[0 for _ in range(N-i)] for i in range(N)]
for i in range(M):
  L, R = map(int, sys.stdin.readline().split())
  LR[L-1][R-L] += 1
 
for i in range(N-2,-1,-1):
  acc = accumulate(LR[i])
  next(acc)
  for j in range(1, N-i):
    LR[i][j] = next(acc) + LR[i+1][j-1]
 
for i in range(Q):
  p, q = map(int, sys.stdin.readline().split())
  sys.stdout.write(str(LR[p-1][q-p])+"\n")

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
N, M, Q = map(int, sys.stdin.readline().split())
LR = [[0 for _ in range(N-i)] for i in range(N)]
for L, R in (map(int, sys.stdin.readline().split()) for _ in range(M)):
  LR[L-1][R-L] += 1
for i in range(N-2,-1,-1):
  acc = accumulate(LR[i])
  next(acc)
  for j in range(1, N-i):
    LR[i][j] = next(acc) + LR[i+1][j-1]
for p, q in (map(int, sys.stdin.readline().split()) for i in range(Q)):
  sys.stdout.write(str(LR[p-1][q-p])+"\n")

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
stdin = sys.stdin.readlines()
N, M, Q = map(int, stdin[0].split())
LR = [[0 for _ in range(N-i)] for i in range(N)]
for L,R in (map(int, line.split()) for line in stdin[1:M+1]):
  LR[L-1][R-L] += 1
for i in range(N-2,-1,-1):
  acc = accumulate(LR[i])
  next(acc)
  for j in range(1, N-i):
    LR[i][j] = next(acc) + LR[i+1][j-1]

sys.stdout.write("\n".join(map(str, 
  (LR[p-1][q-p] for p,q in (map(int, line.split()) for line in stdin[M+1:]))
)))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
stdin = sys.stdin.readlines()
N, M, Q = map(int, stdin[0].split())
LR = [[0 for _ in range(N-i)] for i in range(N)]
for line in stdin[1:M+1]:
  L, R = map(int, line.split())
  LR[L-1][R-L] += 1
for i in range(N-2,-1,-1):
  acc = accumulate(LR[i])
  next(acc)
  for j in range(1, N-i):
    LR[i][j] = next(acc) + LR[i+1][j-1]

sys.stdout.write("\n".join(map(str, 
  (LR[p-1][q-p] for p,q in (map(int, line.split()) for line in stdin[M+1:]))
)))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
N, M, Q = map(int, sys.stdin.readline().split())
 
LR = [[0 for _ in range(N-i)] for i in range(N)]
for i in range(M):
  L, R = map(int, sys.stdin.readline().split())
  LR[L-1][R-L] += 1
 
for i in range(N-2,-1,-1):
  acc = accumulate(LR[i])
  next(acc)
  for j in range(1, N-i):
    LR[i][j] = next(acc) + LR[i+1][j-1]
 
for i in range(Q):
  p, q = map(int, sys.stdin.readline().split())
  sys.stdout.write(str(LR[p-1][q-p])+"\n")

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
N, M, Q = map(int, sys.stdin.readline().split())

LR = [[0 for _ in range(N-i)] for i in range(N)]
for i in range(M):
  L, R = map(int, sys.stdin.readline().split())
  LR[L-1][R-L] += 1

for i in range(N-2,-1,-1):
  for j, (acc, pre) in enumerate(zip(accumulate(LR[i]), [0]+LR[i+1])):
    LR[i][j] = acc + pre

for i in range(Q):
  p, q = map(int, sys.stdin.readline().split())
  sys.stdout.write(str(LR[p-1][q-p])+"\n")

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
N, M, Q = map(int, sys.stdin.readline().split())
 
LR = [[0 for _ in range(N-i)] for i in range(N)]
for i in range(M):
  L, R = map(int, sys.stdin.readline().split())
  LR[L-1][R-L] += 1
 
for i in range(N-2,-1,-1):
  for j, acc in enumerate(accumulate(LR[i])):
    LR[i][j] = acc + LR[i+1][j-1]
  LR[i][0] -= LR[i+1][-1]
 
for i in range(Q):
  p, q = map(int, sys.stdin.readline().split())
  sys.stdout.write(str(LR[p-1][q-p])+"\n")

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
N, M, Q = map(int, sys.stdin.readline().split())
 
LR = [[0 for _ in range(N-i)] for i in range(N)]
for i in range(M):
  L, R = map(int, sys.stdin.readline().split())
  LR[L-1][R-L] += 1
 
for i in range(N-2,-1,-1):
  for j, acc in enumerate(accumulate(LR[i])):
    LR[i][j] = acc + (0 if j==0 else LR[i+1][j-1])
 
for i in range(Q):
  p, q = map(int, sys.stdin.readline().split())
  sys.stdout.write(str(LR[p-1][q-p])+"\n")

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
N, M, Q = map(int, sys.stdin.readline().split())
 
LR = [[0]* (N-i) for i in range(N)]
for i in range(M):
  L, R = map(int, sys.stdin.readline().split())
  LR[L-1][R-L] += 1
 
for i in range(N-2,-1,-1):
  for j, acc in enumerate(accumulate(LR[i])):
    LR[i][j] = acc + (0 if j==0 else LR[i+1][j-1])
 
for i in range(Q):
  p, q = map(int, sys.stdin.readline().split())
  sys.stdout.write(str(LR[p-1][q-p])+"\n")

Submission status: Accepted

Solution code:
import sys
N, M, Q = map(int, sys.stdin.readline().split())
 
LR = [[0 for _ in range(N+2-i)] for i in range(N+2)]
for i in range(M):
  L, R = map(int, sys.stdin.readline().split())
  LR[L][R-L+1] += 1
 
for i in range(2,N+2):
  for j in range(1,N-i+2):
    LR[j][i] += LR[j][i-1] + LR[j+1][i-1] - LR[j+1][i-2]
 
for i in range(Q):
  p, q = map(int, sys.stdin.readline().split())
  sys.stdout.write(str(LR[p][q-p+1]))
  sys.stdout.write("\n")

Submission status: Accepted

Solution code:
import sys
N, M, Q = map(int, sys.stdin.readline().split())
 
LR = [[0 for _ in range(N+2-i)] for i in range(N+2)]
for i in range(M):
  L, R = map(int, sys.stdin.readline().split())
  LR[L][R-L+1] += 1
 
for i in range(2,N+2):
  for j in range(1,N-i+2):
    LR[j][i] += LR[j][i-1] + LR[j+1][i-1] - LR[j+1][i-2]
 
for i in range(Q):
  p, q = map(int, sys.stdin.readline().split())
  sys.stdout.write(str(LR[p][q-p+1])+"\n")

Submission status: Accepted

Solution code:
import sys
N, M, Q = map(int, sys.stdin.readline().split())
 
LR = [[0 for _ in range(N+2-i)] for i in range(N+2)]
for i in range(M):
  L, R = map(int, sys.stdin.readline().split())
  LR[L][R-L+1] += 1
 
for i in range(2,N+2):
  for j in range(1,N-i+2):
    LR[j][i] += LR[j][i-1] + LR[j+1][i-1] - LR[j+1][i-2]
 
for i in range(Q):
  p, q = map(int, sys.stdin.readline().split())
  sys.stdout.write("{}\n".format(LR[p][q-p+1]))

Submission status: Accepted

Solution code:
# あらかじめ全ての区間における答えを求めておく
# 累積和が使える。
# 2次元累積和に関しては、下記のサイトを参照。
# https://paiza.hatenablog.com/entry/2014/05/28/もし女子大生プログラマに『アルゴリズム』を図
# p,qの値に関しての2次元座標系で考えると、値が存在するマスは限られてる
#
#
n, m, q = map(int, input().split())
ll = [[0, 0] for i in range(m)]
p = [[0, 0] for i in range(q)]
for i in range(m):
    ll[i][0], ll[i][1] = map(int, input().split())
for i in range(q):
    p[i][0], p[i][1] = map(int, input().split())
# for i in range(m):
#     print(ll[i])
# for i in range(q):
#     print(p[i])
sum = [[0 for i in range(n)] for i in range(n)]
# sum上でlをy成分＝行、rをx成分=列とする。
# 各区間の値を取り込み
for j in range(m):
    x = ll[j][0]-1
    y = ll[j][1]-1
    sum[y][x] += 1
# 2次元累積和の計算
# for j in range(n):
#     print(sum[j])
# print('-'*30)
for i in range(n):
    for j in range(1, n):
        sum[i][j] += sum[i][j-1]
for i in range(n):
    for j in range(1, n):
        sum[j][i] += sum[j-1][i]
# ans = [[0 for i in range(n)] for i in range(n)]
# for i in range(n):
#    for j in range(i, n):
#        for i2 in range(i, j+1):
#            for j2 in range(i, j+1):
#                ans[i][j] += sum[j2][i2]
# for j in range(n):
#     print(sum[j])


for i in range(q):
    x = p[i][0]-1
    y = p[i][1]-1
    if x != 0:
        print(sum[y][y] - sum[y][x-1] - sum[x-1][y]+sum[x-1][x-1])
    else:
        print(sum[y][y])

Submission status: Accepted

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

l = [[0 for i in range(N+1)] for j in range(N+2)]
for t in [input().split() for _ in range(M)]:
    i = int(t[0])
    j = int(t[1])
    l[i][j] += 1

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

for k in [input().split() for _ in range(Q)]:
    p = int(k[0])
    q = int(k[1])
    print(l[p][q])

Submission status: Accepted

Solution code:
import sys
N, M, Q = map(int, sys.stdin.readline().split())

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

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

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

Submission status: Accepted

Solution code:
import sys
sin = sys.stdin.readlines()
N, M, Q = map(int, sin[0].split())

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

for i in range(2,N+2):
  for j in range(1,N-i+2):
    LR[j][i] += LR[j][i-1] + LR[j+1][i-1] - LR[j+1][i-2]
 
for line in sin[M+1:]:
  p, q = map(int, line.split())
  print(LR[p][q-p+1])

Submission status: Accepted

Solution code:
import sys
sin = sys.stdin.readlines()
N, M, Q = map(int, sin[0].split())

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

for i in range(2,N+2):
  for j in range(1,N-i+2):
    LR[j][i] += LR[j][i-1] + LR[j+1][i-1] - LR[j+1][i-2]
 
A = []
for line in sin[M+1:]:
  p, q = map(int, line.split())
  A.append(LR[p][q-p+1])

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

Submission status: Accepted

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

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

  
for i in range(2,N+2):
  for j in range(1,N-i+2):
    LR[j][i] += LR[j][i-1] + LR[j+1][i-1] - LR[j+1][i-2]
 
A = []
for i in range(Q):
  p, q = map(int, input().split())
  A.append(LR[p][q-p+1])

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
T = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
  L,R = map(int, input().split())
  T[L][R] += 1
for l in range(1,N+1):
  for r in range(1,N+1):
    T[l][r] += T[l-1][r]+T[l][r-1]-T[l-1][r-1]
ans = []
for i in range(Q):
  p,q = map(int, input().split())
  ans.append(T[p-1][p-1]+T[q][q]-T[p-1][q]-T[q][p-1])
print('\n'.join(map(str,ans)))

Submission status: Accepted

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

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

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

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


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


P=[ map( int , raw_input().split() ) for i in range(Q) ] 

for x,y in P:
	if x-1>0:
		print S[y][y]-S[x-1][y]-S[y][x-1]+S[x-1][x-1]
	else:
		print S[y][y]

Submission status: Accepted

Solution code:
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())
    a[l][r] += 1
for i in range(1, N+1):
    for j in range(1, N+1):
        a[i][j] += a[i][j-1]
for i in range(1, N+1):
    for j in range(1, N+1):
        a[i][j] += a[i-1][j]

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

Submission status: Accepted

Solution code:
n,m,q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
p = [list(map(int, input().split()))+ [i] for i in range(q)]
class BIT:
    def __init__(self, node_size):
        self._node = node_size+1
        self.bit = [0]*self._node

    def add(self, index, add_val):
        while index < self._node:
            self.bit[index] += add_val
            index += index & -index

    def sum(self, index):
        res = 0
        while index > 0:
            res += self.bit[index]
            index -= index & -index
        return res
l.extend(p)
l = sorted(l,key= lambda x:x[1])
ka = BIT(n)
ans = []
for i in l:
  if len(i) == 2:
    ka.add(i[0], 1)
  else:
    ans.append([i[2],ka.sum(i[1]) - ka.sum(i[0]-1)])
ans = sorted(ans)
for i in range(len(ans)):
  print(ans[i][1])

Submission status: Accepted

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

for _ in range(qq):
    p, q = map(int, input().split())
    if q == n:
        print(lr[p - 1][q - 1])
    else:
        print(lr[p - 1][q - 1] - lr[q][q - 1])

Submission status: Accepted

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

train = []
for i in range(0, N):
	train.append([])
for i in range(0, M):
	L, R = map(int, raw_input().split())
	train[L-1].append(R)
for i in range(0, N):
	train[i-1].sort()

counter = []
for i in range(0, N):
	lst = []
	for j in range(0, N):
		lst.append(0)
	for j in range(0, len(train[i])):
		lst[train[i][j]-1] = lst[train[i][j]-1] + 1
	for j in range(1, len(lst)):
		lst[j] = lst[j-1] + lst[j]
	counter.append(lst)
for i in range(1, N):
	for j in range(0, N):
		counter[N-1-i][j] = counter[N-1-i][j] + counter[N-i][j]

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

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
X = []
for m in range(M):
    li, ri = map(int, input().split())
    li, ri = li-1, ri-1
    X.append([li, ri])


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

        self.calc()

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for x in range(self.H):
            for y in range(1, self.W):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]

        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]

        elif j1 <= 0 < i1:
            self.G[i2][j2] - self.G[i1 - 1][j2]

        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(N, N)
R2D.load(X)
for i in range(Q):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    print(R2D.get(p, p, q, q))

Submission status: Accepted

Solution code:
n, m, q = list(map(int, input().split()))
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

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

cumsum = [[0]*(n+1) for _ in range(n+1)]
for y in range(1, n+1):
    for x in range(1, n+1):
        cumsum[y][x] = country[y][x]+cumsum[y][x-1]
for y in range(1, n+1):
    for x in range(1, n+1):
        cumsum[y][x] += cumsum[y-1][x]
# for cy in cumsum: print(cy)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
# -*- coding:utf-8 -*-
n, m, q = map(int, input().split())
sm = [[0 for x in range(n + 5)] for y in range(n + 5)]

for i, j in (map(int, input().split()) for _ in range(m)):
    sm[i][j] += 1

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

Submission status: Accepted

Solution code:
import numpy as np
n, m, q = input().split()
n, m, q = int(n), int(m), int(q)
s = np.zeros((501, 501))
 
for _ in range(m):
    l, r = input().split()
    l, r = int(l), int(r)
    s[l, r] += 1
    
"""
     1 2 3
    --------
1 | 1 2 3
2 | 1 0 1
"""
    
for i in range(1, n+1):
    for j in range(1, n+1):
        s[i, j] += s[i, j-1]
        
"""
     1 2 3
    --------
1 | 1 3 6
2 | 1 1 2
"""
        
for j in range(1, n+1):
    for i in range(1, n+1):
        s[i, j] += s[i-1, j]
        
"""
     1 2 3
    --------
1 | 1 3 6
2 | 2 4 8
"""
 
for _ in range(q):
    l, r = input().split()
    l, r = int(l), int(r)
    print(int(s[r, r] - s[r, l-1] - s[l-1, r] + s[l-1, l-1]))

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
#line = [list(map(int, input().split())) for _ in range(m)]
ans = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
	l, r = map(int, input().split())
	l -= 1
	r -= 1
	ans[0][r] += 1
	ans[l + 1][n] += 1
	ans[0][n] -= 1
	ans[l + 1][r] -= 1

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import numpy as np
N, M, Q = map(int, input().split())

train = np.zeros((N, N))
for i in range(M):
	L, R = map(int, input().split())
	train[N-L][R-1] += 1
train = np.cumsum(np.cumsum(train, axis=0), axis=1)

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

Submission status: Accepted

Solution code:
import numpy as np
n, m, q = input().split()
n, m, q = int(n), int(m), int(q)
s = np.zeros((501, 501))

for _ in range(m):
    l, r = input().split()
    l, r = int(l), int(r)
    s[l, r] += 1
    
"""
     1 2 3
    --------
1 | 1 2 3
2 | 1 0 1
"""
    
for i in range(1, n+1):
    for j in range(1, n+1):
        s[i, j] += s[i, j-1]
        
"""
     1 2 3
    --------
1 | 1 3 6
2 | 1 1 2
"""
        
for j in range(1, n+1):
    for i in range(1, n+1):
        s[i, j] += s[i-1, j]
        
"""
     1 2 3
    --------
1 | 1 3 6
2 | 2 4 8
"""

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

Submission status: Accepted

Solution code:
from numpy import *
I=lambda:map(int,input().split())
F=lambda x:flipud(a.cumsum(x))
n,m,q=I()
a=zeros((n+2,n+2))
for i in [0]*m:
  s,e=I()
  a[s,e]+=1
a=F(1)
a=F(0)
for i in [0]*q:
  s,e=I()
  print(int(a[s,e]))

Submission status: Accepted

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
X = np.zeros((N, N), dtype=int)
ends = np.zeros((M, 2), dtype=int)
queries = np.zeros((Q, 2), dtype=int)
for i in range(M):
    ends[i] = [int(item) for item in input().split()]
for i in range(Q):
    queries[i] = [int(item) for item in input().split()]
np.add.at(X, [ends[:,0] - 1, ends[:, 1] - 1], 1)
B = np.cumsum(X[::-1,:], axis = 0)[::-1,:]
C = np.cumsum(B, axis = 1)
for item in queries:
    print(C[item[0] - 1, item[1] - 1])

Submission status: Accepted

Solution code:
import numpy as np
I=lambda:map(int,input().split())
n,m,q=I()
a=np.zeros((n+2,n+2))
for i in range(m):
  s,e=I()
  a[s,e]+=1
b=np.flipud(a.cumsum(1))
b=np.flipud(b.cumsum(0))
for i in range(q):
  s,e=I()
  print(int(b[s,e]))

Submission status: Accepted

Solution code:
import numpy as np
n,m,q=map(int,input().split())
a=np.zeros((n+2,n+2))
for i in range(m):
  s,e=map(int,input().split())
  a[s,e]+=1

b=a.cumsum(1)
b=np.flipud(b)
b=b.cumsum(0)
b=np.flipud(b)

for i in range(q):
  s,e=map(int,input().split())
  print(int(b[s,e]))

Submission status: Accepted

Solution code:
def dpdo(left, right):
    if dp[left][right]!=-1:
        return dp[left][right]
    elif left==right:
        dp[left][right] = grid[left][right]
        return dp[left][right]
    elif right-left==1:
        dp[left][right] = dpdo(left,right-1) + dpdo(left+1, right) + grid[left][right]
        return dp[left][right]
    else:
        dp[left][right] = dpdo(left,right-1) + dpdo(left+1, right) + grid[left][right] - dpdo(left+1,right-1)
        return dp[left][right]

dp = []
grid = []
temp1 = []
temp2 = []
for i in range(0,501):
    temp1 = []
    temp2 = []
    for j in range(0,501):
        temp1.append(0)
        temp2.append(-1)
    dp.append(temp2)
    grid.append(temp1)
    
n, m, q = map(int,input().split())
for i in range(1,m+1):
    left, right = map(int, input().split())
    grid[left][right] += 1
    
dpdo(1,n)

for i in range(1,q+1):
    left, right = map(int, input().split())
    print(dp[left][right])

Submission status: Accepted

Solution code:
# input
N, M, Q = map(int, input().split())
train_query = {} # 対象区間とクエリを一緒にソート
for i in range(M + Q):
    train_query[i] = list(map(int, input().split()))

train_query = sorted(train_query.items(), key=lambda x: x[1][1])
# 辞書をソートするとリストが返ってくることに注意

StartPoints = [0 for _ in range(N)] # 対象区間の開始位置
ans = [0 for _ in range(Q)] # 各クエリに対する答え

for j in range(M + Q):
    if train_query[j][0] < M: # 対象区間
        StartPoints[train_query[j][1][0] - 1] += 1
    else: # クエリ
        ans[train_query[j][0] - M] = sum(StartPoints[(train_query[j][1][0] - 1):(train_query[j][1][1])])

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

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

# 列車情報
# T[l] 都市l発の列車の目的都市
T = [[] for l in range(N + 1)]
for i in range(M):
    l, r = map(int, input().split())
    T[l].append(r)

# nt[l][q] 都市l発で都市q以前に止まる列車数
nt = [[0] * (N + 2) for l in range(N + 1)]
for i in range(1, N + 1):
    T[i].append(N + 1)  # 番兵
    T[i].sort()
    prev = 0
    for r in T[i]:
        if r != prev:
            for j in range(prev + 1, r + 1):
                nt[i][j] = nt[i][prev]
            prev = r
        nt[i][r] += 1

# nt[p][q] 都市p以降発で都市q以前に止まる列車数
for i in range(N - 1, 0, -1):
    for j in range(1, N + 1):
        nt[i][j] += nt[i + 1][j]

# 問い合わせ
for i in range(Q):
    p, q = map(int, input().split())
    print(nt[p][q])

Submission status: Accepted

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
LR = []
for i in range(M):
    l, r = map(int, input().split())
    LR.append([l, r])
PQ = []
for i in range(Q):
    p, q = map(int, input().split())
    PQ.append([p, q])
ar_sec = np.zeros([N, N])
for i in range(M):
    l, r = LR[i][0], LR[i][1]
    ar_sec[l-1][r-1] += 1


ar_sum = np.zeros([N+1, N+1])
for i in range(N):
    for j in range(N):
        ar_sum[i+1][j+1] = ar_sum[i][j+1]+ar_sum[i+1][j]-ar_sum[i][j]+ar_sec[i][j]

for i in range(Q):
    p, q = PQ[i][0], PQ[i][1]
    print(int(ar_sum[q][q]-ar_sum[p-1][q]))