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:
N, M, Q = map(int, input().split())
tbl = [[0] * (N + 1) for _ in range(N)]

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

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

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

for _ in range(Q):
    p, q = [int(x) - 1 for x in input().split()]
    if p == 0:
        print(tbl[q][q])
    else:
        print(tbl[q][q] - tbl[p - 1][q] - tbl[q][p - 1] + tbl[p - 1][p - 1])

Submission status: Accepted

Solution code:
import numpy as np

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

mat = np.zeros((n, n), dtype=int)

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

ans = np.cumsum(np.cumsum(mat, axis=1)[::-1], axis=0)[::-1]

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

Submission status: Accepted

Solution code:
from numpy import cumsum 
n, m, q = list(map(int, input().split()))
lst = [[0]*(n+1) for i in range(n+1)]
for i in range(m):
    l, r = list(map(int, input().split()))
    lst[l][r] += 1
ans1 = cumsum(lst, axis=1)
ans = cumsum(ans1, axis=0)
for i in range(q):
    a, b = list(map(int, input().split()))
    print(ans[b, b] - ans[a-1, b])

Submission status: Accepted

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

import sys


def main():
    n, m, q = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

    x = [[0 for j in range(n+1)] for i in range(n+1)]
    c = [[0 for j in range(n+1)] for i in range(n+1)]
    z = [[0 for j in range(n+1)] for i in range(n+1)]

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        x[l][r] += 1
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            c[i][j] = c[i][j-1] + x[i][j]

    for j in range(1, n+1):
        for i in range(1, n+1):
            z[i][j] = z[i-1][j] + c[i][j]
    
    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        print(z[qq][qq] - z[qq][qp-1] - z[qp-1][qq] + z[qp-1][qp-1])


if __name__=='__main__':
    main()

Submission status: Accepted

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


class CumSum2d(object):
    def __init__(self, H, W):
        self.H, self.W = H, W
        self.tiles = [[0] * W for _ in range(H)]

    def add(self, x, y, c=1):
        self.tiles[y][x] += c

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

    def get(self, sx, sy, tx, ty):
        assert sx <= tx and sy <= ty
        cnt = self.tiles[ty][tx]
        if sx > 0:
            cnt -= self.tiles[ty][sx - 1]
        if sy > 0:
            cnt -= self.tiles[sy - 1][tx]
        if sx > 0 and sy > 0:
            cnt += self.tiles[sy - 1][sx - 1]
        return cnt


cs = CumSum2d(N, N)
for i in range(M):
    l, r = map(int, input().split())
    cs.add(l - 1, r - 1)
cs.build()

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

Submission status: Accepted

Solution code:
n, m, q = [int(i) for i in input().split()]
L = [[int(i) for i in input().split()] for j in range(m)]
Q = [[int(i) for i in input().split()] for j in range(q)]

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

for l, r in L:
    A[l][r] += 1

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

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

for p, q in Q:
    print(A[p][q])

Submission status: Accepted

Solution code:
from collections import Counter


