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 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)] for _ in range(n)]
ruisekiwa = [[0 for _ in range(n)] for _ in range(n)]
# O(nm)
# for p, q in query:
#     cnt = 0
#     for left, right in train:
#         if p <= left and right <= q:
#             cnt += 1
#     print(cnt)
for left, right in train:
    table[left-1][right-1] += 1

# pprint(table, width=40)

for i in range(n):
    for j in range(n):
        ruisekiwa[i][j] = table[i][j]
        if i > 0:
            ruisekiwa[i][j] += ruisekiwa[i-1][j]
        if j > 0:
            ruisekiwa[i][j] += ruisekiwa[i][j-1]
        if i > 0 and j > 0:
            ruisekiwa[i][j] -= ruisekiwa[i-1][j-1]

# pprint(ruisekiwa, width=40)
for p, q in query:
    ans = ruisekiwa[q-1][q-1]
    if p-1 > 0:
        ans -= ruisekiwa[p-2][q-1]
        ans -= ruisekiwa[q-1][p-2]
        ans += ruisekiwa[p-2][p-2]
    print(ans)

Submission status: Accepted

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


def main():
    n, m, q = map(int, input().split())
    summed = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for _ in range(m):
        li, ri = map(int, input().split())
        summed[li][ri] += 1

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

    for _ in range(q):
        pi, qi = map(int, input().split())
        count = summed[qi][qi] - summed[pi - 1][qi] - summed[qi][pi - 1] + summed[pi - 1][pi - 1]
        print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    n, m, q = map(int, input().split())
    summed = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for _ in range(m):
        li, ri = map(int, input().split())
        summed[li][ri] += 1

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

    ans = list()

    for _ in range(q):
        pi, qi = map(int, input().split())
        count = summed[qi][qi] - summed[pi - 1][qi] - summed[qi][pi - 1] + summed[pi - 1][pi - 1]
        ans.append(count)

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

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


def main():
    n, m, q = map(int, input().split())
    lr = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    c = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

    for _ in range(m):
        li, ri = map(int, input().split())
        lr[li][ri] += 1

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

    ans = list()

    for _ in range(q):
        pi, qi = map(int, input().split())
        count = 0

        for i in range(pi, qi + 1):
            count += c[i][qi] - c[i][pi - 1]

        ans.append(count)

    print('\n'.join(map(str, ans)))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

n, m, q = map(int, input().split())
rails = [[0] * n for _ in range(n)]
for _ in range(m):
    l, r = map(int, input().split())
    rails[l - 1][r - 1] += 1
rails = [list(accumulate(s)) for s in rails]
rails = [list(reversed(list(accumulate(reversed(s))))) for s in zip(*rails)]

buf = []
for _ in range(q):
    p, q = map(int, input().split())
    buf.append(rails[q-1][p-1])
print('\n'.join(map(str,buf)))

Submission status: Accepted

Solution code:
#二次元累積和
#https://tqk.hatenablog.jp/entry/ABC106-2
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)]
train = [[0] * (N + 1) for _ in range(N + 1)]
for L,R in LR:
    train[L][R] += 1
for l in range(1,N+1):
    for r in range(1,N+1):
        train[l][r] += (train[l-1][r] + train[l][r-1] - train[l-1][r-1])
for p, q in pq:
    print(train[q][q]-train[q][p-1]-train[p-1][q]+train[p-1][p-1])

Submission status: Accepted

Solution code:
n, m, q = list(map(int, input().split()))
lr = [[0 for i in range(501)] for i in range(501)]
for i in range(m):
  lt, rt = list(map(int, input().split()))
  lr[lt][rt] += 1
for i in range(1, 501):
  for j in range(1, 501):
    lr[i][j] += lr[i][j-1]
for i in range(q):
  lt, rt = list(map(int, input().split()))
  ans = 0
  for j in range(lt, rt+1):
    ans += lr[j][rt]-lr[j][j-1]
  print(ans)

Submission status: Accepted

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

table = [[0 for _ in range(N + 2)] for _ in range(N + 2)]

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

