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

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

for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            pass
        elif i == 0:
            XY[i][j] += XY[i][j - 1]
        elif j == 0:
            XY[i][j] += XY[i - 1][j]
            pre_im1_j = XY[i - 1][j]
        else:
            if XY[i - 1][j] == pre_im1_j:
                XY[i][j] += XY[i][j - 1]
            else:
                XY[i][j] += XY[i][j - 1] + XY[i - 1][j] - pre_im1_j
                pre_im1_j = XY[i - 1][j]

for p, q in pq:
    if p != 1:
        print(XY[q - 1][q - 1] + XY[p - 2][p - 2] - XY[p - 2][q - 1] - XY[q - 1][p - 2])
    else:
        print(XY[q - 1][q - 1])

Submission status: Accepted

Solution code:
n,m,q = (int(x) for x in input().split())
field = [[0]*n for i in range(n)]
S = [[0]*(n+1) for i in range(n+1)]

for i in range(m):
  l,m = (int(x) for x in input().split())
  field[l-1][m-1] += 1

#累積和
for i in range(n):
  for j in range(n):
    S[i+1][j+1] = S[i][j+1] + S[i+1][j] - S[i][j] + field[i][j]
    
for i in range(q):
  begin,end = (int(x) for x in input().split())
  print(S[end][end] - S[begin - 1][end] - S[end][begin - 1] + S[begin - 1][begin - 1])

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

#A
def A():
    n,m = LI()
    a = LIR(n)
    ans = 0
    for i in range(2):
        for j in range(2):
            for k in range(2):
                a.sort(key = lambda x:(-1)**i*x[0]+(-1)**j*x[1]+(-1)**k*x[2])
                p = [0,0,0]
                for l in range(m):
                    p[0] += a[l][0]
                    p[1] += a[l][1]
                    p[2] += a[l][2]
                p = abs(p[0])+abs(p[1])+abs(p[2])
                if p > ans:
                    ans = p
    print(ans)
    return

#B
def B():
    def root(x):
        if x == par[x]:
            return x
        par[x] = root(par[x])
        return par[x]

    def unite(x,y,su):
        x = root(x)
        y = root(y)
        su += comb_2(s[x])+comb_2(s[y])
        if rank[x] < rank[y]:
            s[y] += s[x]
            su -= comb_2(s[y])
            par[x] = y
        else:
            s[x] += s[y]
            su -= comb_2(s[x])
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return su

    def comb_2(a):
        return a*(a-1)//2

    n,m = LI()
    v = LIR(m)
    par = [i for i in range(n)]
    rank = [0]*n
    s = [1]*n
    su = comb_2(n)
    ans = [su]
    for a,b in v[:0:-1]:
        a -= 1
        b -= 1
        if root(a) != root(b):
            su = unite(a,b,su)
        ans.append(su)
    for i in ans[::-1]:
        print(i)
    return

#C
def C():
    def root(x):
        if par[x] == x:
            return par[x]
        r = root(par[x])
        d[x] += d[par[x]]
        par[x] = r
        return par[x]

    def weight(x):
        root(x)
        return d[x]

    def unite(x,y,w):
        w += weight(x)
        w -= weight(y)
        x = root(x)
        y = root(y)
        if rank[x] < rank[y]:
            par[x] = y
            d[x] = -w
        else:
            par[y] = x
            d[y] = w
            if rank[x] == rank[y]:
                rank[x] += 1
    n,m = LI()
    par = [i for i in range(n)]
    rank = [0]*n
    d = [0]*n
    for i in range(m):
        l,r,w = LI()
        l -= 1
        r -= 1
        if root(l) != root(r):
            unite(l,r,w)
        else:
            if weight(r)-weight(l) != w:
                print("No")
                return
    print("Yes")
    return

#D
def D():
    h,w = LI()
    n = I()
    a = LI()
    ans = [0]*h*w
    p = 0
    for i in range(n):
        for j in range(a[i]):
            ans[p+j] = i+1
        p += a[i]
    for i in range(h):
        s = ans[i*w:(i+1)*w]
        if i%2:
            print(*s[::-1])
        else:
            print(*s)
    return

