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 functools import lru_cache

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

# trains[L][r]: L から r まで行く電車の本数 (1 <= L <= r <= N)
trains = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for m in range(M):
    L, r = map(int, input().split())
    trains[L][r] += 1

# スタック深くなるので DP 化
# @lru_cache(maxsize=None)
# def solve(L, r):
#     if L > r:
#         raise ValueError()
#     if L == r:
#         return trains[L][r]
#     if L + 1 == r:
#         return trains[L][L] + trains[r][r] + trains[L][r]
#     return trains[L][r] + solve(L + 1, r) + solve(L, r - 1) - solve(L + 1, r - 1)


# dp[L][r]: L から r に含まれる本数
dp = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for length in range(N + 1):
    L = 1
    r = L + length
    while r <= N:
        if length == 0:
            dp[L][r] = trains[L][r]
        elif length == 1:
            dp[L][r] = dp[L][L] + dp[r][r] + trains[L][r]
        else:
            dp[L][r] = dp[L + 1][r] + dp[L][r - 1] - dp[L + 1][r - 1] + trains[L][r]
        L += 1
        r += 1


def solve(L, r):
    return dp[L][r]


for q in range(Q):
    print(solve(*map(int, input().split())))

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

import numpy as np
from itertools import combinations

trains = [[0]*N for _ in range(N)]

for l, r in LR:
  trains[l-1][r-1] +=1
  
trains = np.array(trains)

# 二次元累積和
row_sum = trains.cumsum(axis=1)
matrix_sum = row_sum.cumsum(axis=0)

answer = {}