def bin(ll, target, key):  # リストにtargetが最初に含まれる位置
    if len(ll) < 100:
        if target in [key(a) for a in ll]:
            return [key(a) for a in ll].index(target)
        return -1

    length = len(ll)
    l, r = ll[:length // 2], ll[length // 2:]
    if key(r[0]) == target:
        if key(l[-1]) != target:
            return len(l)
        return bin(l, target, key)
    elif key(r[0]) > target:
        return bin(l, target, key)
    else:
        return len(l) + bin(r, target, key)


def main():
    n, m, q = [int(a) for a in input().split()]
    QQQ = q
    LRi = sorted([[int(a) for a in input().split()] for _ in range(m)], key=lambda it: it[0])

    PQi = [([int(a) for a in input().split()], k) for k in range(q)]
    # PQi = sorted(PQi, key=lambda a: a[0][1])
    # PQi = sorted(PQi, key=lambda a: a[0][0])

    table1 = [  # l2rの電車の個数
        [0] * n
        for _ in range(n)
    ]

    for l, r in LRi:
        table1[l - 1][r - 1] += 1

    table2 = [  # l2rの電車の個数のlに関しての累積和(iから始まってjより手前で終わる)
        [0] * n
        for _ in range(n)
    ]
    for i in range(n):
        c = 0
        for j in range(i, n):
            c += table1[i][j]
            table2[i][j] = c

    table3 = [  # 2次元累積和(iよりあとから始まってjより手前で終わる)
        [0] * n
        for _ in range(n)
    ]
    for j in range(n):
        c = 0
        for i in reversed(range(0, j + 1)):
            c += table2[i][j]
            table3[i][j] = c

    for (p, q), k in PQi:
        print(table3[p - 1][q - 1])
    return


    # TABLE = []  # iから始まる列車のRとその数
    # ii = 0
    # for i in range(1, n + 1):
    #     a = []  # iから伸びる列車の右端
    #     while True:
    #         if ii >= len(LRi):
    #             break
    #         l, r = LRi[ii]
    #         if l == i:
    #             a.append(r)
    #             ii += 1
    #         else:
    #             break
    #     # a = sorted(a)
    #     c = Counter(a)
    # 
    #     TABLE.append([(a, c[a]) for a in sorted(c.keys())])
    # 
    # TABLE2 = []  # iから始まってjまでで終わる電車TABLE[i,j]
    # for i in range(1, 1 + n):
    #     trains = TABLE[i - 1]  # iから始まる電車
    #     c = 0
    #     res = []  # jまでで終わる電車の数
    #     ccc = 0
    #     for j in range(1, n + 1):
    #         while True:
    #             if c >= len(trains):
    #                 break
    #             dst, num = trains[c]
    #             if dst <= j:
    #                 ccc += num
    #                 c += 1
    #             else:
    #                 break
    #         res.append(ccc)
    #     TABLE2.append(res)
    # 
    # for (p, q), k in PQi:
    #     c = 0
    #     for i in range(p, q + 1):
    #         c += TABLE2[i - 1][q - 1]
    #     print(c)

    # ii = 0
    # res = {}
    # while True:
    #     if ii >= len(PQi):
    #         break
    #
    #     (l, r), k = PQi[ii]# pqに対して、その範囲内のカウンタ全部取得
    #     counts = []
    #     for i in range(l, r + 1):
    #         count = TABLE[i - 1]  # タプル kまでの数v
    #         for rrrr, nnnnn in count:
    #             if rrrr <= r:
    #                 counts.append((rrrr, nnnnn))
    #             else:
    #                 break
    #     lls = [(r, k)]  # 同じlから始まるQ
    #     ii += 1
    #     while True:
    #         if ii >= len(PQi):
    #             break
    #         (ll, rr), kk = PQi[ii]
    #         if ll == r:
    #             lls.append((rr, kk))
    #             ii += 1
    #         else:
    #             break
    #
    #     lls = sorted(lls, key=lambda a: a[0])
    #     b = 0
    #     c = 0
    #     for r, k in lls:
    #         while True:
    #             if c >= len(counts):
    #                 break
    #             kk, v = counts[c]
    #             if kk <= r:
    #                 b += v
    #                 c += 1
    #             else:
    #                 break
    #         res[k] = b
    # for i in range(QQQ):
    #     print(res[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1
dp = [[0] * N for _ in range(N)]
reached = [[False] * N for _ in range(N)]
def ans(left, right):
    if reached[left][right]:
        return dp[left][right]
    elif left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        reached[left][right] = True
        return A[left][right]
    else:
        dp[left][right] = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        reached[left][right] = True
        return dp[left][right]

for q in range(Q):
    pi, qi = queries[q]
    print(ans(pi - 1, qi - 1))

Submission status: Accepted

Solution code:
N,M,Q = map(int, input().split())
train = [[0 for j1 in range(N)] for i1 in range(N)]
st = [[0 for j2 in range(N+1)] for i2 in range(N)]
s = [[0 for j3 in range(N+1)] for i3 in range(N)]

for i in range(M):
    l, r = map(int, input().split())
    train[l-1][r-1] += 1
for i in range(N):
    for j in range(N):
        st[i][j+1] = st[i][j] + train[i][j]
        
for i in range(N+1):
    s[N-1][i] = st[N-1][i]
for i in range(N-2, -1, -1):
    for j in range(N+1):
        s[i][j] = s[i+1][j] + st[i][j]
 
 
for i in range(Q):
    p, q = map(int, input().split())
    print(s[p-1][q])

Submission status: Accepted

Solution code:
from bisect import bisect_left
 
n, m, q = map(int, input().split())
LR = [0]*m
for i in range(m):
    LR[i] = list(map(int, input().split()))
P = [0]*q
Q = [0]*q
for i in range(q):
    P[i], Q[i] = map(int, input().split())
 
LR.sort(key=lambda x: (x[0], x[1]))
L = list(map(lambda x: x[0], LR))
#print(LR)
 
C = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    l = bisect_left(L, i)
    r = bisect_left(L, i+1)-1
    R2 = list(map(lambda x: x[1], LR[l:r+1]))
    #print(l, r, R2)
    for j in range(i,n+1):
        C[i][j] = bisect_left(R2, j+1)
    #print(i, C[i])
 
for i in range(q):
    ans = 0
    for j in range(P[i], Q[i]+1):
        ans += C[j][Q[i]]
    print(ans)

Submission status: Accepted

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

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1

dp = [[0] * N for __ in range(N)]
for i in range(N - 1, -1, -1):
    for j in range(i, N):
        if i == j:
            dp[i][j] = A[i][j]
        else:
            dp[i][j] = dp[i][j - 1] + dp[i + 1][j] + A[i][j] - dp[i + 1][j - 1]
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][ qi - 1])