#E
def E():
    n,k = LI()
    s = [int(x) for x in input()]
    f = [0]*n
    j = 0
    su = 1
    p = s[0]
    for i in range(1,n):
        if s[i] != p:
            f[j] = su
            j += 1
            su = 1
            p = s[i]
        else:
            su += 1
    f[j] = su
    f.append(0)
    if s[0]:
        m = sum(f[:2*k+1])
        ans = m
        for i in range(2*k+1,n):
            m -= f[i-2*k-1]
            if not i%2:
                m += f[i-1]
                m += f[i]
            ans = max(m,ans)
    else:
        m = sum(f[:2*k])
        ans = m
        for i in range(2*k,n):
            m -= f[i-2*k]
            if not i%2:
                m += f[i]
                m += f[i+1]
            ans = max(m,ans)
    print(ans)
    return

#F
def F():
    n = I()
    a = LI()
    s = [0,0,0]
    for i in a:
        if i%4 == 0:
            s[0] += 1
        elif i%2 == 0:
            s[1] += 1
        else:
            s[2] += 1
    a = [0]
    while 1:
        if s[2]:
            if a[-1] == 2:
                print("No")
                return
            s[2] -= 1
            a.append(2)
            if s[0]:
                s[0] -= 1
                a.append(0)
        elif s[1]:
            if a[-1] == 2:
                print("No")
            else:
                print("Yes")
            return
        else:
            print("Yes")
            return
    return

#G
def G():
    n,m,l = LI()
    r = LI()
    for i in range(l):
        r[i] -= 1
    d = [[float("inf")]*n for i in range(n)]
    for i in range(n):
        d[i][i] = 0
    for i in range(m):
        a,b,c = LI()
        a -= 1
        b -= 1
        d[a][b] = c
        d[b][a] = c
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k]+d[k][j])
    m = 1<<l
    dp = [[float("inf")]*l for i in range(m)]
    for i in range(l):
        dp[1<<i][i] = 0
    for b in range(m):
        for i in range(l):
            x = r[i]
            if not b&(1<<i):
                continue
            for j in range(l):
                if b&(1<<j):
                    continue
                nb = b|(1<<j)
                y = r[j]
                res = dp[b][i]+d[x][y]
                if res < dp[nb][j]:
                    dp[nb][j] = res
    print(min(dp[m-1]))
    return

#H
def H():
    n,m,q = LI()
    f = [[0]*(n+1) for i in range(n+1)]
    for i in range(m):
        l,r = LI()
        f[l][r] += 1
    for i in range(n+1):
        for j in range(n):
            f[i][j+1] += f[i][j]

    for j in range(n+1):
        for i in range(n):
            f[i+1][j] += f[i][j]
    for i in range(q):
        l,r = LI()
        print(f[r][r]-f[r][l-1]-f[l-1][r]+f[l-1][l-1])
    return

#I
def I_():

    return

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
N, M, Q = map(int, input().split())
l=[]
p=[]
for i in range(M):
    t=input().split()
    l.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=input().split()
    p.append((int(t[0]),int(t[1])))