#for line in table:
#	print(*line)
#print()

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

#for line in table:
#	print(*line)
#print()

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
from collections import deque  # 双方向キュー
from collections import defaultdict  # 初期化済み辞書
from heapq import heapify, heappush, heappop, heappushpop  # プライオリティキュー
from bisect import bisect_left, bisect_right  # 二分探索
#import numpy as np  # 1.8.2
#import scipy  # 0.13.3
#sys.setrecursionlimit(int(1e+6))
s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in ss]
ss2nnn = lambda ss: [s2nn(s) for s in ss]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline().rstrip() for _ in range(n)]
ii2nn = lambda n: ss2nn(ii2ss(n))
ii2nnn = lambda n: ss2nnn(ii2ss(n))
MOD = int(1e+9) + 7

def main():
    N, M, Q = i2nn()
    LR = ii2nnn(M)
    PQ = ii2nnn(Q)
    D = [[0] * (N+2) for i in range(N+2)]
    for l, r in LR:
        D[l][r] += 1
    for i in range(N, 0, -1):
        for j in range(1, N+1):
            D[i][j] += D[i+1][j] + D[i][j-1] - D[i+1][j-1]
    for p, q in PQ:
        print(D[p][q])

main()

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
LR=[list(map(lambda x:int(x)-1,input().split())) for i in range(M)]
pq=[list(map(lambda x:int(x)-1,input().split())) for i in range(Q)]
_list=[[0 for _ in range(N)] for i in range(N)]
for i in range(M):
    _list[LR[i][0]][LR[i][1]]+=1
for i in range(N):
    for j in range(N-1):
        _list[i][j+1]+=_list[i][j]
for i in range(N):
    for j in range(N-1,0,-1):
        _list[j-1][i]+=_list[j][i]
for i in range(Q):
    print(_list[pq[i][0]][pq[i][1]])

Submission status: Accepted

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

S = [[0]*501 for i in range(501)]

for i in range(500):
    s=0
    for j in range(500):
        s+=Map[i][j]
        S[i+1][j+1]=S[i][j+1]+s

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

Submission status: Accepted

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

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):
    L,R=map(int,input().split())
    a[1][R]+=1
    a[L+1][R]-=1
a=np.cumsum(a, axis=1)
a=np.cumsum(a, axis=0)
for i in range(q):
    L,R=map(int,input().split())
    print(int(a[L][R]))

Submission status: Accepted

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

class Cell:
    def __init__(self):
        self.value = 0
        self.L = 0
    def __repr__(self):
        return str((self.value, self.L))

pairs = [[Cell() for _ in range(N+1)] for _ in range(N+1)]
for L, R in (map(int, input().split()) for _ in range(M)):
    cell = pairs[L][R]
    cell.value += 1
    cell.L = cell.value

for i in range(N-1, 0, -1):
    for j in range(i+1, N+1):
        cell = pairs[i][j]
        cell.L += pairs[i][j-1].L
        cell.value = cell.L + pairs[i+1][j].value
for p, q in (map(int, input().split()) for _ in range(Q)):
    print(pairs[p][q].value)

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]


def solve1():
    table = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        table[l][r] += 1
    # for row in table:
    #     print(row)
    # print("---------")
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = table[i][j - 1] + table[i][j]
    # for row in table:
    #     print(row)
    for p, q in pq_array:
        res = 0
        for i in range(p, q + 1):
            # print(i)
            res += table[i][q]
        print(res)

    return 0


# 横軸：スタート
# 縦軸：ゴール
# 2次元累積和で解く
def solve2():
    table = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        table[l][r] += 1
    # for row in table:
    #     print(row)
    # print("---------")

    # 横方向の累積和
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = table[i][j - 1] + table[i][j]

    # 縦方向の累積和
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = table[i - 1][j] + table[i][j]

    # for row in table:
    #     print(row)

    # p=1, q=8の場合、
    # 「スタートが8でゴールが8の場合のすべての本数」から「スタートが1の場合の
    for p, q in pq_array:
        print(table[q][q] + table[p-1][p-1] - table[q][p-1] - table[p-1][q])


