Problem:


Score: 400 points

Problem Statement

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

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

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

Constraints

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

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 1
1 1
1 2
2 2
1 2

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

1
1

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

Sample Input 3

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

Sample Output 3

7
9
10
6
8
9
6
7
8
10



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


Sample output:
3

Submission status: Accepted

Solution code:
import sys

readline = sys.stdin.buffer.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    n, m, q = map(int, readline().split())
    cum = [[0] * 502 for _ in range(502)]

    for _ in range(m):
        l, r = map(int, readline().split())
        cum[l][r] += 1

    ans = [[0] * 502 for _ in range(502)]

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

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

    for _ in range(q):
        l, r = map(int, readline().split())
        print(ans[l][r])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def train_map(LR,N):
    train = [[0 for _ in range(N+1)] for _ in range(N+1)]
    #train[i][j]:ちょうど区間iからjを走る電車の本数（後に累積和に）
    for l,r in LR:
        train[l][r] += 1

    #累積和
    for i in range(N+1):
        for j in range(1,N+1):
            train[i][j] += train[i][j-1]
    for j in range(N+1):
        for i in reversed(range(1,N+1)):
            train[i-1][j] += train[i][j]

    return train

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

    train = train_map(LR,N)

    for p,q in pq:
        print(train[p][q])

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
#N 500 に合わせて少し余分に準備
p = [[0] * 510 for i in range(510)]

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

#1 ~ N にすることで周囲に空白を用意
for i in range(1, N + 1):
  for j in range(1, N + 1):
    p[i][j] += p[i][j - 1]
#print(p)
#print("")

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

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

Submission status: Accepted

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
table = [[0] * N for _ in range(N)]
for _ in range(M):
    L, R = map(lambda n: int(n) - 1, input().split())
    table[R][- L - 1] += 1
table = np.array(table, dtype=np.int64).cumsum(axis=0).cumsum(axis=1).tolist()
for _ in range(Q):
    p, q = map(lambda n: int(n) - 1, input().split())
    print(table[q][- p - 1])

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

matrix = [[0] * N for _ in range(N)]
for l, r in lr:
    l, r = l-1, r-1
    matrix[l][r] += 1

matrix2 = [[0] * N for _ in range(N)]
for i in range(N):
    for j in range(N):
        if j == 0:
            matrix2[i][j] = matrix[i][j]
        else:
            matrix2[i][j] = matrix2[i][j-1] + matrix[i][j]

for p, q in pq:
    p, q = p-1, q-1
    count = 0
    for x in range(p, q + 1):
        count += matrix2[x][q]
    print(count)

Submission status: Accepted

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

# i 以下に一切含まれていない数 つまり、l以下
# l_list = {}

# # i 以下に全て含まれている数 つまり、r以上
# r_list = {}
# L = []
# R = []
X = [[0]*N for _ in range(N)]

for i in range(M):
    l, r = map(int, input().split())
    X[l-1][r-1] += 1
    # L.append(l)
    # R.append(r)

C = [[0]*N for i in range(N)]

for i in range(N):
    for j in range(N):
        if j == 0:
            C[i][j] = X[i][j]
        else:
            C[i][j] = C[i][j-1] + X[i][j]

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

for p,q in check:
    ans = 0
    for i in range(p-1,q):
        if p-2 < 0:
            ans += C[i][q-1]
        else:
            ans += C[i][q-1] - C[i][p-2]

    print(ans)

Submission status: Accepted

Solution code:
import sys
import numpy as np

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

dp = np.zeros(shape=(N + 1, N + 1), dtype=int)
for _ in range(M):
    L, R = map(int, input().split(' '))
    dp[L][R] += 1

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

queries = np.array(list(map(int, sys.stdin.read().split())))

left = queries[0::2] - 1
right = queries[1::2]

print('\n'.join((dp[right, right] + dp[left, left] - dp[left, right] - dp[right, left]).astype(str)))

Submission status: Accepted

Solution code:
import numpy as np
n,m,q = [int(i) for i in input().split()]

trains = np.zeros([n+1,n+1],dtype = np.int32)

l,r = np.split(np.array([input().split() for _ in range(m)],dtype = np.int32),2,1)
p,q = np.split(np.array([input().split() for _ in range(q)],dtype = np.int32),2,1)


np.add.at(trains,(l,r),1)
ans_arr = np.cumsum(np.cumsum(trains,axis = 0),axis = 1)

p -= 1
ans = ans_arr[q,q] - ans_arr[p,q] - ans_arr[q,p] + ans_arr[p,p]
print('\n'.join(ans.astype(str).flatten()))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d