ans = int(0)
count = int(0)
sumTrain = [[0 for i in range(N+1)] for j in range(N+1)]
ansTrain = [[-1 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    sumTrain[l[i][0]][l[i][1]] += 1

def dfs(l, r):
    if not l <= r:
        return 0
    if l == r:
        return sumTrain[l][r]
    if ansTrain[l][r] != -1:
        return ansTrain[l][r]
    ansTrain[l][r] = res = sumTrain[l][r] + dfs(l+1, r) + dfs(l, r-1) - dfs(l+1, r-1)
    return res

for i in range(Q):
    ans = dfs(p[i][0],p[i][1])
    print(ans)

Submission status: Accepted

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

dp = [[0 for _ in range(N)] for _ in range(N)]

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

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

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

# dp[l][r]は左端がl以下右端がr以下の電車の本数を表す   
for _ in range(Q):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    
    if p >= 1:
        print(dp[N-1][q]-dp[p-1][q])
    else:
        print(dp[N-1][q])

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
from operator import itemgetter

c = []

def main():
	global c
	n, m, q = map(int, input().strip().split())
	xy = [[0] * (n+1) for _ in range(n+1)]
	for i in range(m):
		l, r = map(int, input().strip().split())
		xy[l][r] += 1
	c = [[0] * (n+2) for _ in range(n+1)]
	for i in range(n+1):
		for j in range(n+1):
			c[i][j+1] = xy[i][j] + c[i][j]

	# print(c)
	for i in range(q):
		ans = 0
		p, q = map(int, input().strip().split())
		for k in range(p, q+1):
			ans += c[k][q+1] - c[k][p]
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def cumsum(mydata):
    cumsum = [0]*(len(mydata)+1)
    cumsum[0] = 0
    for i in range(len(mydata)):
        cumsum[i+1] = cumsum[i] + mydata[i]
    return cumsum

def main():
    n,m,q = map(int,input().split())
    train_ls = [[0 for _ in range(n)] for _ in range(n)]
    for _ in range(m):
        l,r = map(int,input().split())
        train_ls[r-1][l-1] += 1
    cumsums = []
    for i in range(n):
        cumsums.append(cumsum(train_ls[i]))
    
    q_ls = [[int(x) for x in input().split()] for _ in range(q)]
    for left,right in q_ls:
        ans = 0
        for i in range(left,right+1):
            ans += cumsums[i-1][right] - cumsums[i-1][left-1]
        print(ans)
        
if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

for l, r in X:
    p[l][r] += 1
    
for i in range(1, N + 1):
    for j in range(1, N + 1):
        p[i][j] += p[i][j - 1]
        
for i in range(1, N + 1):
    for j in range(1, N + 1):
        p[i][j] += p[i - 1][j]
        
for l, r in Y:
    ans = p[r][r] + p[l - 1][l - 1] - p[l - 1][r] - p[r][l - 1]
    print(ans)

Submission status: Accepted

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


def to_cumsum(arr):
    """
    1次元配列を累積和の1次元配列に変換する
    """
    cumsum = 0
    new = list()
    for e in arr:
        cumsum += e
        new.append(cumsum)
    return new


def to_cumsum2d(mat):
    """
    2次元配列を累積和の2次元配列に変換する
    """
    new = [[None for _ in range(len(mat[0]))] for _ in range(len(mat))]
    for i, row in enumerate(mat):
        new[i][0] = row[0]
    new[0] = to_cumsum(mat[0])
    for i in range(1, len(mat)):
        for j in range(1, len(mat[0])):
            new[i][j] = new[i][j - 1] + new[i - 1][j] - new[i - 1][j - 1] + mat[i][j]
    return new


# train[L][R] := LからRに向かう電車の数
train = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for L, R in LR:
    train[L][R] += 1

# 2次元累積和に変換
train = to_cumsum2d(train)

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

Submission status: Accepted

Solution code:
import numpy as np
n, m, q = map(int, input().split())
lst = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
    l, r = map(int, input().split())
    lst[l][r] += 1
lst = np.array(lst)
for i in range(1, n+1):
    lst[:, i] += lst[:, i-1]
for j in range(1, n+1):
    lst[j, :] += lst[j-1, :]
for i in range(q):
    p, q = map(int, input().split())
    print(lst[q, q] - lst[p-1, q] - lst[q, p-1] + lst[p-1, p-1])

Submission status: Accepted

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

import sys
import math
import bisect
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
mod = 10**9 + 7

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

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

Submission status: Accepted

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

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

lst = np.array(lst)
# print (lst)

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


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

# print (lst)

Submission status: Accepted

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# W行H列, x[W][H]
def create_grid(W, H, value = 0):
    return [[ value for _ in range(H)] for _ in range(W)]

########
N, M, Q = l_inpl()

l, r = [], []
for _ in range(M):
    li, ri = l_inpl()
    l.append(li)
    r.append(ri)

p, q = [], []
for _ in range(Q):
    pi, qi = l_inpl()
    p.append(pi)
    q.append(qi)

s = create_grid(N+1, N+1)

for i in range(M):
    s[l[i]][r[i]] += 1

for hi in range(1, N+1):
    for wi in range(1, N+1):
        s[hi][wi] += s[hi-1][wi]
        s[hi][wi] += s[hi][wi-1]
        s[hi][wi] -= s[hi-1][wi-1]

for i in range(Q):
    pi, qi = p[i], q[i]
    print(s[qi][qi] - s[qi][pi-1] - s[pi-1][qi] + s[pi-1][pi-1])

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
LR = [list(map(int,input().split())) for _ in [0]*M]
PQ = [list(map(int,input().split())) for i in range(Q)]

c = [[0]*N for _ in [0]*N]

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
n, m, q = map(int, input().split())
kukan = np.zeros((n+1, n+1))
for _ in range(m):
    l, r = map(int, input().split())
    kukan[r][l] += 1

# まず終点の側から考える
# iまでに終わる線分の数はi-1までの累積和
for i in range(1, n+1):
    kukan[i] += kukan[i-1]
# 次に始点の側から考える
# i以降に始まる線分の数はi-1までの総和
for i in range(1, n+1):
    kukan[:, i] += kukan[:, i-1]
# print(kukan)
for i in range(1, q+1):
    p, q = list(map(int, input().split()))
    print(int(kukan[q][q] - kukan[q][p-1] - kukan[p-1][q] + kukan[p-1][p-1]))

Submission status: Accepted

Solution code:
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)]
#print(LR,PQ)

