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


main()

Submission status: Accepted

Solution code:
import sys

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

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

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


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import sys

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

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

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


if __name__ == '__main__':
  main()

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def imos():
  for j in range(N+1):
    cnt = 0
    for i in range(N+1):
      tmp = l[j][i]
      l[j][i] += cnt
      cnt += tmp

  for j in range(N+1):
    cnt = 0
    for i in range(N+1):
      tmp = l[i][j]
      l[i][j] += cnt
      cnt += tmp

N,M,Q = IL()
l = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
  a,b = IL()
  l[1][b] += 1
  if a+1 <= N:
    l[a+1][b] += -1

imos()

ans = [IL() for i in range(Q)]
for i in range(Q):
    print(l[ans[i][0]][ans[i][1]])

Submission status: Accepted

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

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

for p,q in query:
    p -= 1
    q -= 1
    if p == 0:
        print(csum2[q][q])
    else:
        print(csum2[q][q] - csum2[q][p-1] - csum2[p-1][q] + csum2[p-1][p-1])

Submission status: Accepted

Solution code:
def getSumRange(L, R):
    ans = sum[R][R] - sum[R][L - 1] - sum[L - 1][R] + sum[L - 1][L - 1]
    return ans

n, m, Q = map(int, input().split())
L = [0] * m
R = [0] * m
for i in range(m):
    L[i], R[i] = map(int, input().split())
p = [0] * Q
q = [0] * Q
for i in range(Q):
    p[i], q[i] = map(int, input().split())

sum = [[0] * (n + 1) for i in range(n + 1)]
for i in range(m):
    sum[L[i]][R[i]] += 1
for i in range(n + 1):
    for j in range(n + 1):
        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):
    ans = getSumRange(p[i], q[i])
    print(ans)

Submission status: Accepted

Solution code:
# coding:utf-8

import sys

INF = float('inf')
MOD = 10 ** 9 + 7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


n, m, q = LI()

train = [[0] * n for _ in range(n)]
for _ in range(m):
    l, r = LI_()
    train[n - 1 - l][r] += 1

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

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

for _ in range(q):
    a, b = LI_()
    print(train[n - 1 - a][b])

Submission status: Accepted

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python

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

trains = [ [int(j) for j in input().split()] for _ in range(M)]
queries = [ [int(j) for j in input().split()] for _ in range(Q)]


begin = [0] * (N+1)
# end  = [0] * (N+1)
end = [ [0] * (N+1) for _ in range(N+1)]


for l,r in trains:
    begin[l] += 1
    end[l][r] += 1

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


# print("  ", begin)
# for e,i in enumerate(end):
#     print("{:2d}".format(e), i)
# # exit(0)

for l,r in queries:
    # print("begin: ", begin[l:r+1])
    # print("begin: ", begin[l:r+1])
    ans = min ( sum(begin[l:r+1]), sum(end[l][l:r+1]))
    print(ans)

Submission status: Accepted

Solution code:
import numpy as np

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

array = np.zeros([n,n])
for _ in range(m):
    p, q = map(int, input().split())
    array[p-1][q-1] += 1
    
for p in range(n):
    for q in range(1, n):
        array[p][q] += array[p][q-1]

for p in range(1,n):
    for q in range(n):
        array[p][q] += array[p-1][q]

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

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,m,q=I()
l=[[0]*-~n for _ in range(n+1)]
for _ in range(m):
  s,g=I()
  l[s][g]+=1
for i in range(1,n+1):
  for j in range(1,n+1):
    l[i][j]+=l[i][j-1]
  for j in range(1,n+1):
    l[i][j]+=l[i-1][j]
for _ in range(q):
  s,g=I()
  print(l[g][g]-l[s-1][g]-l[g][s-1]+l[s-1][s-1])

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,m,q=I()
k=n+2
l=[0]*k**2
for _ in range(m):
  s,g=I()
  l[s*k+g]+=1
for i in range(1,n+1):
  for j in range(1,n+1):
    l[i*k+j]+=l[i*k+j-1]
for i in range(1,n+1):
  for j in range(1,n+1):
    l[i*k+j]+=l[(i-1)*k+j]
for _ in range(q):
  s,g=I()
  print(l[g*k+g]-l[(s-1)*k+g]-l[g*k+s-1]+l[(s-1)*k+s-1])

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,m,q=I()
k=n+2
l=[0]*k**2
for _ in range(m):
  s,g=I()
  l[s*k+g]+=1