if __name__ == '__main__':
    # solve1()
    solve2()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
try:
    from math import gcd
except Exception:
    from fractions import gcd


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

    for i in range(0, N):
        for j in range(0, N):
            dp[i][j] += dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]
    ret = []
    for pp, qq in zip(p, q):
        c = dp[qq-1][qq-1] - dp[pp - 2][qq - 1] - dp[qq - 1][pp - 2] + dp[pp - 2][pp - 2]
        ret.append(c)

    return '\n'.join([str(r) for r in ret])


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))
    result = solve(N, M, Q, L, R, p, q)
    print(result)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from functools import partial
from itertools import islice, accumulate


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


def solve(s):
    n, m, q, *lrpq = map(int, s.split())
    lr, pq = lrpq[:2 * m], lrpq[2 * m:]
    t = [[0] * (n + 1) for _ in range(n + 1)]
    for l, r in chunked(lr, 2):
        t[l][r] += 1
    t = [list(accumulate(_t)) for _t in zip(*(accumulate(_t) for _t in t))]
    return "\n".join(
        [str(t[q][q] - t[q][p - 1] - t[p - 1][q] + t[p - 1][p - 1]) for p, q in chunked(pq, 2)])


if __name__ == "__main__":
    n, m, q = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, q) + '\n'.join([input() for _ in range(m + q)])))

Submission status: Accepted

Solution code:
from functools import partial
from itertools import islice, accumulate


def take(n, iterable):
    return list(islice(iterable, n))


def chunked(iterable, n):
    return iter(partial(take, n, iter(iterable)), [])


def solve(s):
    n, m, q, *lrpq = map(int, s.split())
    lr, pq = lrpq[:2 * m], lrpq[2 * m:]
    t = [[0] * (n + 1) for _ in range(n + 1)]
    for l, r in chunked(lr, 2):
        t[l][r] += 1
    t = [list(accumulate(_t)) for _t in zip(*(accumulate(_t) for _t in t))]
    return "\n".join(
        [str(t[q][q] - t[p - 1][q] - t[q][p - 1] + t[p - 1][p - 1]) for p, q in chunked(pq, 2)])


n, m, q = map(int, input().split())
print(solve('{} {} {}\n'.format(n, m, q) + '\n'.join([input() for _ in range(m + q)])))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline

N, M, Q = map(int, input().split())
t = [[0] * (N + 1) for _ in range(N + 1)]
# es[L][R]:=区間[L,R]を走る列車の本数

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

for L in range(1, N + 1):
    for R in range(1, N + 1):
        t[L][R] += t[L - 1][R]
        t[L][R] += t[L][R - 1]
        t[L][R] -= t[L - 1][R - 1]
        # 累積和のテーブルを作る
        # 最終的には
        # t[L][R]には区間が[L,R]に含まれる本数を入れるが、
        # 現時点では区間が[L,R]に一致する本数しか入っていない
        # ここに区間が[L-1,R]に含まれる本数と
        # 区間が[L,R-1]に含まれる本数を足すと
        # 区間が[L,R]に含まれる範囲をカバーできるが、
        # 区間が[L-1][R-1]の範囲が重複して足されている

for _ in range(Q):
    p, q = map(int, input().split())
    print(t[q][q] - t[p - 1][q] - t[q][p - 1] + t[p - 1][p - 1])
    # 2次元累積和

Submission status: Accepted

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

