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())
    L, R = zip(*(
        map(int, input().split())
        for _ in range(M)
    ))
    p, q = zip(*(
        map(int, input().split())
        for _ in range(Q)
    ))

    # answers = f(N, M, Q, L, R, p, q)
    # experiment(N, M, Q, L, R, p, q)
    # answers = TLE(N, M, Q, L, R, p, q)
    answers = editorial_2(N, M, Q, L, R, p, q)
    for ans in answers:
        print(ans)


def editorial_2(N, M, Q, L, R, p, q):
    """
    ２次元累積和のライブラリを持っておくとよいらしい
        確かに実装ミスりそう
    """
    t = [[0] * (N+1) for _ in range(N+1)]
    for l, r in zip(L, R):
        t[l][r] += 1

    # 二次元累積和
    # 積分画像と同じ
    for l in range(1, N+1):
        for r in range(1, N+1):
            t[l][r] += t[l][r-1]
    for l in range(1, N+1):
        for r in range(1, N+1):
            t[l][r] += t[l-1][r]

    answers = []
    for l, r in zip(p, q):
        ans = 0
        ans += t[r][r]
        ans -= t[l-1][r]
        ans -= t[r][l-1]
        ans += t[l-1][l-1]

        answers.append(ans)

    return answers


def editorial_1(N, M, Q, L, R, p, q):
    # Lごとの累積和
    t1 = [[0] * (N+1) for _ in range(N+1)]
    t2 = [[0] * (N+1) for _ in range(N+1)]
    # LRの組合せ, N<=500より間に合う
    for l, r in zip(L, R):
        t1[l][r] += 1

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

    answers = []
    for _p, _q in zip(p, q):
        ans = 0
        for l in range(_p, _q+1):
            ans += t2[l][_q] - t2[l][_p-1]

        answers.append(ans)

    return answers


def TLE(N, M, Q, L, R, p, q):
    """
    10^5 * 10^5
    """
    answers = []
    for _p, _q in zip(p, q):
        ans = 0
        for left, right in zip(L, R):
            if _p <= left and right <= _q:
                ans += 1

        answers.append(ans)

    return answers


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate as acc
import sys


def main():
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    LR = [[0]*N for _ in [0]*N]
    for l, r in (map(int, e.split()) for e in s[1:M + 1]):
        LR[l - 1][r - 1] += 1

    S = [tuple(acc(reversed(s))) for s in zip(*(acc(x) for x in LR))]
    print('\n'.join(map(str, (S[q - 1][N - p] for p, q in (map(int, e.split()) for e in s[M + 1:])))))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
from itertools import accumulate as acc
import sys

if __name__ == "__main__":
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    LR = [[0]*N for _ in [0]*N]
    for l, r in (map(int, e.split()) for e in s[1:M + 1]):
        LR[l - 1][r - 1] += 1

    S = [tuple(acc(reversed(s))) for s in zip(*(acc(x) for x in LR))]
    print('\n'.join(map(str, (S[q - 1][N - p] for p, q in (map(int, e.split()) for e in s[M + 1:])))))

Submission status: Accepted

Solution code:
from itertools import accumulate as acc
import sys

if __name__ == "__main__":
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    LR = [[0]*N for _ in range(N)]
    for l, r in (map(int, e.split()) for e in s[1:M + 1]):
        LR[l - 1][r - 1] += 1

    S = [tuple(acc(reversed(s))) for s in zip(*(acc(x) for x in LR))]
    print('\n'.join(map(str, (S[q - 1][N - p] for p, q in (map(int, e.split()) for e in s[M + 1:])))))

Submission status: Accepted

Solution code:
from itertools import accumulate as acc
import sys

if __name__ == "__main__":
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    LR = [[0]*N for _ in range(N)]
    for l, r in (map(int, e.split()) for e in s[1:M + 1]):
        LR[l - 1][r - 1] += 1

    S = [tuple(acc(reversed(s))) for s in zip(*(acc(x) for x in LR))]
    for p, q in (map(int, e.split()) for e in s[M+1:]):
        print(S[q-1][N-p])

Submission status: Accepted

Solution code:
import sys
s = sys.stdin.readlines()
 