Submission status: Accepted

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

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


D = [[0 for i in range(N+4)] for j in range(N+4)]
E = [0 for i in range(N+4)]
F = [[0 for i in range(N+4)] for j in range(N+4)]
for i in range(N+1):
	for j in range(N+1):
		D[i][j+1] = D[i][j] + C[i][j]
for i in range(N+1):
	E[i+1] = E[i] + D[i][i]
for i in range(N+2):
	for j in range(N+2):
		F[i+1][j] = F[i][j] + D[i][j]

# C[l][l] + ... + C[l][r] = D[l][r+1] - D[l][l]
# C[i][i] + ... + C[i][r] = D[i][r+1] - D[i][i]
# C[r][r] + ... + C[r][r] = D[r][r+1] - D[r][r]

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

Submission status: Accepted

Solution code:
import numpy as np

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

mat = np.zeros((n, n), dtype=int)

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
mat = np.flipud(mat)
matmul = np.cumsum(mat, axis=0)
matmul = np.flipud(matmul)
matmul2 = np.cumsum(matmul, axis=1)

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


L = [[0] * N for _ in range(N)]
for l,r in LR:
    L[l-1][r-1] += 1
for i in range(1,N):
    for j in range(N - i):
        L[j][j+i] += L[j][j+i-1] + L[j+1][i+j] - L[j+1][j+i-1]
for p,q in pq:
    print(L[p-1][q-1])

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]
src.sort(reverse=True)
qs = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(Q)]

q_arr = [[] for i in range(N)]
for i,(l,r) in enumerate(qs):
    q_arr[l].append((r,i))

bit = [0] * (N+2)
def bit_add(a,w):
    x = a
    while x <= N:
        bit[x] += w
        x += (x & -x)

def bit_sum(a):
    x = a
    ret = 0
    while x > 0:
        ret += bit[x]
        x -= (x & -x)
    return ret

ans = [None] * Q

last_l = N-1
for l,r in src:
    while last_l > l:
        for qr,qi in q_arr[last_l]:
            ans[qi] = bit_sum(qr+1)
        last_l -= 1
    bit_add(r+1, 1)
while last_l >= 0:
    for qr,qi in q_arr[last_l]:
        ans[qi] = bit_sum(qr+1)
    last_l -= 1

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

