Problem:


Score: 400 points

Problem Statement

In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east.
A company called AtCoder Express possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i).
Takahashi the king is interested in the following Q matters:

The number of the trains that runs strictly within the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.

Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Constraints

N is an integer between 1 and 500 (inclusive).

M is an integer between 1 and 200 \ 000 (inclusive).

Q is an integer between 1 and 100 \ 000 (inclusive).

1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)

1 \leq p_i \leq q_i \leq N (1 \leq i \leq Q)

Input

Input is given from Standard Input in the following format:

N M Q
L_1 R_1
L_2 R_2
:
L_M R_M
p_1 q_1
p_2 q_2
:
p_Q q_Q

Output

Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City p_i to City q_i.

Sample Input 1

2 3 1
1 1
1 2
2 2
1 2

Sample Output 1

3

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.

Sample Input 2

10 3 2
1 5
2 8
7 10
1 7
3 10

Sample Output 2

1
1

The first query is on the section from City 1 to 7. There is only one train that runs strictly within that section: Train 1.
The second query is on the section from City 3 to 10. There is only one train that runs strictly within that section: Train 3.

Sample Input 3

10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10

Sample Output 3

7
9
10
6
8
9
6
7
8
10



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


Sample output:
3

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

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

csum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        csum[i + 1][j + 1] = csum[i + 1][j] + csum[i][j + 1] - csum[i][j] + G[i][j]

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

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

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

csum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        csum[i + 1][j + 1] = csum[i + 1][j] + csum[i][j + 1] - csum[i][j] + G[i][j]

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

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

def input():
    return sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

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

csum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        csum[i + 1][j + 1] = csum[i + 1][j] + csum[i][j + 1] - csum[i][j] + G[i][j]

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

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

input = lambda: sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60

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

csum = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        csum[i + 1][j + 1] = csum[i + 1][j] + csum[i][j + 1] - csum[i][j] + G[i][j]

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

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

Submission status: Accepted

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

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

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

# for i in LR:
#     print(i)

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

# print(LRsum)

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

# print(L)
# print(LL)

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
n, m, q = map(int, input().split())
cnt = [[0]*(n+1)for _ in range(n+1)]
for _ in range(m):
    L, R = map(int, input().split())
    cnt[L][R] += 1

S = np.cumsum(cnt, axis=0).cumsum(axis=1)
L, R = map(np.array, zip(*[map(int, input().split()) for _ in range(q)]))

ans = S[R, R]-S[R, L-1]-S[L-1, R]+S[L-1, L-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())
cnt = np.zeros((n+1, n+1), dtype=np.int32)
L, R = map(np.array, zip(*[map(int, input().split()) for _ in range(m)]))
np.add.at(cnt, (L, R), 1)

S = np.cumsum(cnt, axis=0).cumsum(axis=1)
L, R = map(np.array, zip(*[map(int, input().split()) for _ in range(q)]))

ans = S[R, R]-S[R, L-1]-S[L-1, R]+S[L-1, L-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())
cnt = [[0]*(n+1)for _ in range(n+1)]
for _ in range(m):
    L, R = map(int, input().split())
    cnt[L][R] += 1

S = np.cumsum(cnt, axis=0).cumsum(axis=1)

L, R = map(np.array, zip(
    *[tuple(map(int, input().split())) for _ in range(q)]))


ans = S[R, R]-S[R, L-1]-S[L-1, R]+S[L-1, L-1]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import numpy as np
n, m, q = map(int, input().split())
cnt = [[0]*(n+1)for _ in range(n+1)]
for _ in range(m):
    L, R = map(int, input().split())
    cnt[L][R] += 1

S = np.cumsum(cnt, axis=0).cumsum(axis=1)

L, R = map(np.array, zip(
    *[tuple(map(int, input().split())) for _ in range(q)]))


ans = S[R, R]-S[R, L-1]-S[L-1, R]+S[L-1, L-1]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import numpy as np
n, m, q = map(int, input().split())
cnt = [[0]*(n+1)for _ in range(n+1)]
for _ in range(m):
    L, R = map(int, input().split())
    cnt[L][R] += 1