N,M,Q = map(int,s[0].split())
 
Section = [[0]*N for _ in [0]*N]
for L,R in (map(int, e.split()) for e in s[1:M+1]):
    Section[L-1][R-1] += 1
 
Sum = [[0]*(N+1) for _ in [0]*(N+1)]
for i in range(N):
    for j in range(N):
        Sum[i+1][j+1] = Sum[i][j+1]+Sum[i+1][j]-Sum[i][j]+Section[i][j]
 
for p,q in (map(int, e.split()) for e in s[M+1:]):
    print(Sum[q][q]-Sum[p-1][q])

Submission status: Accepted

Solution code:
from itertools import accumulate as acc

def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))


if __name__ == "__main__":
    N, M, Q = LI()
    LR = [[0]*N for _ in range(N)]
    for i in range(M):
        l, r = LI_()
        LR[l][r] += 1

    # 二次元累積和
    S = [tuple(acc(reversed(s))) for s in zip(*(acc(x) for x in LR))]
    for _ in range(Q):
        p, q = LI()
        # 必ず正方形だから、
        print(S[q-1][N-p])

Submission status: Accepted

Solution code:
from itertools import accumulate as acc

def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))


if __name__ == "__main__":
    N, M, Q = LI()
    LR = [[0]*N for _ in range(N)]
    for i in range(M):
        l, r = LI_()
        LR[l][r] += 1

    # 二次元累積和
    S = [[0] * N for _ in range(N)]
    for i, row in enumerate(LR):
        LR[i] = list(acc(row))
    for i, col in enumerate(zip(*LR)):
        S[i] = list(acc(reversed(col)))

    for _ in range(Q):
        p, q = LI()
        # 必ず正方形だから、
        print(S[q-1][N-p])

Submission status: Accepted

Solution code:
n,m,q = list(map(int,input().split()))
c = []
query = []

for i in range(n):
  c.append([0*i for i in range(n)])
for i in range(m):
  train = []
  train = list(map(int,input().split()))
  c[train[0]-1][train[1]-1] += 1
for i in range(q):
  query.append(list(map(int,input().split())))

for i in range(n):    
  for j in range(n):
    if j > 0:
      c[i][j] += c[i][j-1]
    else:
      pass

for i in range(n):    
  for j in range(n):
    if i > 0:
      c[i][j] += c[i-1][j]
    else:
      pass

for l in query:    
  if l[0]-1 >= 1 and l[1]-1 >= 1:
    print(c[l[1]-1][l[1]-1] - c[l[1]-1][l[0]-2] - c[l[0]-2][l[1]-1] + c[l[0]-2][l[0]-2])
  elif l[1]-1 > 0:
    print(c[l[1]-1][l[1]-1])
  else:
    print(c[0][0])

Submission status: Accepted

Solution code:
import sys
s = sys.stdin.readlines()

N,M,Q = map(int,s[0].split())

Section = [[0]*N for _ in [0]*N]
for L,R in (map(int, e.split()) for e in s[1:M+1]):
    Section[L-1][R-1] += 1

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

for p,q in (map(int, e.split()) for e in s[M+1:]):
    print(Sum[q][q]-Sum[p-1][q])

Submission status: Accepted

Solution code:
def arr(row, column, value): return [[value for _ in range(column)] for _ in range(row)]

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

sum_range = arr(n + 1, n + 1, 0)
#sum_range[0][0] - sum_range[n][n]まで
#初期値0
#行列値は1からnを取るが、累積和を加算する過程で行列を1引いたものを参照するので、[0][0]がエラーにならないと便利？

for _ in range(m):
    L, R = map(int, input().split())
    sum_range[L][R] += 1#(L, R)間を運行す列車の数を代入
    
for L in range(1, n + 1):
    for R in range(1, n + 1):
        #累積和を取る（53:44あたり）
        #https://www.youtube.com/watch?v=OdJH-io-sVw
        sum_range[L][R] += sum_range[L - 1][R]
        sum_range[L][R] += sum_range[L][R - 1]
        sum_range[L][R] -= sum_range[L - 1][R - 1]

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

Submission status: Accepted

Solution code:
import sys
s = sys.stdin.readlines()