for p,q in PQ:
  if (p,q) not in answer:
    if p==1:
      answer[(p,q)] = matrix_sum[q-1, q-1]
    else:
      answer[(p,q)] = matrix_sum[q-1,q-1] - matrix_sum[p-2,q-1]
  print(answer[(p,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)]

import numpy as np

trains = np.array([[0]*N for _ in range(N)])

for l, r in LR:
  trains[l-1][r-1] +=1

# 二次元累積和
row_sum = trains.cumsum(axis=1)
matrix_sum = row_sum.cumsum(axis=0)

for p,q in PQ:
  if p==1:
    print(matrix_sum[q-1, q-1])
  else:
    print(matrix_sum[q-1,q-1] - matrix_sum[p-2,q-1])

Submission status: Accepted

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


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    mem = [[0] * N for i in range(N)]
    mem2 = [[0] * N for i in range(N)]
    for i in range(M):
        mem[L[i] - 1][R[i] - 1] += 1
    for h in range(N):
        for w in range(N):
            sum = mem[h][w]
            if h == 0 and w > 0:
                sum += mem2[h][w-1]
            elif w == 0 and h > 0:
                sum += mem2[h-1][w]
            elif h > 0 and w > 0:
                sum += mem2[h][w-1] + mem2[h-1][w] - mem2[h-1][w-1]
            mem2[h][w] = sum
    for i in range(Q):
        pc = p[i]-1
        qc = q[i]-1
        low = mem2[pc-1][qc] + mem2[qc][pc-1] - \
            mem2[pc-1][pc-1] if pc > 0 else 0
        sum = mem2[qc][qc] - low
        print(sum)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
def main():
	N, M, Q = map(int, input().split())
	LR = [[0 for _ in range(N+1)] for _ in range(N+1)]
	ans = [0]*Q
	for _ in range(M):
		l, r = map(int, input().split())
		LR[l][r] += 1
	for i in range(1, N+1):
		for j in range(1, N+1):
			LR[i][j] += LR[i][j-1]
	for i in range(1, N+1):
		for j in range(1, N+1):
			LR[i][j] += LR[i-1][j]

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

for i in range(m):
    l, r = (int(i) for i in input().split())
    city[l][r] += 1
for i in range(1, n+1):
    for j in range(1, n+1):
        city[i][j] += city[i][j-1]
for i in range(1, n+1):
    for j in range(1, n+1):
        city[i][j] += city[i-1][j]


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

Submission status: Accepted

Solution code:
import itertools

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

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

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

for i in range(1, N):
    route[i] = list(itertools.accumulate(route[i]))

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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=[list(accumulate(a[i])) for i in range(N+1)]
k=[[b[j][i] for j in range(i+1) ] for i in range(N+1)]

ans=[list(accumulate(reversed(k[i])))[::-1] for i in range(N+1)]


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

Submission status: Accepted

Solution code:
import sys

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(i,N+1):
        b[i][j]=a[i][j]+b[i][j-1]

ans=[[0]*(N+2) for i in range(N+2)]
for q in range(1,N+1):
    for p in range(q,0,-1):
        ans[p][q]=ans[p+1][q]+b[p][q]

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

Submission status: Accepted

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

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

for i in range(M):
    l, r = map(int, input().split())

    count[l][r] += 1

# 2次元累積和
for i in range(1, 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(1, N+1):
        count[i][j] += count[i-1][j]


for i in range(Q):
    l, r = map(int, input().split())
    print(count[r][r]+count[l-1][l-1]-count[l-1][r]-count[r][l-1])

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    a = [[0]*(N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        a[l][r] += 1

    a = [list(itertools.accumulate(x)) for x in a]
    a = [list(itertools.accumulate(s[::-1]))[::-1] for s in zip(*a)]

    for pp, qq in zip(p, q):
        # 転置略して逆指定
        print(a[qq][pp])
    # print(*a, sep="\n")

    return


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:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


class Bit:
    def __init__(self, n, m):
        self.size = [n, m]
        self.tree = [[0] * (n + 1) for _ in range(m+1)]

    def sum(self, i, j):
        s = 0
        while i > 0:
            jj = j
            while jj > 0:
                s += self.tree[i][jj]
                jj -= jj & -jj
            i -= i & -i
        return s

    def add(self, i, j, x):
        while i <= self.size[0]:
            jj = j
            while jj <= self.size[1]:
                self.tree[i][jj] += x
                jj += jj & -jj
            i += i & -i


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    b = Bit(N, N)

    for l, r in zip(L, R):
        b.add(N-l+1, r, 1)

    for pp, qq in zip(p, q):
        print(b.sum(N-pp+1, qq))

    return


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

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

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

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

for (l, r) in data:
    ans[l-1][r-1] += 1
for sub in ans:
    for i in range(n-1):
        sub[i+1] += sub[i]
for i in range(n-2, -1, -1):
    for j in range(n):
        ans[i][j] += ans[i+1][j]
for (l, r) in questions:
    print(ans[l-1][r-1])

Submission status: Accepted

Solution code:
import numpy as np
N,M,Q = map(int,input().split())
c = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    l,r = map(int,input().split())
    c[l][r] += 1
c = np.cumsum(np.cumsum(c,axis=0),axis=1)
for i in range(Q):
    p,q = map(int,input().split())
    print(c[q][q]-c[q][p-1]-c[p-1][q]+c[p-1][p-1])

Submission status: Accepted

Solution code:

def main():
    N, M, Q = [int(n) for n in input().split()]
    imos = [[0] * N for _ in range(N)]
    for i in range(M):
        l, r = [int(i)-1 for i in input().split()]
        imos[l][r]+=1
    # print(imos)
    for h in range(N):
        for w in range(1, N):
            imos[h][w] += imos[h][w-1]
    for h in reversed(list(range(1, N))):
        for w in range(N):
            imos[h-1][w] += imos[h][w]
    # print(imos)
    ans = [0]*Q
    for q in range(Q):
        ql, qr = [int(i)-1 for i in input().split()]
        ans[q] = imos[ql][qr]
    for a in ans:
        print(a)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import numpy as np
n,m,q=map(int,input().split())
s=np.zeros((n,n))
for i in range(m):
    l,r=map(int,input().split())
    s[n-l][r-1]+=1
s=np.cumsum(np.cumsum(s,axis=0),axis=1)
for i in range(q):
    d,t=map(int,input().split())
    print(int(s[n-d][t-1]))

Submission status: Accepted

Solution code:
from collections import Counter
from functools import lru_cache
import sys
sys.setrecursionlimit(2*10**5)

N, M, Q = map(int, input().split())
L, R = zip(*(map(int, input().split()) for _ in range(M)))
p, q = zip(*(map(int, input().split()) for _ in range(Q)))

c = Counter(zip(L, R))


@lru_cache(maxsize=None)
def f(x, y):
    return (
        0 if x > y else
        c[x, y] + f(x + 1, y) + f(x, y - 1) - f(x + 1, y - 1)
    )


ans = '\n'.join(map(str, (f(x, y) for x, y in zip(p, q))))
print(ans)

Submission status: Accepted

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

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

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

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

    ans  = sum_v[q][q]
    ans -= sum_v[q][p-1]
    ans -= sum_v[p-1][q]
    ans += sum_v[p-1][p-1]

    print(ans)

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
#shift to left and add
b=a.cumsum(1)
#rotate 180
b=np.flipud(b)
#shift down and add
b=b.cumsum(0)
#rotate 180
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:
n, m, q = [int(item) for item in input().split()]

lr = [[int(item) for item in input().split()] for _ in range(m)]
pq = [[int(item) for item in input().split()] for _ in range(q)]

field = [[0] * (n+1) for _ in range(n+1)]
cumsum = [[0] * (n+1) for _ in range(n+1)]

for item in lr:
  field[item[0]][item[1]] += 1
  
for i in range(1,n+1):
  for j in range(1,n+1):
    cumsum[i][j] = field[i][j] + cumsum[i][j-1]

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
dist = [list(map(int,input().split())) for i in range(m)]
query = [list(map(int,input().split())) for i in range(q)]

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

for i in range(m):
  coord[dist[i][0]][dist[i][1]] += 1

ruiseki = [[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
  for j in range(1,n+1):
    ruiseki[i][j] = coord[i][j] + ruiseki[i-1][j]
 
for i in range(1,n+1):
  for j in range(1,n+1):
    ruiseki[i][j] = ruiseki[i][j]+ ruiseki[i][j-1]
#print(ruiseki)

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

Submission status: Accepted

Solution code:
#!usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

#C
def C():
    s = S()
    k = I()
    for i in range(k):
        if s[i] != "1":
            print(s[i])
            quit()
    print(1)

#D
def D():
    n,m,q = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        l,r = LI()
        v[l-1].append(r-1)
    for i in range(n):
        v[i].sort()
    f = [[bisect.bisect_right(v[i],j) for j in range(n)] for i in range(n)]
    for i in range(q):
        p,q = LI()
        p -= 1
        q -= 1
        ans = 0
        for j in range(p,q+1):
            ans += f[j][q]
        print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

#Solve
if __name__ == "__main__":
    D()

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
dp=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
    a=list(map(int,input().split()))
    dp[a[0]][a[1]]+=1
for i in range(N,0,-1):
    count=0
    for j in range(1,N+1):
        count+=dp[i][j]
        if i==N:
            dp[i][j]=count
        else:
            dp[i][j]=dp[i+1][j]+count
p=[list(map(int,input().split())) for i in range(Q)]
for i in range(Q):
    print(dp[p[i][0]][p[i][1]])

Submission status: Accepted

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

for _ in range(M):
    a = list(map(int, input().split()))
    N_Map[a[0]][a[1]] += 1

for i in range(N, 0, -1):
    count = 0
    for j in range(1, N  + 1):
        count += N_Map[i][j]
        if i < N:
            N_Map[i][j] = N_Map[i + 1][j] + count
        else:
            N_Map[i][j] = count

Pi = []
for _ in range(Q):
    a = list(map(int, input().split()))
    Pi.append(a)

for p in Pi:
    print(N_Map[p[0]][p[1]])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
Data = [list(map(lambda x: int(x) - 1, input().split())) for i in range(M)]


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

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

    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 y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif 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:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


# 二次元累積和( ･´ｰ･｀)
R2D = Ruisekiwa2D(N, N)
R2D.load(Data)
R2D.calc()


# クエリに答えていく
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:
import numpy as np
N, M, Q = map(int, input().split())
RcntL = np.zeros((N+1, N+1), int)
for _ in range(M):
    l, r = map(int, input().split())
    RcntL[r, l] += 1
pq = []
for _ in range(Q):
    pq.append(list(map(int, input().split())))

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

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

Submission status: Accepted

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

N, M, Q = inpl()
cumsum = [0]*((N+1)**2)
ans = [0]*((N+1)**2)

for i in range(M):
    L, R = inpl()
    cumsum[L*(N+1)+R] += 1

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

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

for i in range(Q):
    p, q = inpl()
    print(ans[p*(N+1)+q])

Submission status: Accepted

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

for i in range(0, m):
    l, r = [int(j) for j in input().split(" ")]
    c[1 + n - l][r] += 1

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

for i in range(0, q):
    pi, qi = [int(j) for j in input().split(" ")]
    print(s[1 + n - pi][qi])

Submission status: Accepted

Solution code:
class Sum2D:
    def __init__(self,h,w):
        self.height=h
        self.width=w
        self.data=[[0]*(self.width+1) for _ in range(self.height+1)]
    def add(self,x,y,v):
        self.data[x][y]+=v
    def build(self):
        for x in range(self.height):
            for y in range(self.width):
                self.data[x+1][y+1]+=self.data[x+1][y]
                self.data[x+1][y+1]+=self.data[x][y+1]
                self.data[x+1][y+1]-=self.data[x][y]
    def query(self,p,q):
        return self.data[q][q]+self.data[p][p]-self.data[p][q]-self.data[q][p]

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m,q=map(int,input().split())
S=Sum2D(n,n)
for _ in range(m):
    l,r=map(int,input().split())
    S.add(l,r,1)
S.build()
for _ in range(q):
    l,r=map(int,input().split())
    print(S.query(l-1,r))

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m,q=map(int, input().split())
Num2D=[[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    l,r=map(int,input().split())
    Num2D[l][r]+=1
for i in range(n):
    for j in range(n):
        Num2D[i+1][j+1]+=Num2D[i+1][j]
        Num2D[i+1][j+1]+=Num2D[i][j+1]
        Num2D[i+1][j+1]-=Num2D[i][j]
for _ in range(q):
    l,r=map(int,input().split())
    print(Num2D[r][r]+Num2D[l-1][l-1]-Num2D[l-1][r]-Num2D[r][l-1])

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m,q = map(int,input().split())

res = [[0]*n for i in range(n)]
for i in range(m):
    L,r = map(int,input().split())
    L -= 1
    r -= 1
    res[r][0] += 1
    if L != n-1:
        res[r][L+1] -= 1

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

Submission status: Accepted

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

table = []
for i in range(n+1):
    table.append([0]*(n+1))
for i in range(m):
    a,b = map(int,input().split())
    table[b][a] += 1

#2...n
for i in range(2,n+1):

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

for _ in range(q):
    start,end = map(int,input().split())
    print(table[end][start])

Submission status: Accepted

Solution code:
class CumulativeSum2D:
    def __init__(self, size: int):
        self.size = size
        self.data = [[0 for _ in range(N + 1)] for _ in range(N + 1)]

    def add(self, l: int, r: int, v: int):
        self.data[l][r] += v

    def build(self):
        for l in range(self.size):
            for r in range(self.size):
                self.data[l + 1][r + 1] += self.data[l + 1][r]
                self.data[l + 1][r + 1] += self.data[l][r + 1]
                self.data[l + 1][r + 1] += -self.data[l][r]

    def query(self, l: int, r: int) -> int:
        """(l, r] x (l, r]
        """
        return self.data[r][r] + self.data[l][l] - self.data[l][r] - self.data[r][l]


def atcoder_express2(
        N: int, M: int, Q: int, data: list, queries: list) -> list:
    # 二次元累積和
    S = CumulativeSum2D(N)
    for l, r in data:
        S.add(l, r, 1)
    S.build()

    return [S.query(p-1, q) for p, q in queries]


if __name__ == "__main__":
    M, Q = 0, 0
    N, M, Q = map(int, input().split())
    data = [tuple(int(s) for s in input().split()) for _ in range(M)]
    queries = [tuple(int(s) for s in input().split()) for _ in range(Q)]
    ans = atcoder_express2(N, M, Q, data, queries)
    for a in ans:
        print(a)

Submission status: Accepted

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

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

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


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

Submission status: Accepted

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import math
import sys

import math
import sys


## input
n,m,q = map(int, sys.stdin.readline().rstrip().split())

## l,r をinputしてdp
num_s = [[0 for j in range(n+2)] for i in range(n+2)]
for _ in range(m):
  l,r = map(int, sys.stdin.readline().rstrip().split())
  num_s[l][r] += 1

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

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

ans = []
for _ in range(q):
  p,q = map(int, sys.stdin.readline().rstrip().split())
  ans.append(dp[p][q])

## output
for a in ans:
  print(a)

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
train = [tuple(map(int, input().split())) for _ in range(m)]
quest = [tuple(map(int, input().split())) for _ in range(q)]
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
d = {}
for l in range(n):
    for r in range(l,n):
        d[(l+1,r+1)] = 0
for p, q in train:
    d[(p,q)] += 1
for l in range(1,n+1):
    dp[l][l] = d[(l,l)]
for w in range(1,n):
    for l in range(n-w):
        dp[l+1][l+w+1] = dp[l+1][l+w] + dp[l+2][l+w+1] - dp[l+2][l+w] + d[(l+1,l+w+1)]
for l, r in quest:
    print(dp[l][r])

Submission status: Accepted

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


main()