Submission status: Accepted

Solution code:
from itertools import accumulate

N,M,Q=map(int,input().split())
ST=[[0 for x in range(N+2)]for y in range(N+2)]

for i in range(M):
  s,t=map(int,input().split())
  ST[1][t]+=1
  ST[s+1][t]-=1
  ST[1][N+1]+=1
  ST[s+1][N+1]-=1

ST1 = [list(accumulate(l)) for l in zip(*ST)]
ST2 = [list(accumulate(l)) for l in zip(*ST1)]

for i in range(Q):
  s,t=map(int,input().split())
  print(ST2[s][t])

Submission status: Accepted

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

Submission status: Accepted

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

table = [[0 for _i in range(N+1)] for _j in range(N+1)]
accum = [[0 for _i in range(N+1)] for _j in range(N+1)]
accum2 = [[0 for _i in range(N+1)] for _j in range(N+1)]

for line in LR:
    table[line[0]][line[1]] += 1
# よこ
for i in range(1, N+1):
    for j in range(1, N+1):
        accum[i][j] = accum[i][j-1] + table[i][j]
# 縦
for i in range(1, N+1):
    for j in range(1, N+1):
        accum2[i][j] = accum2[i-1][j] + accum[i][j]

# for i in range(1, N+1):
#     for j in range(i, N+1):
#         ans[i][j] = sum([accum[k][j] - accum[k][i-1] for k in range(i, j+1)])

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
n, m, qqq = map(int, input().split())
DP = [[0 for _ in range(n)]for __ in range(n)]

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


#DP = [[0 for _ in range(n)]for __ in range(n)]
for i in range(n-1)[::-1]:
    for j in range(1,n):
        DP[i][j] += DP[i+1][j]+DP[i][j-1]-DP[i+1][j-1]

for i in range(qqq):
    p, q = map(int, input().split())
    print(DP[p-1][q-1])
# print(DP)

Submission status: Accepted

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

# print(LR)
# print(pq)

a=LR+pq
# print(a)
a.sort(key=lambda x:x[1])
# print(a)
b=[0]*(N+1)
ans=[]
for i in a:
    if i[2]==0:
        b[i[0]]+=1
    else:
        ans.append([sum(b[i[0]:i[1]+1]), i[3]])
    # print("b", b)
# print(ans)
ans.sort(key=lambda x:x[1])
# print(ans)
for i in ans:
    print(i[0])

Submission status: Accepted

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

LR=[None]*M
for i in range(M):
    LR[i]=list(map(int,input().split()))

pq=[None]*Q
for i in range(Q):
    pq[i]=list(map(int,input().split()))


LIST=[None]*(N+1)
for i in range(N+1):
    LIST[i]=[0 for j in range(N+1)]


for i in range(M):
    LIST[LR[i][0]][LR[i][1]]+=1

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

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

for i in range(Q):
    print(LIST[pq[i][0]][pq[i][1]])

Submission status: Accepted

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

from collections import deque
import itertools as it
import sys
import math

sys.setrecursionlimit(10000000)

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

cnt = [[0] * 550 for i in range(550)]

for loop in range(M):
    L, R = map(int, raw_input().split())
    L -= 1
    R -= 1
    cnt[L][R] += 1

for i in range(510):
    for j in range(1, 510):
        cnt[i][j] += cnt[i][j - 1]

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

for loop in range(Q):
    p, q = map(int, raw_input().split())
    p -= 1
    q -= 1
    print cnt[p][q]

Submission status: Accepted

Solution code:
import numpy as np
n,m,q = map(int,raw_input().split())

imos = [[0 for i in xrange(n)] for j in xrange(n)]

for i in xrange(m):
	f,t = map(int,raw_input().split())
	f -= 1
	t -= 1
	imos[f][t] += 1

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

for i in xrange(n):
	imos[i] = np.cumsum(imos[i])

for i in xrange(q):
	a,b = map(int,raw_input().split())
	print imos[a-1][b-1]

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())		# 5 7 2