N,M,Q = map(int,s[0].split())

Section = [[0]*N for _ in range(N)]
for L,R in (map(int, e.split()) for e in s[1:M+1]):
    Section[L-1][R-1] += 1

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

for p,q in (map(int, e.split()) for e in s[M+1:]):
    print(Sum[q][q]-Sum[p-1][q])

Submission status: Accepted

Solution code:
import sys
s = sys.stdin.readlines()
N,M,Q = map(int,s[0].split())

Section = [[0]*N for _ in range(N)]
for L,R in (map(int, e.split()) for e in s[1:M+1]):
    Section[L-1][R-1] += 1

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

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

for p,q in (map(int, e.split()) for e in s[M+1:]):
    print(Ans[p-1][q-1])

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

temp = [ [0 for _ in range(n)] for _ in range(n)]
tables = [ [0 for _ in range(n)] for _ in range(n)]

if n == 1:
    print('1')
    exit()

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

pq = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

hoge = 0
for j in range(n):
    hoge += temp[0][j]
    tables[0][j] = hoge

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

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

Submission status: Accepted

Solution code:
import numpy as np

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = np.array([[0 for j in range(n)] for i in range(n)],dtype=np.int32)
for (l,r) in rails:
    xlist[l-1,r-1]+=1

sumsumlist = np.cumsum(np.cumsum(xlist,axis=1),axis=0)


for (p,q) in qs:
    if p>1:
        ans = sumsumlist[q-1][q-1] - sumsumlist[q-1][p-2] - sumsumlist[p-2][q-1] + sumsumlist[p-2][p-2]
    elif p==1:
        ans = sumsumlist[q-1][q-1]

    print(ans)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product
import numpy as np

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = np.array([[0 for j in range(n)] for i in range(n)])
for (l,r) in rails:
    xlist[l-1,r-1]+=1

sumsumlist = np.cumsum(np.cumsum(xlist,axis=1),axis=0)


for (p,q) in qs:
    if p>1:
        ans = sumsumlist[q-1][q-1] - sumsumlist[q-1][p-2] - sumsumlist[p-2][q-1] + sumsumlist[p-2][p-2]
    elif p==1:
        ans = sumsumlist[q-1][q-1]

    print(ans)

Submission status: Accepted

Solution code:

from collections import Counter
from itertools import product
import numpy as np

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = np.array([[0 for j in range(n)] for i in range(n)])
for (l,r),i in Counter(rails).items():
    xlist[l-1,r-1]=i

sumsumlist = np.cumsum(np.cumsum(xlist,axis=1),axis=0)


for (p,q) in qs:
    if p>1:
        ans = sumsumlist[q-1][q-1] - sumsumlist[q-1][p-2] - sumsumlist[p-2][q-1] + sumsumlist[p-2][p-2]
    elif p==1:
        ans = sumsumlist[q-1][q-1]

    print(ans)

Submission status: Accepted

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

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


def rectangle_sum(n):
    table = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

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

    for y in range(n + 1):
        for x in range(1, n + 1):
            table[y][x] += table[y][x - 1]

    for y in range(1, n + 1):
        for x in range(n + 1):
            table[y][x] += table[y - 1][x]
    return table


t = rectangle_sum(N)
for p, q in PQ:
    tmp = t[q][q] - t[q][p - 1] - t[p - 1][q] + t[p - 1][p - 1]
    print(tmp)

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


def rectangle_sum(n):
    table = [[0 for _ in range(n)] for _ in range(n)]

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

    for y in range(N):
        for x in range(1, N):
            table[y][x] += table[y][x - 1]

    for y in range(1, N):
        for x in range(N):
            table[y][x] += table[y - 1][x]
    return table


t = rectangle_sum(N)
for p, q in PQ:
    if p - 2 >= 0:
        tmp = t[q - 1][q - 1] - t[q - 1][p - 2] - t[p - 2][q - 1] + t[p - 2][p - 2]
    else:
        tmp = t[q - 1][q - 1]

    print(tmp)

Submission status: Accepted

Solution code:

N, M, Q = map(int, input().split())
rail = []
for i in range(M):
    r = list(map(int, input().split()))
    rail.append(r)
 