S = np.cumsum(cnt, axis=0).cumsum(axis=1).tolist()

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

Submission status: Accepted

Solution code:
import numpy as np
n, m, q = map(int, input().split())
cnt = [[0]*(n+1)for _ in range(n+1)]
for _ in range(m):
    L, R = map(int, input().split())
    cnt[L][R] += 1

S = np.cumsum(cnt, axis=0).cumsum(axis=1)

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

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

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


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

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
edges = [[0]*n for _ in range(n)]

for _ in range(m):
    L, R = map(lambda x: int(x)-1, input().split())
    edges[L][R] += 1


S = [[0]*(n+1)for _ in range(n+1)]
for i in range(n):
    for j in range(n):
        S[i][j+1] = S[i][j] + edges[i][j]

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n, m, q = Is()
LR = TIR(m)
PQ = TIR(q)

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

Acc = deepcopy(X)
for i in range(n+1):
    for j in range(n):
        Acc[i][j+1] += Acc[i][j]
for i in range(n):
    for j in range(n+1):
        Acc[i+1][j] += Acc[i][j]

# X[p][p] + X[p][p+1] + ... + X[p][q] + X[p+1][p] + ... + X[q][q]
# -> Acc[q][q] - Acc[q][p-1] - Acc[p-1][q] + Acc[p-1][p-1]

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# N**2の解法
N, M, Qu = lr()
graph = [[0] * (N+1) for _ in range(N+1)]  # 1-indexed
for i in range(M):
    l, r = lr()
    graph[l][r] += 1

graph = np.array(graph)
np.cumsum(graph, axis=1, out=graph)
np.cumsum(graph, axis=0, out=graph)
P = []; Q = []
for _ in range(Qu):
    p, q = lr()
    P.append(p); Q.append(q)

P = np.array(P); Q = np.array(Q)
answer = graph[Q, Q] - graph[Q, P-1] - graph[P-1, Q] + graph[P-1, P-1]
print('\n'.join(answer.astype(str)))

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# N**2の解法
N, M, Q = lr()
graph = np.array([[0] * (N+1) for _ in range(N+1)])  # 1-indexed
for i in range(M):
    l, r = lr()
    graph[l][r] += 1

for i in range(N+1):
    graph[i] = graph[i].cumsum()

graph = np.cumsum(graph, axis=0)
for _ in range(Q):
    p, q = lr()
    answer = graph[q][q] - graph[q][p-1] - graph[p-1][q] + graph[p-1][p-1]
    print(answer)

# 30

Submission status: Accepted

Solution code:




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


"""
pを含むpの右で出発して、qを含むqの左で停止する列車の本数を求める

愚直解だと、各クエリに対し各列車が当てはまるか見ていけばよい。が、計算量がO(M*Q)とかになるはずなので、到底間に合わない。
N,Mが10**5オーダーなので、各クエリに対し、O(1)とか、１でなくてももうちょっと少ないオーダーでで解答できると間に合う感じ。

各クエリに対し、毎回「列車１はここからここまでを走ってて～」を重複計算するのが無駄。
重複計算は前処理で解消するのが典型的な方法のはず。
区間に対して数え上げをする場合は累積和がよく使われる気がする。今回は二次元累積和。

"""

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

# 累積和にする
for l in range(N):
    for r in range(l+1,N):
        trains[l][r] = trains[l][r-1] + trains[l][r]


for p,q in PQ:
    ans = 0
    for l in range(p-1, q):
        ans += trains[l][q-1]
    print(ans)

Submission status: Accepted

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

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

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

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

result = []
for _ in range(Q):
    p, q = map(int, input().split())
    result.append(t[q][q] + t[p - 1][p - 1] - t[p - 1][q] - t[q][p - 1])
print('\n'.join(str(v) for v in result))

Submission status: Accepted

Solution code:
n,m,qu = map(int,input().split())
lr = [[0]*(n+1) for _ in range(n+1)]

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

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

Submission status: Accepted