for i in range(1,n+1):
  for j in range(1,n+1):
    l[i*k+j]+=l[i*k+j-1]
for i in range(1,n+1):
  for j in range(1,n+1):
    l[i*k+j]+=l[~-i*k+j]
for _ in range(q):
  s,g=I()
  print(l[g*k+g]-l[~-s*k+g]-l[g*k+s-1]+l[~-s*k+s-1])

Submission status: Accepted

Solution code:
I=lambda:list(map(int,input().split()))
n,m,q=I()
l=[[0]*-~n for _ in range(n+1)]
for _ in range(m):
  s,g=I()
  l[s][g]+=1
for i in range(1,n+1):
  for j in range(1,n+1):
    l[i][j]+=l[i][j-1]
for i in range(1,n+1):
  for j in range(1,n+1):
    l[i][j]+=l[i-1][j]
for _ in range(q):
  s,g=I()
  print(l[g][g]-l[s-1][g]-l[g][s-1]+l[s-1][s-1])

Submission status: Accepted

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

arr = [[0 for j in range(n)] for i in range(n)]
arr_sum = []
arr_sum2 = []

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


for i in range(n):
    s = 0
    arr_tmp = []
    for j in range(n):
            s += arr[i][j]
            arr_tmp.append(s)
    arr_sum.append(arr_tmp)


for j in range(n):
    s = 0
    arr_tmp2 = []
    for i in range(n-1,-1,-1):
            s += arr_sum[i][j]
            arr_tmp2.append(s)
    arr_sum2.append(arr_tmp2)

arr_sum3 = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
    for j in range(n):
        arr_sum3[i][j] = arr_sum2[j][n-i-1]

ans_arr = []
for k in range(q):
    p, q = map(int, input().split())
    ans = arr_sum3[p-1][q-1]
    ans_arr.append(ans)

for i in ans_arr:
    print(i)

Submission status: Accepted

Solution code:
n,m,q= map(int,input().split())
dataList = [[0 for xIndex in range(n+1)]for yIndex in range(n+1)]

for i in range(m):
    xTemp,yTemp = map(int,input().split())
    dataList[yTemp][xTemp]+=1
pqList=[list(map(lambda x:int(x),input().split()))for i in range(q)]
for yIndex in range(1,n+1):
    for xIndex in range(1,n+1):
        dataList[yIndex][xIndex]+=dataList[yIndex][xIndex-1]
for yIndex in range(1,n+1):
    for xIndex in range(1,n+1):
        dataList[yIndex][xIndex]+=dataList[yIndex-1][xIndex]

for pq in pqList:
    p = pq[0]-1
    q = pq[1]
    print(dataList[q][q]+dataList[p][p]-dataList[p][q]-dataList[q][p])

Submission status: Accepted

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

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


D = []
for l in range(N):
    s = 0
    d = []
    for r in range(N):
        s += A[l][r]
        d.append(s)
    D.append(d)

T = []
for r in range(N):
    s = 0
    t = []
    for l in range(N):
        s += D[N - l - 1][r]
        t.append(s)
    T.append(list(reversed(t)))

for question in questions:
    print(T[question[1]][question[0]])

Submission status: Accepted

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

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


D = []
for l in range(N):
    s = 0
    d = []
    for r in range(N):
        s += A[l][r]
        d.append(s)
    D.append(d)

T = []
for r in range(N):
    s = 0
    t = []
    for l in range(N):
        s += D[N - l - 1][r]
        t.append(s)
    T.append(t)

for question in questions:
    print(T[question[1]][N - question[0] - 1])

Submission status: Accepted

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

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


D = []
for l in range(N):
    s = 0
    d = []
    for r in range(N):
        s += A[l][r]
        d.append(s)
    D.append(d)

T = []
for r in range(N):
    s = 0
    t = [0]
    for l in range(N):
        s += D[l][r]
        t.append(s)
    T.append(t)

for question in questions:
    print(T[question[1]][N] - T[question[1]][question[0]])

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

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

kukan.sort()

li = [0]*(N+1)
ans = [0]*Q

for t, flag, s in kukan:
    if flag == -1:
        li[s] += 1
    else:
        ans[flag] = sum(li[s:t+1])

for a in ans:
    print(a)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