query = []
for i in range(Q):
    q = list(map(int, input().split()))
    query.append(q)
 
f = [[0 for i in range(N)] for j in range(N)]
g = [[0 for i in range(N)] for j in range(N)]
 
for i in range(M):
    f[rail[i][0]-1][rail[i][1]-1] += 1
 
for i in range(N):
    j = 0
    while j + i < N:
        if i == 0:
            g[j][j+i] = f[j][j+i]
        else:
            g[j][j+i] = f[j][j+i] + g[j+1][j+i] + g[j][j+i-1] - g[j+1][j+i-1]
        j += 1
 
for i in range(Q):
    print(g[query[i][0]-1][query[i][1]-1])

Submission status: Accepted

Solution code:
# coding: utf-8

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

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

for m in M:
    LR[m[0]-1][m[1]] += 1 

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

for q in Q:
    print(LR[q[0]-1][q[1]])

Submission status: Accepted

Solution code:
import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]


def main():
    n, m, q = na()
    lrs = [na() for _ in range(m)]
    pqs = [na() for _ in range(q)]

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

    # 
    for l, r in lrs:
        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]

    # 列方向の累積和
    for j in range(1, n+1):
        for i in range(1, n+1):
            table[i][j] += table[i-1][j]
            
    for p, q in pqs:
        v = table[q][q] - table[q][p-1] - table[p-1][q] + table[p-1][p-1]
        print(v)
    

main()

Submission status: Accepted

Solution code:
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))


if __name__ == "__main__":
    N, M, Q = LI()
    LR = [[0]*(N+1) for _ in range(N+1)]
    for i in range(M):
        l, r = LI()
        LR[l][r] += 1

    # 二次元累積和
    for i in range(1, N+1):
        for j in range(1, N+1):
            LR[i][j] += LR[i][j-1]
            LR[i][j] += LR[i-1][j]
            LR[i][j] -= LR[i-1][j-1]

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

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
rail = []
for i in range(M):
    r = list(map(int, input().split()))
    rail.append(r)

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

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

for i in range(M):
    f[rail[i][0]-1][rail[i][1]-1] += 1

for i in range(N):
    j = 0
    while j + i < N:
        if i == 0:
            g[j][j+i] = f[j][j+i]
        else:
            g[j][j+i] = f[j][j+i] + g[j+1][j+i] + g[j][j+i-1] - g[j+1][j+i-1]
        j += 1

for i in range(Q):
    print(g[query[i][0]-1][query[i][1]-1])

Submission status: Accepted

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

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

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

grid=[[0]*(n+1) for i in range(n+1)]

for i in range(m):
    grid[l[i]][r[i]]+=1

for i in range(1,n+1):
    for j in range(1,n+1):
        grid[i][j]+=grid[i-1][j]
        grid[i][j]+=grid[i][j-1]
        grid[i][j]-=grid[i-1][j-1]
    