Solution code:
def main():
    N, M, Q = list(map(int, input().split(' ')))
    x = [[0 for _ in range(N)] for _ in range(N)]
    for _ in range(M):
        left, right = list(map(int, input().split(' ')))
        x[left - 1][right - 1] += 1
    for i in range(N):
        for j in range(1, N):
            x[i][j] += x[i][j - 1]
    for j in range(N):
        for i in range(N - 2, -1, -1):
            x[i][j] += x[i + 1][j]
    queries = [list(map(int, input().split(' '))) for _ in range(Q)]
    for q in queries:
        print(x[q[0] - 1][q[1] - 1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import numpy as np
import sys

input=sys.stdin.readline

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

lrs = [list(map(int, input().split())) for _ in range(m)]
pqs = [list(map(int, input().split())) for _ in range(q)]

train_array = np.zeros((n+1,n+1),dtype=int)

for lr in lrs:
    train_array[lr[0]][lr[1]] +=1


#print(train_array)

train_array_ruisekiwa = np.zeros((n+1,n+1), dtype = int)

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

#print(train_array_ruisekiwa)

for pq in pqs:
    print(train_array_ruisekiwa[pq[1]][pq[1]] - train_array_ruisekiwa[pq[1]][pq[0]-1] - train_array_ruisekiwa[pq[0]-1][pq[1]] + train_array_ruisekiwa[pq[0]-1][pq[0]-1])

Submission status: Accepted

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

def main():
    N, M, Q = map(int, readline().rstrip().split())
    train_cnt = [[0] * N for _ in range(N)]
    for _ in range(M):
        l, r = map(int, readline().rstrip().split())
        train_cnt[l-1][r-1] += 1
    
    for i in range(N):
        for j in range(1, N):
            train_cnt[i][j] += train_cnt[i][j-1]
    
    for j in range(N):
        for i in range(N-2, -1, -1):
            train_cnt[i][j] += train_cnt[i+1][j]
    
    for _ in range(Q):
        p, q = map(int, readline().rstrip().split())
        print(train_cnt[p-1][q-1])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
lr = []
for i in range(m):
    l, r = map(int, input().split())
    lr.append((l, r))

mtx = [[0 for i in range(n)] for j in range(n)]

for item in lr:
    mtx[item[0]-1][item[1]-1] += 1

rui = [[0 for i in range(n+1)] for j 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] + mtx[i][j]

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

Submission status: Accepted

Solution code:
inf = 10 ** 15
mod = 10 ** 9 + 7

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

maps = [[0 for j in range(n)]for i in range(n)]
for i in range(m):
    l,r = map(int, input().split())
    l-=1
    r-=1
    maps[l][r]+=1
c = []
for i in range(n):
    a = [0]
    for j in maps[i]: a.append(a[-1]+j)
    c.append(a)
for i in range(q):
    l,r  = map(int, input().split())
    ans = 0
    for i in range(l-1,r):
        ans += (c[i][r]-c[i][l-1])
    print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

# https://atcoder.jp/contests/abc106
# -12:47 done


def main():
    N, M, Q = map(int, input().split())
    L = [None] * M
    R = [None] * M
    p = [None] * Q
    q = [None] * Q

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

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

    dp = [[0]*N for _ in range(N)]
    for i in range(M):
        dp[L[i]][R[i]] += 1

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

    for i in range(Q):
        print(dp[p[i]][q[i]])


main()

Submission status: Accepted

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

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

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 _ in range(Q):
    p, q = map(int, input().split())

    print(s[q][q] - s[q][p-1] -s[p-1][q] + s[p-1][p-1])

Submission status: Accepted

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


#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

#006
import numpy as np

def main():
	n,m,q=MI()
	li=np.zeros((n+1,n+1),dtype=np.int64)
	for _ in range(m):
		l,r=MI()
		li[l][r]+=1
	#print(li)

	li=np.cumsum(li,axis=0)
	li=np.cumsum(li,axis=1)
	#print(li)

	for _ in range(q):
		p,q=MI()
		print(li[q,q]-li[p-1,q]-li[q,p-1]+li[p-1,p-1])

if __name__ == "__main__":
	main()

Submission status: Accepted

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

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

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

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

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

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

DP=[[0 for _ in range(n+1)] for _ in range(n+1)]
for l,r in LR:
    DP[l][r] +=1

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

for i in range(1,n+1):
    for j in range(1,n+1):
        DP[i][j]=DP[i][j-1]+DP[i][j]
        
for p,q in PQ:
    print(DP[q][q]-DP[q][p-1]-DP[p-1][q]+DP[p-1][p-1])

Submission status: Accepted

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

for i in range(q):
    p,q=MI()
    p-=1
    print(t[q][q]-t[q][p]-t[p][q]+t[p][p])

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

Submission status: Accepted

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

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

#print(L)

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, Q = map(int, input().split())
    lines = np.zeros((N + 1, N + 1)).astype(np.int32)

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

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

    for _ in range(Q):
        p, q = map(int, input().split())
        # 終点がq以下のものの総数から，始点がp-1以下で終点がq以下のものをひく
        print(lines[-1][q] - lines[p - 1][q])


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
n, m, q = [int(x) for x in input().split()]

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

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

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

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

Submission status: Accepted

Solution code:
import sys
import numpy as np

input=sys.stdin.readline

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

x=np.zeros((N+1,N+1),dtype=np.int32)
for _ in range(M):
    l,r=map(int,input().split())
    x[l,r]+=1

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

Submission status: Accepted

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


def solve_iter(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    f = [[0] * N for _ in range(N)]
    for l, r in zip(L, R):
        f[l-1][r-1] += 1
    dp = [[0] * (N + 1) for _ in range(N+1)]
    for h in range(N):
        for w in range(N):
            dp[h+1][w+1] = dp[h+1][w] + dp[h][w+1] - dp[h][w] + f[h][w]

    #print(*f, sep='\n')
    #print(*dp, sep='\n')
    for pp, qq in zip(p, q):
        #yield pp, qq, dp[qq][qq] - dp[qq][pp-1] - dp[pp-1][qq] + dp[pp-1][pp-1]
        yield dp[qq][qq] - dp[qq][pp-1] - dp[pp-1][qq] + dp[pp-1][pp-1]

def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    return list(solve_iter(N, M, Q, L, R, p, q))

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools
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))
    print(*solve(N, M, Q, L, R, p, q), sep='\n')

def test():
    import doctest
    doctest.testmod()

if __name__ == '__main__':
    #test()
    main()

Submission status: Accepted

Solution code:
import sys
import numpy as np
from itertools import accumulate

input = sys.stdin.readline

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

lines = np.zeros((501, 501), np.int32)

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

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


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

Submission status: Accepted

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m, q = mi()
    train = [lmi() for _ in range(m)]
    query = [lmi() for _ in range(q)]

    """
    電車の運行区間のうち開始地点を x 座標で、終着地点を y 座標で表し二次元座標で管理する
    [i, j] 区間内で運行する電車は 0 <= x <= i, 0 <= y <= j の長方形区間内の全ての電車である
    """
    coordinate = [[0] * (n + 1) for _ in range(n + 1)]
    for start, end in train:
        coordinate[start][end] += 1
    # for line in coordinate:
    #     print(*line)
    # print("")
    
    # 二次元累積和に
    for i in range(n):
        for j in range(n):
            coordinate[i+1][j+1] += coordinate[i][j+1] + coordinate[i+1][j] - coordinate[i][j]
    # for line in coordinate:
    #     print(*line)
    # print("")

    # 各クエリに O(1) で答えられる！
    for l, r in query:
        print(coordinate[r][r] - coordinate[l-1][r] - coordinate[r][l-1] + coordinate[l-1][l-1])


if __name__ == "__main__":
    main()

Submission status: Accepted

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

class Cumulative_Sum_2D:
    def __init__(self, a):
        lai = len(a)
        laj = len(a[0])
        self.s = [[0] * (laj + 1) for _ in range(lai + 1)]
        for i in range(lai):
            for j in range(laj):
                self.s[i+1][j+1] = self.s[i+1][j] + a[i][j]
        for i in range(lai):
            for j in range(laj):
                self.s[i+1][j+1] += self.s[i][j+1]
    def sum(self, li, lj, ri, rj):
        s = self.s
        return s[ri][rj] - s[li][rj] - s[ri][lj] + s[li][lj]

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

cs = Cumulative_Sum_2D(a)

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