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/python3
# -*- coding:utf-8 -*-

import numpy

def main():
  n, m, q = map(int, input().split())
  counts = numpy.zeros((n, n), dtype=numpy.int)
  llr = [], []
  for _ in range(m):
    l, r = map(int, input().split())
    counts[l-1, r-1] += 1
  
  cusum = counts.cumsum(0).cumsum(1)
  for _ in range(q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    
    if p-1 < 0:
      print(cusum[q, q])
    else:
      print(cusum[q, q] - cusum[p-1, q] - cusum[q, p-1] + cusum[p-1, p-1])

if __name__=='__main__':
  main()

Submission status: Accepted

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


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

# 二次元累積和
table = np.array(table)
table = table.cumsum(axis=0).cumsum(axis=1)

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

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d
# 何も見ずにやり直してみる

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


class cumsum2d:  # 二次元累積和クラス pypyでも使えるよ
    def __init__(self, ls: list):
        '''
        2次元のリストを受け取る
        '''
        from itertools import product
        H = len(ls)
        W = len(ls[0])
        self.ls_accum = [[0] * (W + 1)]
        for l in ls:
            self.ls_accum.append([0] + l)

        # 縦に累積
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i - 1][j]
        # 横に累積
        for i, j in product(range(1, H + 1), range(1, W + 1)):
            self.ls_accum[i][j] += self.ls_accum[i][j - 1]

    def total(self, i1, j1, i2, j2):
        '''
        点(i1,j1),(i1,j2),(i2,j1),(i2,j2)の4点が成す四角の中の合計を取り出す
        ただし i1<=i2, j1<=j2
        ただし、i軸に関しては[i1,i2),j軸に関しては[j1,j2)の半開区間である
        '''
        return self.ls_accum[i2][j2] - self.ls_accum[i1][j2] \
            - self.ls_accum[i2][j1] + self.ls_accum[i1][j1]


N, M, Q = read_ints()

# 列車を二次元座標に代入
table = [[0] * N for _ in range(N)]  # 都市はそれぞれ-1扱い
for _ in range(M):
    L, R = read_ints()
    table[L - 1][R - 1] += 1

# 二次元累積和を取る
table = cumsum2d(table)

# クエリに答える
for _ in range(Q):
    p, q = read_ints()
    p -= 1
    q -= 1
    print(table.total(p, p, q + 1, q + 1))

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d
# 何も見ずにやり直してみる

import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline


def read_ints():
    return list(map(int, read().split()))


N, M, Q = read_ints()

# 列車を二次元座標に代入
table = [[0] * N for _ in range(N)]  # 都市はそれぞれ-1扱い
for _ in range(M):
    L, R = read_ints()
    table[L - 1][R - 1] += 1

# 二次元累積和を取る
import numpy as np
table_ = np.array(table)
table = np.zeros((N + 1, N + 1), dtype='int')
table[1:, 1:] = table_.cumsum(axis=0).cumsum(axis=1)
# print(table)

# クエリに答える
for _ in range(Q):
    p, q = read_ints()
    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())

xmat,cmat=[],[]
for i in range(N+1):
  xmat.append([0]*(N+1))
  cmat.append([0]*(N+1))

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

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()
from itertools import accumulate

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

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

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

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

for _ in range(Q):
    p,q = map(int, input().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 = [int(i) for i in input().split()]

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

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

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

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

Submission status: Accepted

Solution code:
#!python3

# input
N, M, Q = list(map(int, input().split()))
LR = [[0] * 501 for _ in range(501)]
for _ in range(M):
    l, r = list(map(int, input().split()))
    LR[l][r] += 1
pq = [list(map(int, input().split())) for _ in range(Q)]


def main():
    dp = [[0] * 501 for _ in range(501)]
    for i in range(1, 501):
        for j in range(1, 501):
            dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + LR[i][j]
    
    for p, q in pq:
        ans = dp[q][q] - dp[q][p-1] - dp[p-1][q] + dp[p-1][p-1]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def f(h,w,a):
    da = [[0]*(w+1)for _ in range(h+1)]
    da[0][0] = a[0][0]
    for i in range(1, w+1):
        da[0][i] = da[0][i-1] + a[0][i]
    for i in range(1, h+1):
        cnt_w = 0
        for j in range(w+1):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j] + cnt_w
    return da