for i in range(Q):
    print(grid[q[i]][q[i]]-grid[q[i]][p[i]-1]-grid[p[i]-1][q[i]]+grid[p[i]-1][p[i]-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""

n, m, qn = list(map(int, input().split()))

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

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

for _ in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = lr[qi][qi] - lr[qi][pi-1] - lr[pi-1][qi] +lr[pi-1][pi-1]
    
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
import numpy as np
def main():
    s = sys.stdin.readlines()
    N, M, _ = map(int, s[0].split())
    X = np.zeros((N, N), dtype=int)
    for L, R in (map(int, e.split()) for e in s[1:M + 1]): X[L - 1][R - 1] += 1
    S = np.cumsum(np.cumsum(X, axis=1)[::-1], axis=0)[::-1]
    print('\n'.join(map(str, (S[p - 1][q - 1] for p, q in (map(int, e.split()) for e in s[M + 1:])))))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate as acc
def main():
    s = sys.stdin.readlines()
    N, M, _ = map(int, s[0].split())
    X = [[0] * N for _ in [0] * N]
    for L, R in (map(int, e.split()) for e in s[1:M + 1]): X[L - 1][R - 1] += 1
    S = [tuple(acc(reversed(s))) for s in zip(*(acc(x) for x in X))]
    print('\n'.join(map(str, (S[q - 1][N - p] for p, q in (map(int, e.split()) for e in s[M + 1:])))))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, Q = map(int,input().split())
senro = [list(map(int,input().split())) for k in range(M)]
query = [list(map(int,input().split())) for k in range(Q)]
S = [[0 for k in range(N+2)] for l in range(N+2)]

for s in senro:
    S[s[0]][s[1]] += 1

for k in range(1,N+2):
    for l in range(1,N+2):
        S[k][l] += S[k][l-1]

for k in range(1,N+2):
    for l in range(1,N+2):
        S[k][l] += S[k-1][l]

for q in query:
    print(S[q[1]][q[1]]-S[q[0]-1][q[0]-1]-S[q[0]-1][q[1]]+S[q[1]][q[0]-1])

Submission status: Accepted

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

dp = [[0 for col in range(N)] for row in range(N)]

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

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

results = []

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

for result in results:
    print(result)

Submission status: Accepted

Solution code:
import sys
def main():
    s = sys.stdin.readlines()
    N, M, Q = map(int, s[0].split())
    x = [[0] * N for _ in [0] * N]
    for e in s[1:M + 1]:
        L, R = map(int, e.split())
        x[L - 1][R - 1] += 1
    for k in range(1, N):
        for i in range(N - k):
            j = i + k
            x[i][j] += x[i][j - 1] + x[i + 1][j] - x[i + 1][j - 1]
    res = []
    for e in s[M + 1:]:
        p, q = map(int, e.split())
        res.append(x[p - 1][q - 1])
    print('\n'.join(map(str, res)))
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# encoding: utf-8
N, M, Q = map(int, input().split())
LR = [list(map(int, input().split())) for i in range(M)]
pq = [list(map(int, input().split())) for i in range(Q)]

# create table of count: M
cnt_tab = [0] * (N ** 2)
for l, r in LR: cnt_tab[(r - 1) * N + (l - 1)] += 1

# create table of sum: N ** 2
sum_tab = [None] * (N ** 2) 
for r in range(N):
    newsum = 0
    for l in reversed(range(r + 1)):
        newsum += cnt_tab[r * N + l] 
        if l < r: sum_tab[r * N + l] = sum_tab[(r - 1) * N + l] + newsum
        else: sum_tab[r * N + l] = newsum
        
# anser the questions using sum table: Q
for p, q in pq: print(sum_tab[(q - 1) * N + (p - 1)])

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
lr = [[0 for _ in range(0,n+1)] for _ in range(0,n+1)]
ans = []
for i in range(0,m):
    L,R = map(int,input().split())
    lr[R][L] += 1
for r in range(0,n+1):
    for l in range(0,n):
        lr[r][n-l-1] += lr[r][n-l]
for l in range(0,n+1):
    for r in range(0,n):
        lr[r+1][l] += lr[r][l]
for i in range(0,q):
    P,Q = map(int,input().split())
    ans.append(lr[Q][P])
for i in range(0,q):
    print(ans[i])

Submission status: Accepted

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

# 2次元累積和を導出
for i in range(2, N+1):
    G[i][1] += G[i-1][1]
    G[1][i] += G[1][i-1]
for i in range(2, N+1):
    for j in range(2, N+1):
        G[i][j] += G[i-1][j] + G[i][j-1] - G[i-1][j-1]

# クエリに答えていく
for q in range(Q):
    p, q = map(int, input().split())
    print(G[q][q] - G[q][p-1] - G[p-1][q] + G[p-1][p-1])

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
L=[0 for i in range(M)]
R=[0 for i in range(M)]
p=[0 for i in range(Q)]
q=[0 for i in range(Q)]
ans=[0 for i in range(Q)]
B=[[0 for i in range(N+1)] for i in range(N+1)]
C=[[0 for i in range(N+1)] for i in range(N+1)]
D=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
    L[i],R[i]=map(int,input().split())
    L[i]-=1
    R[i]-=1
for i in range(Q):
    p[i],q[i]=map(int,input().split())
    p[i]-=1
    q[i]-=1
for i in range(M):
    B[R[i]][0]+=1
    B[R[i]][L[i]+1]-=1
    B[N][0]-=1
    B[N][L[i]+1]+=1
for i in range(N+1):
    for j in range(N+1):
        if i==0:
            C[i][j]=B[i][j]
        else:
            C[i][j]=B[i][j]+C[i-1][j]
for i in range(N+1):
    for j in range(N+1):
        if j==0:
            D[i][j]=C[i][j]
        else:
            D[i][j]=C[i][j]+D[i][j-1]
for i in range(Q):
    ans[i]=D[q[i]][p[i]]

for line in ans:
    print(line)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
# import numpy as np

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

# Xi = np.zeros((N+1,N+1),dtype=np.int32)
Xi = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    Xi[L][R] += 1

# Ci = np.zeros((N+1,N+1),dtype=np.int32)
Ci = [[0]*(N+1) for i in range(N+1)]
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# print(Ci)

for r in range(N+1):
    tmp = 0
    for l in range(N+1):
        tmp += Ci[l][r]
        Ci[l][r] = tmp

# print(Ci)

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

for (p, q) in pqi:
    tmp = Ci[q][q] - Ci[q][p-1]  - Ci[p-1][q] + Ci[p-1][p-1]
    print(tmp)

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
sumsumlist = [[0 for j in range(n+1)] for i in range(n+1)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i


for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])

for (i,j) in product(range(n),range(n)):
    sumsumlist[i+1][j+1] = sum(map(lambda x:x[j+1],sumlist[0:i+1]))



for (p,q) in qs:
    ans = sumsumlist[q][q]- sumsumlist[q][p-1] -sumsumlist[p-1][q] + sumsumlist[p-1][p-1]
    print(ans)

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate, islice

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

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate, islice

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

Submission status: Accepted

Solution code:
from collections import Counter
from itertools import product

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i


for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])


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

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 l, r in (map(int, line.split()) for line in ipt[:m]):
    rails[l - 1][r - 1] += 1
