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:
#!/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()
    intervals = []
    for _ in range(m):
        l, r = mi()
        intervals.append((l - 1, r))
    intervals.sort(key=itemgetter(1))

    commands = []
    for _ in range(q):
        a, b = mi()
        commands.append((a - 1, b))

    
    # completely_included[i] = ([0:i] で完全に含んでいる区間数)
    completely_included = [0] * (n + 1)
    for _, right in intervals:
        completely_included[right] += 1
    prev = 0
    for i in range(1, n + 1):
        completely_included[i] += prev
        prev = completely_included[i]
    # print(completely_included)
    
    # across_num[r][l] = (0:right に含まれるインターバルのうち、left を内部に含むようなインターバルの個数)
    across_num = [[0] * (n + 1) for _ in range(n + 1)]
    for left, right in intervals:
        if right - left >= 2:
            for i in range(right, n + 1):
                across_num[i][left + 1] += 1
                across_num[i][right] -= 1
    for i in range(1, n + 1):
        prev = 0
        for j in range(1, n + 1):
            across_num[i][j] += prev
            prev = across_num[i][j]
    

    def calc_included_intervals(left, right):
        return completely_included[right] - completely_included[left] - across_num[right][left]


    for l, r in commands:
        print(calc_included_intervals(l, r))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = lambda :sys.stdin.readline().rstrip()

def main():
    n, m, Q = map(int, input().split())
    Train= [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(m):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        Train[l][r] += 1
    
    P_Train = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for i in range(n):
        for j in range(n):
            P_Train[i + 1][j + 1] = P_Train[i][j + 1] + P_Train[i + 1][j] + Train[i][j] - P_Train[i][j]
    
    #print(*P_Train, sep = '\n')

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

def solve(P_Train, p, q):
    ans = 0
    ans = P_Train[q + 1][q + 1] -P_Train[p][q + 1] - P_Train[q + 1][p] + P_Train[p][p]
    return ans


if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 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 II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main_old(): 
    N, M, queries = LI()
    L = []
    R = []
    for _ in range(M):
        l, r = LI()
        L.append(l)
        R.append(r)
    P = []
    Q = []
    for _ in range(queries):
        p, q = LI()
        P.append(p)
        Q.append(q)

    regions = [[] for _ in range(N+1)]
    for l, r in zip(L, R):
        regions[l].append(r-l)
    regions_cumsum = [[0]*(N+1) for _ in range(N+1)]
    for i in range(len(regions)):  # [0,1,1,1,2,2] みたいなのを [1, 4, 6] と変換したい。
        # まずはカウントする
        cnt = [0]*(N+1)
        for j in range(N+1):
            cnt[regions[i][j]] += 1
        # 続いて累積和を取る。
        regions_cumsum[0] = cnt[0]
        for j in range(1, N+1):
            regions_cumsum[j] = regions_cumsum[j-1] + cnt[j]

    from bisect import bisect_right
    
    for p, q in zip(P, Q):
        counter = 0
        length = q-p
        print(regions_cumsum[q] - regions_cumsum[p])




    # 駅番号: [そこから出る区間の長さのリスト] を持つ。
    # クエリを駅番号・長さに持ち替えてソート。
    # クエリごとに、駅番号において長さよりも短い電車が何本あるか見ていく。となりの駅に写ったら1引く。
    # これでQ*N？



def main(): 
    N, M, queries = LI()
    L = []
    R = []
    for _ in range(M):
        l, r = LI()
        L.append(l)
        R.append(r)
    P = []
    Q = []
    for _ in range(queries):
        p, q = LI()
        P.append(p)
        Q.append(q)

    trains = [[0]*(N+1) for _ in range(N+1)]
    for l, r in zip(L,R):
        trains[l][r] += 1

    cumsum = [[0]*(N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, N+1):
            cumsum[i][j] = cumsum[i][j-1] + trains[i][j]

    for p, q in zip(P, Q):
        range_sum = 0
        for i in range(p, q+1):
            range_sum += cumsum[i][q] - cumsum[i][p-1]
        print(range_sum)

main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
n,m,q = map(int,input().split())
def func(a):
    return int(a)-1
grid = [[0]*n for i in range(n)]
pq = [0]*q
for i in range(m):
    l,r = map(func,input().split())
    grid[l][r] += 1
for i in range(q):
    pq[i] = list(map(func,input().split()))

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

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

anslist = [0]*q
for i in range(q):
    anslist[i] = s[pq[i][1]][pq[i][1]] - s[pq[i][1]][pq[i][0]-1] - s[pq[i][0]-1][pq[i][1]] + s[pq[i][0]-1][pq[i][0]-1] if pq[i][0] > 0 else s[pq[i][1]][pq[i][1]]
#print(grid)
#print(s)
for ans in anslist:
    print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
x=[[0]*N for i in range(N)]
for i in range(M):
    L,R=map(lambda x:int(x)-1,input().split())
    x[L][R]+=1
cum=[[0]*(N+1) for i in range(N+1)]
for l in range(N):
    for r in range(N):
        cum[l][r+1]=cum[l][r]+x[l][r]
for i in range(Q):
    p,q=map(lambda x:int(x)-1,input().split())
    res=0
    for l in range(p,q+1):
        res+=cum[l][q+1]-cum[l][p]
    print(res)

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = 10**20
def I(): return int(input())
def F(): return float(input())
def S(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LS(): return input().split()

def resolve():
    N, M, Q = map(int, input().split())
    LR = [LI_() for _ in range(M)]
    pq = [LI_() for _ in range(Q)]

    cnt = [[0]*N for _ in range(N)]
    for i in LR:
        cnt[i[0]][i[1]] += 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+1][j] + cnt[i][j]
    for i in range(N):
        for j in range(N):
            acc[i+1][j+1] += acc[i][j+1]

    for i in pq:
        p = i[0]
        q = i[1]
        ans = acc[q+1][q+1] - acc[p][q+1] - acc[q+1][p] + acc[p][p]
        print(ans)

if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

train = [[0 for _ in range(501)] for _ in range(501)]
train_total = [[0 for _ in range(501)] for _ in range(501)]
query = []

for i in range(m):
    a, b = map(int, input().split())
    train[a][b] += 1

for j in range(q):
    x, y = map(int, input().split())
    query.append([x, y])

for left in range(0, 501):
    cnt = 0
    for right in range(0, 501):
        cnt += train[left][right]
        train_total[left][right] = cnt

for left, right in query:
    total = 0
    for row in range(left, right+1):
        num2 = train_total[row][right]
        num1 = train_total[row][left-1]
        total += (num2 - num1)
    print(total)

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)


# da[i][j]:(0,0)~(i,j)の長方形の和
def da_generate(h, w, a):
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i-1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j] + cnt_w
    return da