# MAX_N = 505
n, m, q = map(int, input().split())
X = [[0] * (n + 1) for _ in range(n + 1)]
C = [[0] * (n + 1) for _ in range(n + 1)]
count = [0] * (n + 1)
for _ in range(m):
    li, ri = map(int, input().split())
    X[li][ri] += 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        C[i][j] = C[i][j - 1] + X[i][j]

for _ in range(q):
    p, q = map(int, input().split())
    sum_k = 0
    for j in range(p, q + 1):
        sum_k += C[j][q] - C[j][p - 1]
    print(sum_k)

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
def main():
    #入力
    readline=stdin.readline
    n,m,q=map(int,readline().split())
    table=np.array([[0]*n for _ in range(n)],dtype="int64")
    for i in range(m):
        l,r=map(lambda x:int(x)-1,readline().split())
        table[l][r]+=1

    #累積和
    for i in range(n):
        table[i]=table[i].cumsum()

    ans=[0]*q
    for i in range(q):
        l,r=map(lambda x:int(x)-1,readline().split())
        ans[i]=table[l:r+1,r].sum()

    for i in range(q):
        print(ans[i])

if __name__=="__main__":
    main()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 8)

def Z(): return int(input())
def ZZ(): return [int(_) for _ in input().split()]

def main():
    N, M, Q = ZZ()
    lr = sorted([ZZ() for _ in range(M)])
    query = [ZZ() for _ in range(Q)]
    p = [[0] * (N+1) for _ in range(N+1)]
    for l, r in lr: p[l][r] += 1
    for i in range(1, N+1)[::-1]:
        for j in range(1, N+1):
            if j+1 <= N: p[i][j+1] += p[i][j]
            if 0 <= i-1: p[i-1][j] += p[i][j]
            if j+1 <= N and 0 <= i-1: p[i-1][j+1] -= p[i][j]
    for a, b in query: print(p[a][b])

    return

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from sys import stdin
import numpy as np
N,M,Q = [int(x) for x in stdin.readline().rstrip().split()]

cumsum_2d = np.zeros([N+1,N+1]) 
for i in range(M):
    L,R = [int(x) for x in stdin.readline().rstrip().split()]
    cumsum_2d[L,R] += 1
    
np.cumsum(cumsum_2d,axis=0,out=cumsum_2d)
np.cumsum(cumsum_2d,axis=1,out=cumsum_2d)
    
for i in range(Q):
    p,q = [int(x) for x in stdin.readline().rstrip().split()]
    ans = cumsum_2d[q,q] - cumsum_2d[q,p-1] - cumsum_2d[p-1,q] + cumsum_2d[p-1,p-1]
    print(int(ans))

Submission status: Accepted

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
table = [[0] * N for _ in range(N)]
for _ in range(M):
    L, R = map(lambda n: int(n) - 1, input().split())
    table[L][R] += 1
table = np.rot90(np.rot90(table, k=-1).cumsum(axis=0).cumsum(axis=1), k=1).tolist()
for _ in range(Q):
    p, q = map(lambda n: int(n) - 1, input().split())
    print(table[p][q])

Submission status: Accepted

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
table = np.zeros((N, N), np.int64)
for _ in range(M):
    L, R = map(lambda n: int(n) - 1, input().split())
    table[L][R] += 1
table = np.rot90(np.rot90(table, k=-1).cumsum(axis=0).cumsum(axis=1), k=1).tolist()
for _ in range(Q):
    p, q = map(lambda n: int(n) - 1, input().split())
    print(table[p][q])

Submission status: Accepted

Solution code:
class segment_():
    def __init__(self,n,ide_ele,segfunc):
        self.ide_ele = ide_ele
        self.num = 1 << n.bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc

    def update1(self, k):
        k += self.num
        self.seg[k] += 1
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

    def query(self, p, q):
        if q < p:
            return self.ide_ele
        p += self.num;
        q += self.num
        res = self.ide_ele
        while p < q:
            if p & 1 == 1:
                res = self.segfunc(res, self.seg[p])
                p += 1
            if q & 1 == 1:
                q -= 1
                res = self.segfunc(res, self.seg[q])
            p >>= 1;
            q >>= 1
        return res

def main():
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  from operator import itemgetter

  N,M,Q = map(int,readline().split())
  S = segment_(N,0,lambda a, b: a+b)
  chk = []
  for i in range(M):
    L,R = map(int,readline().split())
    chk.append((1,L,R,i))
  for i in range(Q):
    l,r = map(int,readline().split())
    chk.append((2,l,r,i))

  chk.sort(key=itemgetter(2))
  ans = [0]*Q
  for a,l,r,i in chk:
    if a == 1:
      S.update1(l)
    else:
      ans[i] = S.query(l,r+1)

  print(*ans,sep='\n')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class segment_():
    def __init__(self,n,ide_ele,segfunc):
        self.ide_ele = ide_ele
        self.num = 1 << n.bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc

    def update1(self, k):
        k += self.num
        self.seg[k] += 1
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

    def query(self, p, q):
        if q < p:
            return self.ide_ele
        p += self.num;
        q += self.num
        res = self.ide_ele
        while p < q:
            if p & 1 == 1:
                res = self.segfunc(res, self.seg[p])
                p += 1
            if q & 1 == 1:
                q -= 1
                res = self.segfunc(res, self.seg[q])
            p >>= 1;
            q >>= 1
        return res
      
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter

N,M,Q = map(int,readline().split())
S = segment_(N,0,lambda a, b: a+b)
chk = []
for i in range(M):
  L,R = map(int,readline().split())
  chk.append((1,L,R,i))
for i in range(Q):
  l,r = map(int,readline().split())
  chk.append((2,l,r,i))
  
chk.sort(key=itemgetter(2))
ans = [0]*Q
for a,l,r,i in chk:
  if a == 1:
    S.update1(l)
  else:
    ans[i] = S.query(l,r+1)
    
for i in ans:
  print(i)

Submission status: Accepted

Solution code:
# 一点更新、区間取得
class segment_():
    def __init__(self,n,ide_ele,segfunc):
        #####単位元######要設定0or1orinf
        self.ide_ele = ide_ele
        ####################
        self.num = 1 << n.bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc

    def update(self, k, r):
        k += self.num
        self.seg[k] = r
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

    # 値xに1加算
    def update1(self, k):
        k += self.num
        self.seg[k] += 1
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

    def updateneg1(self, k):
        k += self.num
        self.seg[k] -= 1
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

    def query(self, p, q):
        # qは含まない
        if q < p:
            return self.ide_ele
        p += self.num;
        q += self.num
        res = self.ide_ele
        while p < q:
            if p & 1 == 1:
                res = self.segfunc(res, self.seg[p])
                p += 1
            if q & 1 == 1:
                q -= 1
                res = self.segfunc(res, self.seg[q])
            p >>= 1;
            q >>= 1
        return res
      
import sys
input = sys.stdin.readline
from operator import itemgetter

N,M,Q = map(int,input().split())
S = segment_(N+1,0,lambda a, b: a+b)
chk = []
for i in range(M):
  L,R = map(int,input().split())
  chk.append((1,L,R,i))
for i in range(Q):
  l,r = map(int,input().split())
  chk.append((2,l,r,i))
  
chk.sort(key=itemgetter(2))
ans = [0]*Q
for a,l,r,i in chk:
  if a == 1:
    S.update1(l)
  else:
    ans[i] = S.query(l,r+1)
    
for i in ans:
  print(i)

Submission status: Accepted

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

ts = [[0] * (n+1) for _ in range(n+1)]
for _ in range(m):
    l, r = tuple(map(int, input().split()))
    ts[l][r] += 1
# 二次元累積和
for i in range(1, n+1):
    for j in range(1, n+1):
        ts[i][j] += ts[i][j-1]

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

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

Submission status: Accepted

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

Submission status: Accepted

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

import sys
sys.setrecursionlimit(300000)


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    ends = {}
    for i in range(M):
        s, e = L[i], R[i]
        if not e in ends:
            ends[e] = {}
        if not s in ends[e]:
            ends[e][s] = 0
        ends[e][s] += 1

    counts = [[0]]
    for i in range(1, N + 1):
        tmp = [v for v in counts[i - 1]]
        tmp.append(0)
        if i in ends:
            for s, cnt in ends[i].items():
                tmp[s] += cnt
        counts.append(tmp)
    #print(counts)

    for s, e in zip(p, q):
        ret = 0
        for j in range(s, e + 1):
            ret += counts[e][j]
        print(ret)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

    for _ in range(M):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        LR[0][r] += 1
        LR[l + 1][r] -= 1
    for r in range(N):
        t = 0
        for l in range(N):
            t += LR[l][r]
            LR[l][r] = t
    for l in range(N):
        t = 0
        for r in range(N):
            t += LR[l][r]
            LR[l][r] = t
    for _ in range(Q):
        p, q = map(int, input().split())
        p, q = p - 1, q - 1
        print(LR[p][q])
main()

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

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


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

Submission status: Accepted

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

trains = [[0 for _ in range(n+1)] for _ in range(n+1)]

for i in range(m):
    l, r = lr[i]
    trains[l][r] += 1

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

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

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

Submission status: Accepted

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

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


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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

for _ in range(M):
    left, right = map(int, input().split())
    areas[left][right] += 1
# print(areas)
for i in range(1, N + 2):
    for j in range(1, N + 2):
        areas[i][j] += areas[i][j - 1]
# print(areas)
for _ in range(Q):
    left, right = map(int, input().split())
    cost = 0
    for i in range(left, right + 1):
        cost += areas[i][right] - areas[i][left - 1]
    print(cost)