for _ in range(M):
    a, b = map(int, input().split())
    mat[a][b] += 1


def solve():

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

    ans = []

    for _ in range(Q):
        ql, qr = map(int, input().split())
        tmp = 0
        for i in range(ql, qr+1):
            tmp += mat[i][qr] - mat[i][ql-1]
        ans.append(tmp)

    for a in ans:
        print(a)


def solve2():

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

    ans = [0]*Q
    for i in range(Q):
        ql, qr = map(int, input().split())
        t = mat[qr][qr] - mat[ql-1][qr] - mat[qr][ql-1] + mat[ql-1][ql-1]
        ans[i] = t

    for a in ans:
        print(a)


solve2()

Submission status: Accepted

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

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

for e in ans_list:
    print(e)

Submission status: Accepted

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

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

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

for i in ans:
    print(i)

Submission status: Accepted

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


for x in range(501):
    mp[0][x + 1] += mp[0][x]

for y in range(1, 502):
    for x in range(501):
        mp[y][x + 1] += mp[y][x]
        mp[y][x] += mp[y - 1][x]

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

Submission status: Accepted

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

def main():
    na = list(map(int, input().split()))
    N, M, Q = na[0], na[1], na[2]
    tc = [0] * (N * N)
    ttc = [0] * (N * N)
    for i in range(M):
        na = list(map(int, input().split()))
        tc[N * (na[1] - 1) + na[0] - 1] += 1
    p_list = []
    q_list = []
    for i in range(Q):
        na = list(map(int, input().split()))
        p_list.append(na[0])
        q_list.append(na[1])


    for r in range(N):
        t = 0
        nr = N * r
        for l in range(r, -1, -1):
            t += tc[nr + l]
            ttc[nr + l] = t

    for l in range(N):
        t = 0
        for r in range(l, N):
            nr = N * r
            t += ttc[nr + l]
            ttc[nr + l] = t


    for i in range(Q):
        print(ttc[N * (q_list[i] - 1) + p_list[i] - 1])

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

for y in range(N+1):
    for x in range(N):
        L[x+1][y] += L[x][y]  
for _ in range(Q):
    x, y = map(int, input().split())
    print(L[N][y]-L[x-1][y])

Submission status: Accepted

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

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

totals = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
    for j in range(1, n + 1):
        totals[i][j] += totals[i][j - 1] + matrix[i][j]

answers = []
for _ in range(q):
    p, q = map(int, input().split())
    answer = sum(totals[i][q] - totals[i][p - 1] for i in range(p, q + 1))
    answers.append(answer)

for answer in answers:
    print(answer)

Submission status: Accepted

Solution code:
from sys import stdin
from itertools import accumulate
from pprint import pprint
input = stdin.readline

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

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

#accum = [[0]*(N+1) for _ in range(N+1)]
#for i in range(N+1):
#    accum[i][0] = count[i][0]
#    for j in range(1, N+1):
#        accum[i][j] = accum[i][j-1] + count[i][j]
#pprint(accum)
#for i in range(1, N+1):
#    for j in range(N+1):
#        accum[i][j] = accum[i-1][j] + accum[i][j]
#pprint(accum)
accum = list(zip(*[list(accumulate(d)) for d in zip(*(accumulate(c) for c in count))]))
#pprint(accum)

#test = [[0]*(N+1) for _ in range(N+1)]
#for i in range(1, N+1):
#    for j in range(1, N+1):
#        test[i][j] = accum[j][j] - accum[i-1][j] - \
#            accum[j][i-1] + accum[i-1][i-1]
# pprint(test)


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

Submission status: Accepted

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

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

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

accum = [[0]*(N+1) for _ in range(N+1)]
for i in range(N+1):
    accum[i][0] = count[i][0]
    for j in range(1, N+1):
        accum[i][j] = accum[i][j-1] + count[i][j]
for i in range(1, N+1):
    for j in range(N+1):
        accum[i][j] = accum[i-1][j] + accum[i][j]
# pprint(accum)

test = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        test[i][j] = accum[j][j] - accum[i-1][j] - \
            accum[j][i-1] + accum[i-1][i-1]
# pprint(test)


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

Submission status: Accepted

Solution code:
n, m, q = [int(i) for i in input().split()]
imos = [[0 for r in range(n+1)] for l in range(n+1)]
for i in range(m):
    l, r = [int(i) - 1 for i in input().split()]
    imos[0][r] += 1
    imos[l+1][r] -= 1