# da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(p, q, x, y):
    if p > x or q > y:
        return 0
    if p == 0 and q == 0:
        return da[x][y]
    if p == 0:
        return da[x][y] - da[x][q-1]
    if q == 0:
        return da[x][y] - da[p-1][y]
    return da[x][y] - da[p-1][y] - da[x][q-1] + da[p-1][q-1]


n, m, q = map(int, readline().split())
lr = [[0] * (n + 1) for _ in range(n + 1)]
for _ in range(m):
    l, r = map(int, readline().split())
    lr[l][r] += 1
da = da_generate(n + 1, n + 1, lr)
for _ in range(q):
    p, q = map(int, readline().split())
    print(da_calc(p, p, q, q))

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,q = inpl()
g = [[0]*n for _ in range(n)]
gg = [[0]*n for _ in range(n)]
for _ in range(m):
    l,r = inpl()
    l,r = l-1, r-1
    g[l][r] += 1
for i in range(n)[::-1]:
    for j in range(n):
        # print(i)
        if i == n-1:
            gg[i][j] += g[i][j]
            continue
        gg[i][j] += g[i][j] + gg[i+1][j]
# print(gg)
for i in range(n):
    for j in range(n-1):
        gg[i][j+1] += gg[i][j]

# pprint.pprint(gg)
for _ in range(q):
    a,b = inpl()
    a,b = a-1,b-1
    print(gg[a][b])

Submission status: Accepted

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

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

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

ans = []
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    ans.append(A[q][q] - A[q][p] - A[p][q] + A[p][p])
print(*ans, sep='\n')

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
trains = [[0]*(n+1) for _ in range(n+1)]
ans = [[0]*(n+1) for _ in range(n+1)]
for i in range(m):
    l,r = map(int,input().split())
    trains[l][r] += 1
for i in range(1,n+1):
    cur = 0
    for j in range(i,n+1):
        cur += trains[i][j]
        ans[i][j] = cur
for i in range(q):
    p,q = map(int,input().split())
    ansi = 0
    for j in range(p,q+1):
        ansi += ans[j][q]
    print(ansi)

Submission status: Accepted

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

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

cwa = np.cumsum(np.cumsum(wa, axis=0), axis=1).tolist()
for i in range(Q):
    p, q = map(int, input().split())
    ans = cwa[N][q]-cwa[p-1][q]
    print(ans)