def Calc(p,q,x,y, da):
    if p>x  or q>y:
        return 0
    if p==0 or 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[x][q-1] - da[p-1][y] + da[p-1][q-1]

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

d = f(N,N,t)
for _ in range(Q):
    p,q = map(int,input().split())
    print(Calc(p,p,q,q,d))

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
n,m,q = map(int,input().split())
ipt = sys.stdin.readlines()
rails = [[0]*n for _ in range(n)]
for line in ipt[:m]:
    l,r = map(int,line.split())
    rails[l-1][r-1] += 1
rails = [accumulate(s) for s in rails]
rails = [list(reversed(list(accumulate(reversed(s))))) for s in zip(*rails)]
buf = []
for  line in ipt[m:]:
    p,q = map(int,line.split())
    buf.append(rails[q-1][p-1])
print('\n'.join(map(str, buf)))

Submission status: Accepted

Solution code:
import numpy as np
N,M,Q = map(int,input().split())
grid = np.zeros((N+1,N+1))
for _ in range(M):
    l,r = map(int,input().split())
    grid[l,r] += 1

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

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

Submission status: Accepted

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip()

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

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

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

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


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

Submission status: Accepted

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

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

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

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

for i in range(Q):
    L, R = map(int, input().split())
    ans = sum[R][R]
    ans -= sum[R][L - 1]
    ans -= sum[L - 1][R]
    ans += sum[L - 1][L - 1]
    print(ans)

Submission status: Accepted

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

n, m, Q = [int(x) for x in input().split()]

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

for _ in range(m):
    l, r = [int(x) for x in input().split()]
    table[l][r] += 1
# print(table)

# l固定で累積和
for i in range(1, n + 1):
    for j in range(1, n + 1):
        table[i][j] += table[i][j - 1]

for _ in range(Q):
    p, q = [int(x) for x in input().split()]
    res = 0
    for i in range(p, n + 1):
        res += table[i][q]
    print(res)

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
a=[[0]*n for _ in range(n)]
for _ in range(m):
  l,r=map(int,input().split())
  l-=1
  r-=1
  a[l][r]+=1
#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]
da=da_generate(n,n,a)
for _ in range(q):
  p,q=map(int,input().split())
  p-=1
  q-=1
  print(da_calc(p,p,q,q))

Submission status: Accepted

Solution code:
def main():
    N, M, Q, *X = map(int, open(0).read().split())
    L = [0]*M
    R = [0]*M
    p = [0]*Q
    q = [0]*Q
    for i in range(M):
        L[i], R[i] = X[2*i], X[2*i + 1]
    for i in range(Q):
        p[i], q[i] = X[2*M + 2*i], X[2*M + 2*i + 1]
    # print(N, M, Q, L, R, p, q)
    S = [[0]*(N+1) for i in range(N+1)]
    for i in range(M):
        S[L[i]][R[i]] += 1
    # for s in S:
    #     print(s)
    S2 = [[0]*(N+1) for i in range(N+1)]
    for i in range(N+1):
        S2[i][0] = S[i][0]
        for j in range(1, N+1):
            S2[i][j] = S2[i][j-1] + S[i][j]
    # for s in S2:
    #     print(s)
    S3 = [[0]*(N+1) for i in range(N+1)]
    for i in range(N+1):
        S3[0][i] = S2[0][i]
        for j in range(1, N+1):
            S3[j][i] = S3[j-1][i] + S2[j][i]
    for i in range(Q):
        pi, qi = p[i], q[i]
        ans = S3[qi][qi] - S3[qi][pi-1]
        ans -= S3[pi-1][qi] - S3[pi-1][pi-1]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

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

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