A=[]	# (l,r)をそのまま保持
B=[]	# (l,r,n) lからrまでの本数nを保持, B[l][r]=n

for i in range(N+1):
	a=[0]*(N+1)
	B.append(a)

for i in range(M):
	l, r = map(int, input().split())		# 5 7
	A.append( (l,r) )
	B[l][r]+=1

#print("A", A)
#print("B", B)

for iR in range(1,N+1):
	for iC in range(1,N+1):
		B[iR][iC] += B[iR][iC-1]

for iC in range(1,N+1):
	for iR in range(iC, 1, -1):
		B[iR-1][iC] += B[iR][iC]


#print("B", B)


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

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split());
L = [];
R = [];

for i in range(M):
    Lnew, Rnew = map(int, input().split());
    L.append(Lnew);
    R.append(Rnew);

p = [];
q = [];

for i in range(Q):
    pnew, qnew = map(int, input().split());
    p.append(pnew);
    q.append(qnew);


trainList = [0] * (N**2);
ansList   = [0] * (N**2);

for i in range(M):
    trainList[(R[i]-L[i])*N+(L[i]-1)]+=1;

for i in range(N**2):
    if(i<N):
        ansList[i]=trainList[i];
    elif(i<N*2):
        ansList[i]=trainList[i]+ansList[i-N]+ansList[i-N+1];
    else:
        ansList[i]=trainList[i]+ansList[i-N]+ansList[i-N+1]-ansList[i-2*N+1];

for i in range(Q):
    ln=q[i]-p[i];
    print(ansList[ln*N+p[i]-1]);

Submission status: Accepted

Solution code:
def main():
    n, m, q = [int(i) for i in raw_input().strip().split()]
    f = [[0 for j in xrange(n)] for i in xrange(n)]
    for i in xrange(m):
        l, r = [int(i) - 1 for i in raw_input().strip().split()]
        f[l][r] += 1
    for d in xrange(1, n):
        for i in xrange(0, n - d):
            f[i][i + d] += f[i][i + d - 1] + f[i + 1][i + d] - f[i + 1][i + d - 1]
    for i in xrange(q):
        p, q = [int(i) - 1 for i in raw_input().strip().split()]
        print f[p][q]

if __name__ == '__main__':
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

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

Ass = [list(accumulate(Ts)) for Ts in Tss]

Bss = [[0] * N for i in range(N)]
for j in range(N):
    Bss[N - 1][j] = Ass[N - 1][j]
    for i in reversed(range(N - 1)):
        Bss[i][j] = Bss[i + 1][j] + Ass[i][j]

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

Submission status: Accepted

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

    city[1][r] += 1
    city[l+1][r] -= 1
    if l==r:
        same[l] += 1

"""
print()
for c in city[1:n+1]:
    print(c[1:n+1])
"""

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

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

"""
print()
for c in city[1:n+1]:
    print(c[1:n+1])
"""

for _ in range(q):
    x, y = map(int, input().split())
    if x==y:
        print(same[x])
    else:
        print(city[x][y])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,q=map(int, input().split())
lr=[list(map(int,input().split())) for _ in range(m)]
pq=[list(map(int,input().split())) for _ in range(q)]
x=[[0 for _ in range(n)] for _ in range(n)]
for t in lr:
    x[t[0]-1][t[1]-1]+=1
for i in range(n):
    k=False
    for j in range(n):
        if k:
            x[i][j]+=x[i][j-1]
        elif x[i][j]>0:
            k=True
            
for i in range(n-1,0,-1):
    for j in range(n-1,-1,-1):
        x[i-1][j]+=x[i][j]
for t in pq:
    print(x[t[0]-1][t[1]-1])

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N, M, Q = reads()

mat = [[0] * N for _ in range(N)]
for _ in range(M):
  l, r = reads()
  l, r = l-1, r-1
  mat[l][r] += 1

acc = [[0] * (N+1) for _ in range(N+1)]
for i, j in product(range(N), range(N)):
  acc[i+1][j+1] = acc[i][j+1] + acc[i+1][j] - acc[i][j] + mat[i][j]