Submission status: Accepted

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

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

    tb = [[0] * (N + 1) for _ in range(N + 1)]
    # tb[L][R]:=区間LR内を走る列車総数
    for _ in range(M):
        L, R = map(int, input().split())
        tb[L][R] += 1

    for L in range(1, N + 1):
        for R in range(1, N + 1):
            tb[L][R] += tb[L - 1][R]
            tb[L][R] += tb[L][R - 1]
            tb[L][R] -= tb[L - 1][R - 1]

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

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


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

#2次元累積和
for i in range(n):
    for j in range(n):
        Acum[i+1][j+1] = Acum[i][j+1] + Acum[i+1][j] - Acum[i][j] + A[i][j]

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

Submission status: Accepted

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

p = [0]
q = [0]
for i in range(Q):
  a,b = map(int,input().split())
  p.append(a)
  q.append(b)


for i in range(1,Q+1):
  print(m[q[i]][q[i]]+m[p[i]-1][p[i]-1]-m[q[i]][p[i]-1]-m[p[i]-1][q[i]])

Submission status: Accepted

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

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


# 二次元累積和の計算
for i in range(N):
    for j in range(N):
        c_sum[i+1][j+1] += c_sum[i+1][j] + c_sum[i][j+1] - c_sum[i][j]

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

Submission status: Accepted

Solution code:
class Ruiseki2D:
    """二次元累積和を構築する"""
    def __init__(self, matrix):
        self.h = len(matrix)
        self.w = len(matrix[0])
        self.ru = [[0] * (self.w + 1) for _ in range(self.h + 1)]

        for i in range(self.h):
            for j in range(self.w):
                self.ru[i + 1][j + 1] = self.ru[i + 1][j] + matrix[i][j]
        for i in range(self.h):
            for j in range(self.w):
                self.ru[i + 1][j + 1] += self.ru[i][j + 1]

    def get_sum(self, hl, hr, wl, wr):
        """[hl, hr), [wl, wr) で囲まれた部分の和を求める"""
        return (self.ru[hr][wr] + self.ru[hl][wl]
                - self.ru[hr][wl] - self.ru[hl][wr])

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

matrix = [[0] * (n + 1) for i in range(n + 1)]
for l, r in info:
    matrix[l][r] += 1

ru = Ruiseki2D(matrix)

for q1, q2 in query:
    print(ru.get_sum(q1, q2 + 1, q1, q2 + 1))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M,Q = map(int,input().split())
LR = [tuple(map(int,input().split())) for i in range(M)]
PQ = [tuple(map(int,input().split())) for i in range(Q)]

imos = [[0]*(N+1) for _ in range(N+1)]
for l,r in LR:
    imos[l][r] += 1
for i in range(N+1):
    for j in range(N):
        imos[i][j+1] += imos[i][j]
for j in range(N+1):
    for i in range(N):
        imos[i+1][j] += imos[i][j]

ans = []
for p,q in PQ:
    p -= 1
    a = imos[q][q] + imos[p][p] - imos[p][q] - imos[q][p]
    ans.append(a)
print(*ans, sep='\n')

Submission status: Accepted

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

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

Submission status: Accepted

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

for i in range(1, M+1):
    l, r = map(int, input().split())
    LR[l][r] += 1
cLR = np.cumsum(np.cumsum(LR, axis=0), axis=1)

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10**6)
dp = []
train = []

def subq(l, r):
    global dp, train
    if l == 0 or r == 0:
        return 0
    else:
        tmp1 = dp[l][r]
        if tmp1 != -1:
            return tmp1
        else:
            tmp2 = train[l][r] + subq(l - 1, r) + subq(l, r - 1) -  subq(l - 1, r - 1)
            dp[l][r] = tmp2
            return tmp2

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

    for _ in range(qn):
        p, q = map(int, input().split())
        r = subq(q, q) - subq(p-1, q) - subq(q, p-1) + subq(p-1, p-1)
        print(r)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# 区間が出る問題は累積和を疑おう
N, M, Q = map(int, input().split())

# l から rまで行く鉄道の数
lr = [[0 for i in range(N + 1)] for j in range(N + 1)]
# l から r以前のどこかまで行く鉄道の数
imos = [[0 for i in range(N + 1)] for j 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(1, N + 1):
        imos[i][j] = imos[i][j-1] + lr[i][j]
res = []
for i in range(Q):
    ans = 0
    p, q = map(int, input().split())
    for i in range(p, q + 1):
        ans += imos[i][q]
    res.append(ans)

for row in res:
    print(row)

Submission status: Accepted

Solution code:





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


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

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



accum = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(i,N):
        if i == j:
            accum[i][j] = trains[i][j]
        else:
            accum[i][j] = accum[i][j-1] + trains[i][j]

for p, q in query:
    cnt = 0
    for i in range(p-1, q):
        cnt += accum[i][q-1]

    print(cnt)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import sys


# import math
# import bisect

# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize
# MOD = 10 ** 9 + 7

# ===CODE===
def main():
    n, m, z = map(int, input().split())
    ruisekiwa = [[0 for i in range(n + 1)] for j in range(n + 1)]

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

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

    for _ in range(z):
        p, q = map(int, sys.stdin.readline().split())
        ans = ruisekiwa[q][q] - ruisekiwa[p - 1][q] - ruisekiwa[q][p - 1] + ruisekiwa[p - 1][p - 1]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

j = 0
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][j - 1]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        S[i][j] += S[i - 1][j]

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