d = [[0]*n for i in range(n)]

for i in range(m):
    l = LR[i][0]-1
    r = LR[i][1]-1
    d[l][r] += 1
#print(d)

c = [[0]*n for i in range(n)]
for i in range(n):
    for j in range(n):
        if j == 0:
            c[i][j] = d[i][j]
        else:
            c[i][j] = c[i][j-1] + d[i][j]
#print(c)
for i in range(q):
    l = PQ[i][0]-1
    r = PQ[i][1]-1
    res = 0
    for j in range(l,r+1):
        if j == 0 or l == 0:
            res += c[j][r]
        else:
            res += (c[j][r]-c[j][l-1])
    print(res)

Submission status: Accepted

Solution code:
N,M,Q = map(int, input().split())
train = []
quest = []
for i in range(M):
    train.append([int(x) for x in input().split()])
for j in range(Q):
    quest.append([int(x) for x in input().split()])

List = []
for s in range(N):
    List.append([])

for k in range(N):
    for l in range(k+1):
        List[k].append(0)

for i in range(M):
    List[N-(train[i][1]-train[i][0]+1)][train[i][0]-1] += 1

num = N-1

while num >= 1:
    for j in range(len(List[num-1])):
        List[num-1][j] += List[num][j] + List[num][j+1]
        if num-1 < N-2:
            List[num-1][j] -= List[num+1][j+1]
    num -= 1
for k in range(Q):
    print( List[N-(quest[k][1]-quest[k][0]+1)][quest[k][0]-1])

Submission status: Accepted

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

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

    check = np.zeros((N+1, N+1))

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

    check = np.zeros((N+1, N+1))

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

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
lr = [[0,0] for _ in range(M)]
pq = [[0,0] for _ in range(Q)]
L = [[0]*N for _ in range(N)]
for i in range(M):
    lr[i][0], lr[i][1] = map(int,input().split())
    L[lr[i][0]-1][lr[i][1]-1] += 1
for i in range(Q):
    pq[i][0], pq[i][1] = map(int,input().split())
    pq[i][0] -= 1
    pq[i][1] -= 1
L_sum = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if i == 0 and j == 0:
            L_sum[i][j] = L[i][j]
        if i == 0 and j != 0:
            L_sum[i][j] = L[i][j] + L_sum[i][j-1]
        if i != 0 and j == 0:
            L_sum[i][j] = L[i][j] + L_sum[i-1][j]
        if i != 0 and j != 0:
            L_sum[i][j] = L[i][j] + L_sum[i][j-1] + L_sum[i-1][j] - L_sum[i-1][j-1]
for i in range(Q):
    if pq[i][0] == 0:
        print(L_sum[pq[i][1]][pq[i][1]])
    else:
        print(L_sum[pq[i][1]][pq[i][1]]-L_sum[pq[i][0]-1][pq[i][1]])

Submission status: Accepted

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

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

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

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

# 累積和
S = [[0 for _ in range(N+1)] for _ in range(N+1)]  # ゼロパディング

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

for x in range(N+1):
    for y in range(N):
        table[N-y-1][x]+=table[N-y][x]
        
for p, q in P:
    print(table[p][q])

Submission status: Accepted

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

tbl = [[0] * (N + 1) for _ in range(N + 1)]
# tbl[L][R] = 累積和
# 1-indexed

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

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

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

Submission status: Accepted

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

lr = [ [0]*(N+1) for i in range(N+1)]
for i in range(M):
    l,r = LR[i][0],LR[i][1]
    lr[l][r] += 1

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

for i in range(Q):
    ans = 0
    p,q = pq[i][0],pq[i][1]
    for i in range(p,q+1):
        ans += (lr[i][q] - lr[i][p-1])
    print(ans)