for i in range(Q):
  L,R=map(int,input().split())
  ans=A[R][R]-A[L-1][R]-A[R][L-1]+A[L-1][L-1]
  print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
L,R=[],[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i][j-1]
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i-1][j]
for i in range(Q):
  ans=c[Ql[i]][Ql[i]]-c[Pl[i]-1][Ql[i]]-c[Ql[i]][Pl[i]-1]+c[Pl[i]-1][Pl[i]-1]
  print(ans)

Submission status: Accepted

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

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    n,m,q = LI()
    a = [[0]*n for i in range(n)]
    for _ in range(m):
        l,r = LI()
        l -= 1
        r -= 1
        a[l][r] += 1
    for i in range(n):
        for j in range(n-1):
            a[i][j+1] += a[i][j]
    for j in range(n):
        for i in range(n-1)[::-1]:
            a[i][j] += a[i+1][j]
    for _ in range(q):
        l,r = LI()
        l -= 1
        r -= 1
        print(a[l][r])
    return

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

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
L, R = [], []
for _ in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

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

cum_sum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    cum_sum[L[i]][R[i]] += 1

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

def get_sum_range(L, R):
    ans = cum_sum[R][R] - cum_sum[R][L-1] - cum_sum[L-1][R] + cum_sum[L-1][L-1]
    return ans

for i in range(Q):
    ans = get_sum_range(p[i], q[i])
    print(ans)

Submission status: Accepted

Solution code:
N,M,Q = map(int, input().split())
# A[i][j]: L=i, R=jの本数
A = [[0] * 509 for _ in range(509)]
for _ in range(M):
    L, R = map(int, input().split())
    A[L][R] += 1

# 二次元累積和をとる O(N * N)
for i in range(1, N + 1):
    for j in range(1, N + 1):
        A[i][j] += A[i][j - 1]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        A[i][j] += A[i - 1][j]

# クエリ O(Q)
for _ in range(Q):
    L, R = map(int, input().split())
    ans = A[R][R] - A[L - 1][R] - A[R][L - 1] + A[L - 1][L - 1]
    print(ans)

Submission status: Accepted

Solution code:
import sys
input=lambda: sys.stdin.readline().rstrip()
n,m,q=map(int,input().split())
T=[[0]*(n+2) for _ in range(n+2)]
for _ in range(m):
  l,r=map(int,input().split())
  T[l][r]+=1
for i in range(1,n+1)[::-1]:
  for j in range(1,n+1):
    T[i][j+1]+=T[i][j]
for j in range(1,n+1):
  for i in range(1,n+1)[::-1]: 
    T[i-1][j]+=T[i][j]

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

Submission status: Accepted

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

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

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

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

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

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

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

Submission status: Accepted

Solution code:
'''
https://atcoder.jp/contests/abc106/tasks/abc106_d
'''
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(10000000)
    from collections import Counter, deque
    #from collections import defaultdict
    from itertools import combinations, permutations, accumulate
    #from itertools import product
    from bisect import bisect_left,bisect_right
    import heapq
    from math import floor, ceil
    #from operator import itemgetter

    #inf = 10**17
    #mod = 1000000007

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

    def csum_gen(h, w, table):
        d = [[0]*w for _ in range(h)]
        d[0][0] = table[0][0]
        for i in range(1, w):
            d[0][i] = d[0][i-1]+table[0][i]
        #上のマスとその行の和を足す
        for i in range(1, h):
            total = 0
            for j in range(w):
                total += table[i][j]
                d[i][j] = d[i-1][j]+total
        return d

    d = csum_gen(N, N, table)

    def csum_cal(p, q, x, y, d):
        #p<=x and q<=y
        if p>x or q>y:
            return 0
        if p==0 and q==0:
            return d[x][y]
        if p==0:
            return d[x][y] - d[x][q-1]
        if q==0:
            return d[x][y] - d[p-1][y]
        return d[x][y]-d[p-1][y]-d[x][q-1]+d[p-1][q-1]


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