Submission status: Accepted

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


class Ruiseki2D:
    """二次元累積和を構築する"""
    def __init__(self, matrix):
        self.h = len(matrix)
        self.w = len(matrix[0])
        self.ru = [[0] * (self.w + 1) for _ in range(self.h + 1)]

        for i in range(self.h):
            for j in range(self.w):
                self.ru[i + 1][j + 1] = self.ru[i + 1][j] + matrix[i][j]
        for i in range(self.h):
            for j in range(self.w):
                self.ru[i + 1][j + 1] += self.ru[i][j + 1]

    def get_sum(self, hl, hr, wl, wr):
        """[hl, hr), [wl, wr) で囲まれた部分の和を求める"""
        return (self.ru[hr][wr] + self.ru[hl][wl]
                - self.ru[hr][wl] - self.ru[hl][wr])


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

matrix = [[0] * (n + 1) for i in range(n + 1)]
for l, r in info:
    matrix[l][r] += 1
ru = Ruiseki2D(matrix)

for l, r in query:
    ans = ru.get_sum(l, r + 1, l, r + 1)
    print(ans)

Submission status: Accepted

Solution code:
class Ruiseki2D:
    """二次元累積和を構築する"""
    def __init__(self, matrix):
        self.h = len(matrix)
        self.w = len(matrix[0])
        self.ru = [[0] * (self.w + 1) for _ in range(self.h + 1)]

        for i in range(self.h):
            for j in range(self.w):
                self.ru[i + 1][j + 1] = self.ru[i + 1][j] + matrix[i][j]
        for i in range(self.h):
            for j in range(self.w):
                self.ru[i + 1][j + 1] += self.ru[i][j + 1]

    def get_sum(self, hl, hr, wl, wr):
        """[hl, hr), [wl, wr) で囲まれた部分の和を求める"""
        return (self.ru[hr][wr] + self.ru[hl][wl]
                - self.ru[hr][wl] - self.ru[hl][wr])


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

matrix = [[0] * (n + 1) for i in range(n + 1)]
for l, r in info:
    matrix[l][r] += 1
ru = Ruiseki2D(matrix)

for l, r in query:
    ans = ru.get_sum(l, r + 1, l, r + 1)
    print(ans)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M,Q = LI()
city = [[0] * (N+1) for _ in range(N+1)]
for _ in range(M):
    l,r = LI()
    city[l][r] += 1

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

for _ in range(Q):
    p,q = LI()
    ans = city[q][q] - city[q][p-1] - city[p-1][q] + city[p-1][p-1]
    print (ans)

Submission status: Accepted

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

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

smat=[[0]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
  for j in range(1,N+1):
    smat[i][j]=xmat[i][j]+smat[i][j-1]+smat[i-1][j]-smat[i-1][j-1]
#print(smat)

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

Submission status: Accepted

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

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

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




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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import numpy as np
N,M,Q = (int(x) for x in input().split())
route = np.zeros((N,N))
for i in range(M):
    L,R = (int(x) for x in input().split())
    route[L-1][R-1] += 1
cs1 = np.cumsum(route,axis=1)
cs2 = np.cumsum(cs1,axis=0)
for i in range(Q):
    p,q = (int(x) for x in input().split())
    if p == 1:
        print(int(cs2[q-1][q-1]))
    else:
        print(int(cs2[q-1][q-1]-cs2[p-2][q-1]))

Submission status: Accepted

Solution code:

import numpy as np

def resolve():
    N, M, Q = map(int, input().split())
    L, R = np.array([list(map(int, input().split())) for _ in range(M)]).T
    P, Q = np.array([list(map(int, input().split())) for _ in range(Q)]).T
    P -= 1
    S = np.zeros(((N + 1), (N + 1)))

    # L,Rの区間にある本数
    np.add.at(S, (L,R), 1)

    # ゼータ変換（横縦累積和） axis=1:横, axis=0:縦
    S = np.cumsum(S, axis=1).cumsum(axis=0)

    ans = S[P, P] - S[P, Q] - S[Q, P] + S[Q, Q]
    print(*ans.astype(int), sep="\n")

if __name__ == "__main__":
    resolve()