rails = [list(reversed(list(accumulate(reversed(s))))) for s in zip(*(accumulate(s) for s in rails))]
print('\n'.join(str(rails[q - 1][p - 1]) for p, q in (map(int, line.split()) for line in ipt[m:])))

Submission status: Accepted

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

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

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

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

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


res = []
for _ in range(qq):
    ans = 0
    p, q = map(int, input().split())
    ans += lr[q][q] + lr[p-1][p-1] - lr[p-1][q] - lr[q][p-1]
    res.append(ans)

for row in res:
    print(row)

Submission status: Accepted

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

result = [[0] * n for _ in range(n)]
for i in range(m):
    result[0][mlist[i][1] - 1] += 1
    if mlist[i][0] < n:
        result[mlist[i][0]][mlist[i][1] - 1] -= 1

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

for i in range(q):
    print(result[qlist[i][0] - 1][qlist[i][1] - 1])

Submission status: Accepted

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

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

sumlr = [[0 for _ in range(n+1)] for _ in range(n+1)]
for l, r in ((l, r) for l in range(1, n+1) for r in range(1, n+1)):
    sumlr[l][r] = lr[l][r] + sumlr[l-1][r] + sumlr[l][r-1] - sumlr[l-1][r-1]

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

Submission status: Accepted

Solution code:
import numpy as np
n, m, q = [int(item) for item in input().split(" ")]
# n, m, q = [int(item) for item in lines[0].split(" ")]

end = np.zeros((m,2),dtype=int)
query = np.zeros((q,2),dtype=int)
for i in range(m):
    end[i] = [int(item) for item in input().split(" ")]
#     end[i] = [int(item) for item in lines[1+i].split(" ")]

for i in range(q):
    query[i] = [int(item) for item in input().split(" ")]
#     query[i] = [int(item) for item in lines[1+m+i].split(" ")]

a = np.zeros((n,n), dtype=int)
np.add.at(a, [end[:,0]-1,end[:,1]-1], 1)
b = np.cumsum(a[::-1,:], axis=0)[::-1,:]
c = np.cumsum(b, axis=1)

result = c[query[:,0]-1, query[:,1]-1]
for i in range(q):
    print(result[i])
# for item in query:
#     print(c[item[0]-1, item[1]-1])
    # print(np.sum(a[(item[0]-1):, :item[1]]))