if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import math,itertools,bisect,sys,copy,queue

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())

N,M,Q = LI()

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

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

for _ in range(Q):
    l,r = LI()
    print (c[r][r]-c[r][l-1]-c[l-1][r]+c[l-1][l-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from operator import itemgetter

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

que = []

for _ in range(M):
    l, r = list(map(int, input().split()))
    que.append((-1, l, r))
for i in range(Q):
    l, r = list(map(int, input().split()))
    que.append((i, l, r))

ans = [0 for _ in range(Q)]
que = sorted(que, key=itemgetter(2, 0))
before = -1
ans_data = [0 for _ in range(N)]
for i, l, r in que:
    if i == -1:
        ans_data[l-1] += 1
    else:
        ans[i] = sum(ans_data[l-1:r])

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)

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

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


N, M, Q = map(int, input().split())
sects = []
for _ in range(M):
    sects.append([0] + list(map(int, input().split())))
for q in range(Q):
    sects.append([1] + list(map(int, input().split())) + [q])

sects.sort(key=lambda x: x[2])
b = Bit(N)
ans = []
for s in sects:
    if s[0] == 0:
        b.add(s[1], 1)
    else:
        ans.append((b.sum(s[2]) - b.sum(s[1] - 1), s[3]))
ans.sort(key=lambda x: x[1])
for x in ans:
    print(x[0])

Submission status: Accepted

Solution code:
import numpy as np
import sys

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

I = sys.stdin.read().split()

L,R = np.array(I[:2*M], np.int32).reshape([2,-1], order='F')
p,q = np.array(I[2*M:], np.int32).reshape(2,-1, order='F')
d = np.zeros([N+1, N+1], np.int32)

d = np.zeros([1+N, 1+N], np.int32)
np.add.at(d, (N-L,R), 1)

d = np.add.accumulate(d, axis = 1)
d = np.add.accumulate(d)

ans = d[N-p,q]

for a in ans:
	print(a)

Submission status: Accepted

Solution code:
6# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

def main():
    N,M,Q=map(int,input().split())
    x=[[0]*N for _ in range(N)]
    for i in range(M):
        L,R=map(lambda x: int(x)-1,input().split())
        x[L][R]+=1
    S=[[0]*(N+1) for _ in range(N+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]+x[i][j]
    for _ in range(Q):
        p,q=map(lambda x: int(x)-1,input().split())
        print(S[q+1][q+1]-S[q+1][p]-S[p][q+1]+S[p][p])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
6# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
def input(): return sys.stdin.readline().rstrip()

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

if __name__ == '__main__':
    main()

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

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
LR=[tuple(map(int,input().split())) for _ in range(m)]
PQ=[tuple(map(int,input().split())) for _ in range(q)]

MAP=[[0]*(n+1) for _ in range(n+1)]
for l,r in LR:
    MAP[l][r] +=1

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

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

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

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
p = []
q = []

# 2次元累積和を使う(都市数 * 都市数)
# l で始まり、 j で終わる鉄道を CS[l - 1][r - 1]に入れる
# その後、累積和を取っていく
CS = [[0] * (N + 1) for _ in range(N + 1)]

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

# N <= 500 だからできるやつ	
for i in range(N + 1):
	for j in range(N + 1):
		if j - 1 >= 0: # １つ左にあるマスからもらう
			CS[i][j] += CS[i][j - 1]
		if i - 1 >= 0: # 1つ上にあるマスからもらう
			CS[i][j] += CS[i - 1][j]
		if j - 1 >= 0 and i - 1 >= 0: # 包除原理
			CS[i][j] -= CS[i - 1][j - 1]
	
for _ in range(Q):
	a, b = map(int, input().split())
	p.append(a)
	q.append(b)
	
for i in range(Q):
	print(CS[q[i]][q[i]] - CS[p[i] - 1][q[i]] - CS[q[i]][p[i] - 1] + CS[p[i] - 1][p[i] - 1])

Submission status: Accepted

Solution code:
# ABC106 D - AtCoder Express 2
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]
for i in range(n+1):
    for j in range(n+1):
        mat[i][j]+=mat[i][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 sys
input=sys.stdin.readline
sys.setrecursionlimit(100000000)

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

    for _ in range(m):
        l,r=map(int,input().split())
        l-=1
        r-=1
        cum[0][r]+=1
        if l!=n-1:
            cum[l+1][r]-=1
       
    for i in range(n):
        for j in range(1,n):
            cum[i][j]+=cum[i][j-1]
    
    for i in range(1,n):
        for j in range(n):
            cum[i][j]+=cum[i-1][j]

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

if __name__=='__main__':
    main()

Submission status: Accepted

Solution code:
# ABC106 D - AtCoder Express 2
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 sys

N, M, Q = map(int, sys.stdin.readline().split())

S = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    l, r = map(int, sys.stdin.readline().split())
    S[l][r] += 1

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

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

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

Submission status: Accepted

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


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

    for i in range(M):
        matrix[L[i]][R[i]] += 1
    
    for i in range(1,N+1):
        for j in range(1,N+1):
            matrix[i][j] += matrix[i-1][j]+matrix[i][j-1]-matrix[i-1][j-1]
    
    for i in range(Q):
        pp,qq = p[i],q[i]
        print(matrix[qq][qq]-matrix[pp-1][qq]-matrix[qq][pp-1]+matrix[pp-1][pp-1])

    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:
import numpy as np

N,M,Q,*LRpq = map(int,open(0).read().split())
LR = LRpq[:2*M]
pq = LRpq[2*M:]

train_count = np.zeros((N,N),int)

for l,r in zip(LR[::2],LR[1::2]):
    train_count[l-1,r-1] += 1

query_ans = train_count[::-1,].cumsum(axis=0)[::-1,].cumsum(axis=1)

for p,q in zip(pq[::2],pq[1::2]):
    print(query_ans[p-1,q-1])

Submission status: Accepted

Solution code:

def accumulater2D(A): # B:list[list[int]]
    import copy
    #ヨコに累積和
    n = len(A)
    B = copy.deepcopy(A)
    for i in range(n):
        for j in range(n):
            if i: B[i][j] += B[i-1][j]
    #タテに累積和
    for i in range(n):
        for j in range(n):
            if j: B[i][j] += B[i][j-1]
    return B # Aの2次元累積和

N,M,Q = map(int,input().split())
LR = []
pq = []
tiles = [[0 for x in range(N+1)] for y in range(N+1)]
for i in range(M):
    L,R = list(map(int,input().split()))
    tiles[L][R] += 1
    #LR.append([L-1,R-1])
A = accumulater2D(tiles)
for i in range(Q):
    p,q = list(map(int,input().split()))
    pq.append([p,q])

for i in range(Q):
    p,q = pq[i]
    print(A[q][q]-A[p-1][q]-A[q][p-1]+A[p-1][p-1])
    #pq.append([p-1,q-1])

Submission status: Accepted

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

# 二次元累積和の作成
LR_rui = [[0 for _ in range(n+1)] for _ in range(n+1)]
# 各Lについての累積
for i in range(n):
    for j in range(n):
        LR_rui[i+1][j+1] = LR_rui[i+1][j]+LR[i][j]
# 各Rについての累積:
for i in range(n):
    for j in range(n):
        LR_rui[i+1][j+1] = LR_rui[i+1][j+1] + LR_rui[i][j+1]

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