Submission status: Accepted

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

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

LR_array = [list(map(int, input().split())) for _ in range(M)]
PQ_array = [list(map(int, input().split())) for _ in range(Q)]

for lr in LR_array:
    l, r = lr
    ans_array[l - 1][r - 1] += 1

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


for pq in PQ_array:
    p, q = pq
    print(ans_array[p-1][q-1])

Submission status: Accepted

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

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

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


for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1

    print(train[r+1][r+1] - train[l][r+1] - train[r+1][l] + train[l][l])

Submission status: Accepted

Solution code:
from copy import copy

N, M, Q = map(int, input().split())
area = [copy([0]*N) for i in range(N)]
L = [0]*N
R = [0]*N

# O(M)
for i in range(M):
    l, r = map(int, input().split())
    area[l-1][r-1] += 1

# O(N^2)
for i in range(N):
    for j in range(i, -1, -1):
        if j!=i:
            area[j][i] += area[j+1][i]

# O(N^2)
for i in range(N):
    for j in range(i, -1, -1):
        if j != i:
            area[j][i] += area[j][i-1]

# O(Q)
count = 0
for i in range(Q):
    p, q = map(int, input().split())
    print(area[p-1][q-1])

Submission status: Accepted

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

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

for i in range(M):
  ans[LR[i][0]-1][LR[i][1]-1] +=1
  
ans_sum=[[0 for i in range(N)] for j in range(N)]
  
for l in range(N):
  for r in range(N):
    if N-1-l > r:
      ans_sum[N-1-l][r] = 0
    elif N-1-l == r:
      ans_sum[N-1-l][r]=ans[N-1-l][r]
    else:
      ans_sum[N-1-l][r]=ans_sum[N-l][r]+ans_sum[N-1-l][r-1]-ans_sum[N-l][r-1]+ans[N-1-l][r]

for i in range(Q):
  print(ans_sum[pq[i][0]-1][pq[i][1]-1])

Submission status: Accepted

Solution code:

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

dp = [[0 for _ in range(N)] for _ in range(N)]

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

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

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

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

Submission status: Accepted

Solution code:
from collections import Counter
from collections import deque
from functools import reduce
from pprint import pprint
import bisect
import copy
import fractions
import itertools
import math
import queue
import random
import sys
import time
sys.setrecursionlimit(10**7)
INF = 10 ** 18
MOD = 10 ** 9 + 7
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def MI(): return map(int, sys.stdin.readline().split())
def II(): return int(sys.stdin.readline())
def IS(): return input()
def C(x): return Counter(x)
def GCD_LIST(numbers): return reduce(fractions.gcd, numbers)
def LCM_LIST(numbers): return reduce(LCM, numbers)
def LCM(m, n): return (m * n // fractions.gcd(m, n))
class UnionFind():

    def __init__(self, n):
        self.n = n
        self.node = [i for i in range(n)]
        self.size = [1 for _ in range(n)]

    def same(self, x, y):
        return bool(self.root(x) == self.root(y))

    def root(self, x):
        if self.node[x] == x:
            return x
        else:
            self.node[x] = self.root(self.node[x])  # 経路圧縮
            return self.node[x]

    def unite(self, x, y):
        x, y = self.root(x), self.root(y)
        if x == y:
            return  # 結合不要
        if self.size[x] < self.size[y]:
            x, y = y, x
        self.node[y] = x
        self.size[x] += self.size[y]

    def return_size(self, x):
        return self.size[self.root(x)]


n, m, q = MI()
train = [LI() for _ in range(m)]
query = [LI() for _ in range(q)]
table = [[0 for _ in range(n+1)] for _ in range(n+1)]
ruisekiwa = [[0 for _ in range(n+1)] for _ in range(n+1)]
for left, right in train:
    table[left][right] += 1
for i in range(1, n+1):
    for j in range(1, n+1):
        ruisekiwa[i][j] = table[i][j]
        if j > 1:
            ruisekiwa[i][j] += ruisekiwa[i][j-1]
        if i > 1:
            ruisekiwa[i][j] += ruisekiwa[i-1][j]
        if j > 1 and i > 1:
            ruisekiwa[i][j] -= ruisekiwa[i-1][j-1]
for p, q in query:
    print(ruisekiwa[q][q] - ruisekiwa[p-1][q] - ruisekiwa[q][p-1] + ruisekiwa[p-1][p-1])