#imos法
for l in range(n):
    for r in range(1, n):
        imos[l][r] += imos[l][r-1]
for r in range(n):
    for l in range(1, n):
        imos[l][r] += imos[l-1][r]
for i in range(q):
    l, r = [int(i) - 1 for i in input().split()]
    print(imos[l][r])

Submission status: Accepted

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

for i in range(m):
    l, r = map(int, input().split())
    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):
    for j in range(n+1):
        dp[i+1][j] += dp[i][j]
    
for i in range(q):
    p, q = map(int, input().split())
    print(dp[q][q] - dp[q][p-1] - dp[p-1][q] + dp[p-1][p-1])

Submission status: Accepted

Solution code:
#横にn個入力
n, m, q = map(int, input().split())
#行列
s = []
for i in range(m):#h:高さ
    s.append([int(m) for m in input().split()] + [i])
# 行列
t = []
for i in range(q):  # h:高さ
    t.append([int(m) for m in input().split()])

LR = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for v in range(m):
     LR[s[v][0]][s[v][1]] += 1

for j in range(1, n + 1):
    for i in range(1, n + 1):#Lについての累積和
        LR[i][j] += LR[i - 1][j]
for i in range(1, n + 1):
    for j in range(1, n + 1):#Rについての累積和，2次元累積和にする
        LR[i][j] += LR[i][j - 1]

for k in range(q):
    tmp = 0
    #for j in range(t[k][0], t[k][1] + 1):#Rについてみていく
        #tmp += LR[t[k][1]][j] - LR[t[k][0] - 1][j]
    tmp += (LR[t[k][1]][t[k][1]] - LR[t[k][1]][t[k][0] - 1]) - (LR[t[k][0] - 1][t[k][1]] - LR[t[k][0] - 1][t[k][0] - 1])

    print(tmp)

Submission status: Accepted

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

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

for p, q in pq:
    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())
A = [[0] * (n+2) for i in range(n+2)]

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

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

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

Submission status: Accepted

Solution code:
n,m,Q = map(int, input().split())
train = []
for i in range(n):
  a = []
  for j in range(n):
    a.append(0)
  train.append(a)
  
for i in range(m):
  l,r = map(int, input().split())
  train[l-1][r-1] += 1
cumsum = []
list1 = []
for i in range(n+1):
  list1.append(0)
cumsum.append(list1)
for i in range(n):
  lst = [0,cumsum[i][1]+train[i][0]]
  for j in range(1,n):
    lst.append(lst[j]+train[i][j]+(cumsum[i][j+1]-cumsum[i][j]))
  cumsum.append(lst)
for i in range(Q):
  p,q = map(int, input().split())
  print(cumsum[q][q]-cumsum[p-1][q]-cumsum[q][p-1]+cumsum[p-1][p-1])

Submission status: Accepted

Solution code:
num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * (num_city + 1) for i in range(0, num_city + 1)]
for i in range(0, num_train):
    start, arrive = [int(j) for j in input().split()]
    trains[start][arrive] += 1

#累積和表を作る
cumlative_sum = [[0] * (num_city + 1) for i in range(0, num_city  + 1)]
for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        cumlative_sum[start][arrive] = cumlative_sum[start][arrive - 1] + trains[start][arrive]

for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        cumlative_sum[start][arrive] += cumlative_sum[start - 1][arrive]

for i in range(0, num_question):
    start, arrive = [int(j) for j in input().split()]
    result = cumlative_sum[arrive][arrive] - cumlative_sum[start - 1][arrive] - cumlative_sum[arrive][start - 1] + cumlative_sum[start - 1][start - 1]
    print(result)

Submission status: Accepted

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

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

for i, j in x:
    table[i-1][j-1] += 1

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

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

for i, j in y:
    print(table[i-1][j-1])

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
Trains = []
for i in range(M):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1
    Trains.append((l, r))


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(N, N)
R2D.load(Trains)
R2D.calc()

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

Submission status: Accepted

Solution code:
n,m,Q = map(int, input().split())
train = []
for i in range(n):
  a = []
  for j in range(n):
    a.append(0)
  train.append(a)
  
for i in range(m):
  l,r = map(int, input().split())
  train[l-1][r-1] += 1
cumsum = []
list1 = []
for i in range(n+1):
  list1.append(0)