n, m, Q = map(int,input().split())
lr = [[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

# 二次元累積和(indexに注意)
s = [[0 for i in range(n+1)] for j in range(n+1)]
# s[x][y]:=[0,x-1]×[0,y-1]の長方形区間の総和
for i in range(n):
    for j in range(n):
        s[i+1][j+1] = s[i+1][j] + s[i][j+1] -s[i][j] + lr[i+1][j+1]

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

# 72

Submission status: Accepted

Solution code:
n, m, Q = map(int,input().split())
lr = [[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

# 二次元累積和(indexに注意)
s = [[0 for i in range(n+1)] for j in range(n+1)]
# s[x][y]:=[0,x-1]×[0,y-1]の長方形区間の総和
for i in range(n):
    for j in range(n):
        s[i+1][j+1] = s[i+1][j] + s[i][j+1] -s[i][j] + lr[i+1][j+1]

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

# 72

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
 
def main():
	N, M, Q = map(int, input().split(" "))
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for _ in range(M):
		l, r = map(int, input().split(" "))
		l -= 1
		r -= 1
		N_list[l][r] += 1
		
	#print(N_list)
	
	for i in range(N):
		for j in range(N):
			if i == 0 and j == 0:
				continue
			if i == 0:
				N_list[i][j] = N_list[i][j] + N_list[i][j-1]
				continue
			if j == 0:
				N_list[i][j] = N_list[i][j] + N_list[i-1][j]
				continue
			N_list[i][j] = N_list[i][j] + N_list[i-1][j] + N_list[i][j-1] - N_list[i-1][j-1]
			
	#print(N_list)
		
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		
		a = 0
		b = 0
		c = 0
		if p != 0:
			a = N_list[q][p-1]
			b = N_list[p-1][q]
			c = N_list[p-1][p-1]
		ans = N_list[q][q] - a - b + c
		print(ans)
		
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M, Q = map(int, input().split(" "))
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for _ in range(M):
		l, r = map(int, input().split(" "))
		l -= 1
		r -= 1
		N_list[l][r] += 1
		
	#print(N_list)
	
	for i in range(N):
		for j in range(N):
			if i == 0 and j == 0:
				continue
			if i == 0:
				N_list[i][j] = N_list[i][j] + N_list[i][j-1]
				continue
			if j == 0:
				N_list[i][j] = N_list[i][j] + N_list[i-1][j]
				continue
			N_list[i][j] = N_list[i][j] + N_list[i-1][j] + N_list[i][j-1] - N_list[i-1][j-1]
			
	#print(N_list)
		
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		
		a = 0
		b = 0
		c = 0
		if p != 0:
			a = N_list[q][p-1]
			b = N_list[p-1][q]
			c = N_list[p-1][p-1]
		ans = N_list[q][q] - a - b + c
		print(ans)
		
	
if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(1000000)

N,M,Q = [int(x) for x in input().split()]
lr = [[int(x) for x in input().split()]for _ in range(M)]
pq = [[int(x) for x in input().split()]for _ in range(Q)]

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

for i in lr:
    dp[i[0]][i[1]]+=1

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

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

for i in pq:
    print(dp[i[0]][i[1]])

Submission status: Accepted

Solution code:

from collections import defaultdict


def main():
    num_city, num_tarin, num_q = map(int, input().split())
    data = [list(map(int, input().split())) for i in range(num_tarin)]
    dp = [[0 for i in range(num_city)] for j in range(num_city)]
    for i in range(num_tarin):
        x, y = data[i]
        dp[x- 1][y - 1] += 1
    # print(dp)
    for i in range(num_city):
        for j in range(max(1, i), num_city):
            dp[i][j] += dp[i][j - 1]

    # print(dp)

    for i in range(num_q):
        x, y = map(int, input().split())
        kari = 0
        for j in range(x, y + 1):
            kari += dp[j - 1][y - 1]
        print(kari)




if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
n,m,qq = map(int,input().split())
PQ = []
LR = [[_+1,0]+list(map(int,input().split())) for _ in range(m)]

for i in range(qq):
    p,q = map(int,input().split())
    PQ.append([i+1,1,p,q+0.1])
record = [0]*(n+1)
Ans = []

All = LR+PQ
from operator import itemgetter
All.sort(key = itemgetter(3))

for num,flag ,l, r in All:
    if flag :
        Ans.append([num,sum(record[l:int(r+1)])])
    else:
        record[l] += 1
Ans.sort(key = itemgetter(0))
for ans in Ans:
    print(ans[1])

Submission status: Accepted

Solution code:
# count p<=x<=q and p<=y <=q
# 長方形に含まれる格子点の数
import numpy as np
N,M,Q = map(int,input().split())

cnt = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
  x,y = map(int,input().split())
  cnt[x][y] += 1

# cumsumだけnumpyを使って、添字アクセスするときはlistの方が速い
cnt = np.cumsum(cnt,axis=0).cumsum(axis=1).tolist()

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

Submission status: Accepted

Solution code:
# count p<=x<=q and p<=y <=q
# 長方形に含まれる格子点の数
import numpy as np
N,M,Q = map(int,input().split())

cnt = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
  x,y = map(int,input().split())
  cnt[x][y] += 1

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

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

Submission status: Accepted

Solution code:
# count p<=x<=q and p<=y <=q
# 長方形に含まれる格子点の数
import numpy as np
N,M,Q = map(int,input().split())

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

cnt = cnt.cumsum(axis=0).cumsum(axis=1)

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

Submission status: Accepted

Solution code:
N,M,Q = [ int(it) for it in input().split() ]
lit = [ [ int(it)-1 for it in input().split() ] for i in range(M) ]
liq = [ [ int(it)-1 for it in input().split() ] for i in range(Q) ]

li = [[0]*(N+1) for i in range(N+1)]
for p,q in lit:
  li[p+1][q+1]+=1

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

for p,q in liq:
  s = 0
  for i in range(p+1,N+1):
    s += li[i][q+1]
  print  (s)

Submission status: Accepted

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

train = [[0 for i in range(N+1)] for j in range(N+1)]
for m in range(M):
    L,R = map(int,input().split())
    train[L][R] += 1

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

for x 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:
import sys
input = sys.stdin.readline
n,m,Q=map(int,input().split())
L=[[0 for i in range(n)] for i in range(n)]
LL=[[0 for i in range(n)] for i in range(n)] 
for i in range(m):
  l,r=map(int,input().split())
  L[l-1][r-1]+=1
LL[0][0]=L[0][0]
for i in range(1,n):
  LL[i][0]=LL[i-1][0]+L[i][0]
  LL[0][i]=LL[0][i-1]+L[0][i]
for i in range(1,n):
  for j in range(1,n):
    LL[i][j]=LL[i-1][j]+LL[i][j-1]+L[i][j]-LL[i-1][j-1]
for i in range(Q):
  p,q=map(int,input().split())
  if p==1:
    ans=LL[q-1][q-1]
  elif q==1:
    ans=LL[0][0]
  else:
    ans=LL[q-1][q-1]-LL[q-1][p-2]-LL[p-2][q-1]+LL[p-2][p-2]
  print(ans)

Submission status: Accepted

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

s = a[:]

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

for l in range(1,n+1):
  for r in range(1,n+1):
    s[l][r] = a[l][r] + s[l-1][r] + s[l][r-1] - s[l-1][r-1]

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
D - AtCoder Express 2
https://atcoder.jp/contests/abc106/tasks/abc106_d

"""
import sys


def solve(N, M, Q, lines, queries):
    dp = [[0]*(N+1) for _ in range(N+1)]
    for f, t in lines:
        dp[f][t] += 1
    for f in range(N-1, 0, -1):
        for t in range(f, N+1):
            dp[f][t] += (dp[f][t-1] + dp[f+1][t] - dp[f+1][t-1])
    for f, t in queries:
        print(dp[f][t])


def main(args):
    N, M, Q = map(int, input().split())
    lines = [[int(i) for i in input().split()] for _ in range(M)]
    queries = [[int(i) for i in input().split()] for _ in range(Q)]
    solve(N, M, Q, lines, queries)


if __name__ == '__main__':
    main(sys.argv[1:])

Submission status: Accepted

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

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

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

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

for e in range(1, N):  # endのe
    for s in reversed(range(N)):  # startのs
        if s == e:
            ans[e][s] = trains[e][s]
        else:
            ans[e][s] = sum(trains[e][s:]) + ans[e-1][s]


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

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)