Submission status: Accepted

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

for _ in range(M):
    left, right = map(int, input().split())
    bord[left][right] += 1
# print(bord)
for i in range(1, N + 2):
    for j in range(1, N + 2):
        bord[i][j] += bord[i][j - 1]
# print(bord)
for _ in range(Q):
    left, right = map(int, input().split())
    cost = 0
    for i in range(left, right + 1):
        cost += bord[i][right] - bord[i][left - 1]
    print(cost)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

for _ in range(M):
    l, r = map(int, sys.stdin.readline().rstrip().split())
    a[l - 1][r - 1] += 1

da = da_generate(N, N, a)

for _ in range(Q):
    p, q = map(int, sys.stdin.readline().rstrip().split())
    p -= 1
    q -= 1
    print(da_calc(p, p, q, q))

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N,M,Q=map(int,input().split())
lst=[[0 for e in range(N+1)] for f in range(N+1)]
for i in range(M):
 L,R=map(int,input().split())
 for j in range(1,L+1):
  lst[j][R]+=1
for j in range(N):
 for i in range(N+1):
  lst[i][j+1]+=lst[i][j]
for i in range(Q):
 p,q=map(int,input().split())
 print(lst[p][q])

Submission status: Accepted

Solution code:
# ABC105D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n,m,q = map(int, input().split())
lr = [None] * m
qs = [None] * q

for i in range(m):
    lr[i] = tuple(map(lambda x: int(x)-1, input().split()))
    
t = [[0]*(n+1) for _ in range(n+1)]

for x,y in lr:
    t[y][x] += 1
    
for i in range(n):
    for j in range(i,n):
        t[j][j-i] += t[j-1][j-i] + t[j][j-i+1] - t[j-1][j-i+1]
        
ans = [None] * q
for i in range(q):
    l, r = tuple(map(lambda x: int(x)-1, input().split()))
    ans[i] = t[r][l]
write("\n".join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m,Q=mp()
grid=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    l,r=mp()
    for k in range(1,l+1):
        grid[k][r]+=1

for i in range(n):
    for k in range(n):
        grid[i][k+1]+=grid[i][k]



for i in range(Q):
    p,q=mp()
    print(grid[p][q])

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
import bisect
import collections
import functools
import heapq
import math
import sys
from collections import deque
from collections import defaultdict
input = sys.stdin.readline
MOD = 10**9+7

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

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
input = stdin.readline
N, M, Q = map(int, input().split())
D = [[0] * (N + 1) for i in range(N + 1)]
for _ in range(M):
    L, R = map(int, input().split())
    D[L][R] += 1
for i in range(N - 1, 0, -1):
    for j in range(i, N + 1):
        D[i][j] += D[i + 1][j]
for i in range(1, N + 1):
    D[i] = list(accumulate(D[i]))
for _ in range(Q):
    p, q = map(int, input().split())
    print(D[p][q])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
def input(): return sys.stdin.readline().rstrip()
def main():
    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)]
    dp=[[0]*(n+1) for _ in range(n+1)] #i(1-)以上j(1-)以下の間に完全に含まれる列車の本数
    for l,r in LR:
        dp[l][r]+=1
    for i in range(n+1):
        for j in range(n):
            dp[i][j+1]+=dp[i][j]
    for i in range(n-1,0,-1):
        for j in range(n+1):
            dp[i][j]+=dp[i+1][j]
    for p,q in PQ:
        print(dp[p][q])

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate

n,m,q = map(int,input().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]
lin = []

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

for i in range(n+1):
    lin += [list(accumulate(li[i]))]

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

Submission status: Accepted

Solution code:
import numpy as np

n,m,q = map(int,input().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]

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

li = np.array(li)
c = np.cumsum(li,axis=1).cumsum(axis=0).tolist()

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

Submission status: Accepted

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

# map(int, input().rstrip().split())

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

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

table = VVI(N+1, N+1)

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

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(Q):
  p, q = map(int, input().rstrip().split())
  print(table[p][q])

Submission status: Accepted

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

# map(int, input().rstrip().split())

def VI(N, init=0):
  return [init for _ in range(N)]
def VVI(N, M, init=0):
  return [[init for _ in range(M)] for _ in range(N)]

def VD(N, init=0.0):
  return [init for _ in range(N)]
def VVD(N, M, init=0.0):
  return [[init for _ in range(M)] for _ in range(N)]

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

table = VVI(N+1, N+1)

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

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


for i in range(Q):
  p, q = map(int, input().rstrip().split())
  ma = max(p, q)
  mi = min(p, q)
  print(table[ma][ma]-table[ma][mi-1]-table[mi-1][ma]+table[mi-1][mi-1])

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate

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

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

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

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

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