cumsum.append(list1)
for i in range(n):
  lst = [0,cumsum[i][1]+train[i][0]]
  for j in range(1,n):
    lst.append(lst[j]+train[i][j]+(cumsum[i][j+1]-cumsum[i][j]))
  cumsum.append(lst)
for i in range(Q):
  p,q = map(int, input().split())
  print(cumsum[q][q]-cumsum[p-1][q]-cumsum[q][p-1]+cumsum[p-1][p-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

A = [[0] * (N+1) for i in range(N)]
for i in range(1,N+1):
  A[0][i] = C[i][i]
for i in range(1,N):
  A[1][i] = A[0][i] + A[0][i+1] + C[i][i+1]
for i in range(2,N):
  for j in range(1,N+1-i):
    A[i][j] = A[i-1][j] + A[i-1][j+1] - A[i-2][j+1] + C[j][i+j]
    
for i in range(Q):
  p, q = list(map(int, input().split()))
  print(A[q-p][p])

Submission status: Accepted

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

"""
参考：https://betrue12.hateblo.jp/entry/2018/08/18/224408
・二次元累積和
・こっちの方針のが分かりやすいかも。
"""

N, M, Q = map(int, input().split())
LR = [[0] * (N) for i in range(N)]
for i in range(M):
    l, r = map(int, input().split())
    # 左端=L、右端=Rの表
    LR[l-1][r-1] += 1

# 二次元の縦横両方について累積和を出す
# 縦方向の足し方を逆からにすることで、今回の条件と合致できる
for i in range(N):
    for j in range(1, N):
        # 左端=L、右端<=Rになる
        LR[i][j] += LR[i][j-1]
for i in range(N):
    for j in range(N-2, -1, -1):
        # 左端>=L、右端<=Rになる
        LR[j][i] += LR[j+1][i]

for i in range(Q):
    p, q = map(int, input().split())
    # ここでは添字指定だけで加減不要
    ans = LR[p-1][q-1]
    print(ans)

Submission status: Accepted

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

"""
参考：https://img.atcoder.jp/abc106/editorial.pdf
　　　https://atcoder.jp/contests/abc106/submissions/3024983
　　　https://imoz.jp/algorithms/imos_method.html
・二次元累積和
・最後にどこを足し引きするかは上記参考の二次元いもすと同じ話だと思う。
"""

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

# 縦横両方について累積和を出す
# 先頭1行1列は0のままにしておく
for i in range(1, N+1):
    for j in range(2, N+1):
        LR[i][j] += LR[i][j-1]
for i in range(1, N+1):
    for j in range(2, N+1):
        LR[j][i] += LR[j-1][i]

for i in range(Q):
    p, q = map(int, input().split())
    # +左上 -右上 -左下 +右下
    ans = LR[p-1][p-1] - LR[p-1][q] - LR[q][p-1] + LR[q][q]
    print(ans)

Submission status: Accepted

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

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

#for l in lr :        
#    print(l)
#print()

# 二次元累積和
for i in range(n) :
    for j in range(n) :
        left = 0
        btm  = 0
        mid  = 0

        if i > 0 :
            left = lr[j][i-1]
        if j > 0 :
            btm  = lr[j-1][i]
        if i > 0 and j > 0 :
            mid  = lr[j-1][i-1]
       
        lr[j][i] = lr[j][i] + left + btm - mid

#for l in lr :        
#    print(l)

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

    l = l - 1
    r = r - 1
    pre = 0
    if l > 0:    
        #print(lr[r][r],lr[l-1][r],lr[r][l-1],lr[l-1][l-1])
        pre = lr[l-1][r] + lr[r][l-1] - lr[l-1][l-1]     

    count = lr[r][r] - pre
    ans.append(count)

for a in ans:
    print(a)

Submission status: Accepted

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

N, M, Q = (int(i) for i in input().split())
dp = [[0] *(N+1) for i in range(N+1)]
for i in range(M):
    L, R = (int(i) for i in input().split())
    dp[L-1][R-1] += 1

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

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

Submission status: Accepted

Solution code:
N, M, QN = [int(x) for x in input().split()]

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

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

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

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

for i in range(QN):
    p, q = [int(x) for x in input().split()]
    ret = 0
    ret = ret + MM[q][q] - MM[q][p - 1] - MM[p - 1][q] + MM[p - 1][p - 1]
    print(ret)