for _ in range(Q):
  p, q = reads()
  p, q = p-1, q-1
  ans = acc[N][q+1] - acc[p][q+1]
  print(ans)

Submission status: Accepted

Solution code:
imos = [[0 for j in range(501)]for i in range(501)]
query = []
N,M,Q = map(int,input().split())
for i in range(M):
    L,R = map(int,input().split())
    imos[L][R] += 1
for i in range(Q):
    p,qq = map(int,input().split())
    query.append([p,qq])
for i in range(501):
    for j in range(1,501):
        imos[i][j] += imos[i][j-1]
for i in range(501):
    for j in range(1,501):
        imos[i][j] += imos[i-1][j]
for q in query:
    print(imos[N][q[1]]-imos[q[0]-1][q[1]])

Submission status: Accepted

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

x = [[0 for i in range(n)] for j in range(n)]

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

for j in range(1, n):
    for k in range(n-j):
        x[k][j+k] += x[k][j+k-1] + x[k+1][j+k] - x[k+1][j+k-1]

y = []
for i in range(q):
    a, b = map(int, input().split())
    y.append(x[a-1][b-1])
    
for i in range(q):
    print(y[i])

Submission status: Accepted

Solution code:
import sys

def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M, Q] = [long(input_raw[0]), long(input_raw[1]), long(input_raw[2])]
    table = [[0 for i in range(N+1)] for i in range(N+1)]
    
    for i in range(M):
        input_raw = read_func().strip().split()
        [L, R] = [long(input_raw[0]), long(input_raw[1])]
        table[L][R] += 1;

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

    for i in range(Q):
        input_raw = read_func().strip().split()
        [p, q] = [long(input_raw[0]), long(input_raw[1])]
        print table[p][q]

if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

A = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    l,r = L[i],R[i]
    A[r][0] += 1
    A[r][l+1] -= 1
    A[N][0] -= 1 
    A[N][l+1] += 1

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

for i in range(X):
    p,q = P[i],Q[i]
    print(A[q][p])

Submission status: Accepted

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

train = [[0 for j1 in range(N)] for i1 in range(N)]
st = [[0 for j2 in range(N+1)] for i2 in range(N)]
s = [[0 for j3 in range(N+1)] for i3 in range(N)]


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

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

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


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


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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



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



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

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

#l=[]
#r=[]

A=[[0 for i in range(n)] for j in range(n)]
for _ in range(m):
    a,b= list(map(int,input().split()))
#    print(a,b)
#    l.append(a)
#    r.append(b)
    A[a-1][b-1]+=1

#print("A",A)
ruiseki=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(n):
#        print(i,j)
        ruiseki[i][j+1]=ruiseki[i][j] +ruiseki[i-1][j+1] - ruiseki[i-1][j] + A[i-1][j]

#print("R",ruiseki)        

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


#print(p,q)

for i in range(Q):
    print(ruiseki[q[i]+1][q[i]+1] - ruiseki[p[i]][q[i]+1] - ruiseki[q[i]+1][p[i]] + ruiseki[p[i]][p[i]])


#if :
#    print("Yes")
#else:
#    print("No")

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

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

m = [[0] * N for _ in range(N)]
for i in range(N):
  rowsum = 0
  for j in range(N):
    rowsum += ct[i][j]
    m[i][j] = rowsum
    if i > 0:
      m[i][j] += m[i-1][j]

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

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(int(1e9))

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

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

H, W = (501, 501)
for i in range(H):
    for j in range(1, W):
        cnt[i][j] = cnt[i][j] + cnt[i][j-1]

for j in range(W):
    for i in range(1, H):
        cnt[i][j] = cnt[i][j] + cnt[i-1][j]

def Sum(l, r):
    return cnt[r][r] - cnt[l][r] - cnt[r][l] + cnt[l][l]

for i in range(Q):
    l, r = list(map(int, input().split()))
    ans = Sum(l-1, r)
    print(ans)