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: Time Limit Exceeded

Solution code:
'''
    N  都市　西から順に1,2,3...N
    M　列車の数
    Q　質問の数
    L, R 列車iが走行する都市の区間
    p, q 都市pから都市qまでの区間に、走る区間が完全に含まれている
    　　　列車の数を問う
'''

def logic(N, M, Q, L, R, p, q):
    train_map = [[0 for __ in range(N)] for __ in range(N)]
    ret = []
    for lr in range(M):
        train_map[L[lr] - 1][R[lr] - 1] += 1
    for pq in range(Q):
        count = 0
        for sCalc in range(p[pq] - 1, q[pq]):
            count += sum(train_map[sCalc][p[pq]-1:q[pq]])
        ret.append(count)
    return ret

def main():
    N, M, Q = map(int, input().split())
    L, R, p, q = [], [], [], []
    for __ in range(M):
        LR = list(map(int, input().split()))
        L.append(LR[0])
        R.append(LR[1])
    for __ in range(Q):
        pq = list(map(int, input().split()))
        p.append(pq[0])
        q.append(pq[1])
    ret = logic(N, M, Q, L, R, p, q)
    [print(st) for st in ret]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
'''
    N  都市　西から順に1,2,3...N
    M　列車の数
    Q　質問の数
    L, R 列車iが走行する都市の区間
    p, q 都市pから都市qまでの区間に、走る区間が完全に含まれている
    　　　列車の数を問う
'''

def logic(N, M, Q, L, R, p, q):
    ret = []
    for pq in range(len(p)):
        count = 0
        for lr in range(len(L)):
            if p[pq] <= L[lr] and R[lr] <= q[pq]:
                count += 1
        ret.append(count)
    return ret


def main():
    N, M, Q = map(int, input().split())
    L, R, p, q = [], [], [], []
    for __ in range(M):
        LR = list(map(int, input().split()))
        L.append(LR[0])
        R.append(LR[1])
    for __ in range(Q):
        pq = list(map(int, input().split()))
        p.append(pq[0])
        q.append(pq[1])
    ret = logic(N, M, Q, L, R, p, q)
    [print(st) for st in ret]


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = np.zeros((city_count + 1, city_count + 1), np.int_)

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

    city_list.cumsum(1, out=city_list)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = np.zeros((city_count + 1, city_count + 1), np.uint32)

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

    np.cumsum(city_list, 1, out=city_list)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from array import array
from itertools import accumulate, islice, repeat
from operator import itemgetter


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [array('L', repeat(0, city_count + 1))
                 for _ in range(city_count + 1)]

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

    for city_index in range(1, city_count + 1):
        city_list[city_index] = array('L', accumulate(city_list[city_index]))

    for _ in range(query_count):
        p, q = map(int, input().split())
        print(sum(map(itemgetter(q), islice(city_list, p, q + 1))))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from array import array
from itertools import islice, repeat


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [array('L', repeat(0, city_count + 1))
                 for _ in range(city_count + 1)]

    for express_index in range(1, express_count + 1):
        l, r = map(int, input().split())
        city_list[l][r] += 1

    for _ in range(query_count):
        p, q = map(int, input().split())
        answer = 0
        for left_index, right_list in enumerate(islice(city_list, p, q + 1), p):
            answer += sum(islice(right_list, left_index, q + 1))
        print(answer)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import islice


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [[[], []] for _ in range(city_count + 1)]

    for express_index in range(1, express_count + 1):
        l, r = map(int, input().split())
        for city in islice(city_list, 1, l + 1):
            city[0].append(express_index)
        for city in islice(city_list, r, None):
            city[1].append(express_index)

    for city in city_list:
        city[0] = frozenset(city[0])
        city[1] = frozenset(city[1])

    for _ in range(query_count):
        p, q = map(int, input().split())
        city_p = city_list[p][0]
        city_q = city_list[q][1]
        print(len(city_p & city_q))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import islice


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = [(set(), set()) for _ in range(city_count + 1)]

    for express_index in range(1, express_count + 1):
        l, r = map(int, input().split())
        for city in islice(city_list, 1, l + 1):
            city[0].add(express_index)
        for city in islice(city_list, r, None):
            city[1].add(express_index)

    for _ in range(query_count):
        p, q = map(int, input().split())
        city_p = city_list[p][0]
        city_q = city_list[q][1]
        print(len(city_p & city_q))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

a = [[0 for i in range(509)] for j in range(509)]
sum = [[0 for i in range(509)] for j in range(509)]
ans = [[0 for i in range(509)] for j in range(509)]

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

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

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

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

Submission status: Time Limit Exceeded

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

a = [[0 for i in range(509)] for j in range(509)]
sum = [[0 for i in range(509)] for j in range(509)]

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

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

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

Submission status: Time Limit Exceeded

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

a = [[0 for i in range(509)] for j in range(509)]
sum = [[0 for i in range(509)] for j in range(509)]

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

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

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

Submission status: Time Limit Exceeded

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

trains = []
for train in range(M):
  trains.append(list(map(int, input().split())))

cities = []
for city in range(Q):
  cities.append(list(map(int, input().split())))

a = [[0 for i in range(509)] for j in range(509)]
sum = [[0 for i in range(509)] for j in range(509)]

for t in trains:
  L = t[0]
  R = t[1]
  a[L][R] += 1

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

for c in cities:
  p = c[0]
  q = c[1]
  ans = 0
  for i in range(p,q+1):
    ans += sum[i][q] - sum[i][p-1]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int,input().split(" "))
LR_2d = [[0 for i in range(n)] for i in range(n)]
for i in range(m):
    L,R = map(int,input().split(" "))
    LR_2d[L-1][R-1] += 1
LR_2dsum = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    LR_2dsum[i][0] = LR_2d[i][0]
    for j in range(1,n):
        LR_2dsum[i][j] = LR_2dsum[i][j-1] + LR_2d[i][j]
for i in range(q):
    ans = 0
    p_i,q_i = map(int,input().split(" "))
    for j in range(p_i-1,q_i):
        if p_i == 1:
            ans_j = LR_2dsum[j][q_i-1]
        else:
            ans_j = LR_2dsum[j][q_i-1] - LR_2dsum[j][p_i-2]
        ans += ans_j
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int,input().split(" "))
LRs =[]
for i in range(m):
    LR_i = list(map(int,input().split(" ")))
    LRs.append(LR_i)
for i in range(q):
    ans = 0
    p_i,q_i = map(int,input().split(" "))
    for j in LRs:
        if p_i <= j[0] and j[1] <= q_i:
            ans = ans + 1
    print(ans)

Submission status: Time Limit Exceeded

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

towns=[[0 for x in range(N+1)] for y in range(N+1)]
for i in range(M):
	towns[train[i][0]][train[i][1]] +=1

for j in range(Q):
	count = 0
	for k in range(quest[j][1]-quest[j][0]+1):
		for l in range(quest[j][1]-quest[j][0]+1):
			count += towns[quest[j][0]+k][quest[j][0]+l]
	print(count)

Submission status: Time Limit Exceeded

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

for j in range(Q):
	quest.append(list(map(int, input().split())))

for j in range(Q):
	count = 0
	for i in range(M):
		if quest[j][0]<=train[i][0] and train[i][1]<=quest[j][1]:
			count += 1
	print(count)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,raw_input().split())
a = []
for i in range(M):
  b = map(int,raw_input().split())
  a.append(b)
for i in range(Q):
  c,d = map(int,raw_input().split())
  x = 0
  for j in range(M):
    e = a[j]
    if c <= int(e[0]) and d >= int(e[1]):
      x += 1
  print x

Submission status: Time Limit Exceeded

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

nl = [[0 for i in range(N)] for j in range(N)]
for t in [input().split() for _ in range(M)]:
    i = int(t[0]) - 1
    j = int(t[1]) - 1
    nl[i][j] += 1

l = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    s = 0
    for j in range(N):
        l[i][j] = s + nl[i][j]
        s = l[i][j]

for k in [input().split() for _ in range(Q)]:
    p = int(k[0])
    q = int(k[1])
    ans = 0
    for i in range(p-1, q):
        if p == 1:
            d = l[i][q-1]
        else:
            d = l[i][q-1] - l[i][p-2]
        ans += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = [int(_) for _ in input().split()]
train = [[int(_) for _ in input().split()] for i in range(M)]
question = [[int(_) for _ in input().split()] for i in range(Q)]

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

l = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    s = 0
    for j in range(N):
        l[i][j] = s + nl[i][j]
        s = l[i][j]

for k in range(Q):
    p = question[k][0]
    q = question[k][1]
    ans = 0
    for i in range(p-1, q):
        if p == 1:
            d = l[i][q-1]
        else:
            d = l[i][q-1] - l[i][p-2]
        ans += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = [int(_) for _ in input().split()]
train = [[int(_) for _ in input().split()] for i in range(M)]
question = [[int(_) for _ in input().split()] for i in range(Q)]

l = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    s = 0
    for j in range(N):
        if i >= j:
            a = train.count([j+1, i+1])
        else:
            a = train.count([i+1, j+1])
        l[i][j] = s + a
        s += a

for k in range(Q):
    p = question[k][0]
    q = question[k][1]
    ans = 0
    for i in range(p-1, q):
        if i == 0:
            d = l[i][q-1]
        else:
            d = l[i][q-1] - l[i][i-1]
        ans += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = [int(_) for _ in input().split()]
train = [[]] * M
question = [[]] * Q
for i in range(M):
    train[i] = [int(_) for _ in input().split()]
for i in range(Q):
    question[i] = [int(_) for _ in input().split()]

l = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    s = 0
    for j in range(N):
        if i >= j:
            a = train.count([j+1, i+1])
        else:
            a = train.count([i+1, j+1])
        l[i][j] = s + a
        s += a

for k in range(Q):
    p = question[k][0]
    q = question[k][1]
    ans = 0
    for i in range(p-1, q):
        if i == 0:
            d = l[i][q-1]
        else:
            d = l[i][q-1] - l[i][i-1]
        ans += d
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = [int(_) for _ in input().split()]
train = [[]] * M
question = [[]] * Q
for i in range(M):
    train[i] = [int(_) for _ in input().split()]
for i in range(Q):
    question[i] = [int(_) for _ in input().split()]

l = []
for i in range(N):
    s = 0
    l2 = []
    for j in range(N):
        if i >= j:
            a = train.count([j+1, i+1])
        else:
            a = train.count([i+1, j+1])
        l2.append(s + a)
        s += a
    l.append(l2)

for k in range(Q):
    p = question[k][0]
    q = question[k][1]
    ans = 0
    for i in range(p-1, q):
        if i == 0:
            d = l[i][q-1]
        else:
            d = l[i][q-1] - l[i][i-1]
        ans += d
    print(ans)

Submission status: Time Limit Exceeded

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

LR = np.array([np.zeros(N+2-i, dtype=np.int) for i in range(N+2)])
for i in range(M):
  L, R = map(int, input().split())
  LR[L][R-L+1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
# あらかじめ全ての区間における答えを求めておく
# 累積和が使える。
# p,qの値に関しての2次元座標系で考えると、値が存在するマスは限られてる
#
#
n, m, q = map(int, input().split())
ll = [[0, 0] for i in range(m)]
p = [[0, 0] for i in range(q)]
for i in range(m):
    ll[i][0], ll[i][1] = map(int, input().split())
for i in range(q):
    p[i][0], p[i][1] = map(int, input().split())
# for i in range(m):
#     print(ll[i])
# for i in range(q):
#     print(p[i])
sum = [[0 for i in range(n)] for i in range(n)]
# sum上でlをy成分＝行、rをx成分=列とする。
for j in range(m):
    y = ll[j][0]-1
    x = ll[j][1]-1
    sum[y][x] += 1
ans = [[0 for i in range(n)] for i in range(n)]
for i in range(n):
    for j in range(i, n):
        for i2 in range(i, j+1):
            for j2 in range(i, j+1):
                ans[i][j] += sum[j2][i2]

for i in range(q):
    y = p[i][0]-1
    x = p[i][1]-1
    print(ans[y][x])

Submission status: Time Limit Exceeded

Solution code:
# あらかじめ全ての区間における答えを求めておく
# 累積和が使える。
# p,qの値に関しての2次元座標系で考えると、値が存在するマスは限られてる

n, m, q = map(int, input().split())
ll = [[0, 0] for i in range(m)]
p = [[0, 0] for i in range(q)]
for i in range(m):
    ll[i][0], ll[i][1] = map(int, input().split())
for i in range(q):
    p[i][0], p[i][1] = map(int, input().split())

sum = [[0 for i in range(n)] for i in range(n)]
for j in range(m):
    y = ll[j][0]-1
    x = ll[j][1]-1
    sum[y][x] += 1

for i in range(q):
    ans = 0
    for j in range(p[i][0]-1, p[i][1]):
        for k in range(p[i][0]-1, p[i][1]):
            ans += sum[k][j]
    print(ans)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
N, M , Q = map(int, input().split())

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

for i in range(Q):
  p, q = map(int, input().split())
  S = 0
  for l,R in LR.items():
    if not p <= l <= q: continue
    for r,s in R.items():
      if q < r: continue
      S += s
  print(S)

Submission status: Time Limit Exceeded

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

LR = {}
for i in range(M):
  L, R = map(int, input().split())
  if L in LR:
    LR[L].append(R)
  else:
    LR[L] = [R]

for r in LR.values():
  r.sort()

for i in range(Q):
  p, q = map(int, input().split())
  s = 0
  for l,r in LR.items():
    if not p <= l <= q: continue
    for j in r:
      if q < j: break
      s += 1
  print(s)

Submission status: Time Limit Exceeded

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

LR = {}
for i in range(M):
  L, R = map(int, input().split())
  if L in LR:
    LR[L].append(R)
  else:
    LR[L] = [R]

for r in LR.values():
  r.sort()

for i in range(Q):
  p, q = map(int, input().split())
  s = 0
  for i in range(p,q+1):
    if i not in LR: continue
    for j in LR[i]:
      if q < j: break
      s += 1
  print(s)

Submission status: Time Limit Exceeded

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

LR = []
for i in range(M):
  L, R = map(int, input().split())
  LR.append((L, R))

for i in range(Q):
  p, q = map(int, input().split())
  print(sum(1 for l,r in LR if p<=l and r<=q))

Submission status: Time Limit Exceeded

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

accl = [0]*(N)
accr = [0]*(N)

for i in range(M):
    l,r = lr[i]
    accl[(l-1)] = (accl[(l-1)] | (1 << i))
    accr[(r-1)] = (accr[(r-1)] | (1 << i))

for i in range(N-1):
    accl[N-i-2] |= accl[N-i-1]
    accr[i+1] |= accr[i]

for i in range(Q):
    p,q = map(int,input().split(" "))
    s1,s2 = accl[p-1],accr[q-1]
    s = s1 & s2
    print(bin(s).count("1"))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = [int(_) for _ in input().split()]
train = [[]] * M
question = [[]] * Q
for i in range(M):
    train[i] = [int(_) for _ in input().split()]
for i in range(Q):
    question[i] = [int(_) for _ in input().split()]

l = []
for i in range(Q):
    counter = 0
    p = question[i][0]
    q = question[i][1]
    for j in range(M):
        if p <= train[j][0] and train[j][1] <= q:
            counter += 1
    l.append(counter)

for i in range(Q):
    print(l[i])

Submission status: Time Limit Exceeded

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

for k, l in pq:
    cnt = 0
    for m, n in LR:
        if k <= m and n <= l:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from functools import reduce
import numpy as np

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

dist = np.zeros((N,N), dtype=int)

for m in range(M):
  L, R = map(lambda x: int(x)-1, input().split())
  for i in range(R, N):
    dist[L][i] += 1

for _ in range(Q):
  p, q = map(lambda x: int(x)-1, input().split())
  print(reduce(lambda s, i: s + dist[i][q], range(p, q+1), 0))

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int, input().split()))
 
p = [list(map(int, input().split())) for i in range(a[1])]
q = [list(map(int, input().split())) for i in range(a[2])]
 
res = [[0]*a[0] for i in range(a[0])]
 
def lsadd(L,R):
    L-=1
    R-=1
    for i in range(0,L+1):  
        res[i][R] += 1
 
for l,r in p:
    lsadd(l,r)
 
for l,r in q:
    print(sum(res[l-1][:r]))

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))

k = [[0 for i in range(a[0])] for j in range(a[0])]

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

for i in range(a[2]):
    p = 0
    m,n = map(int,input().split())
    for j in range(m-1,n):
        for l in range(j,n):
            p += k[j][l]
    print(p)

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))

c = [[0 for i in range(a[0]+1)] for j in range(a[0]+1)]

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

d = [[0 for i in range(a[0]+4)] for j in range(a[0]+4)]

for i in range(a[0]+1):
    for j in range(a[0]+1):
        d[i][j+1] = d[i][j] + c[i][j]

for i in range(a[2]):
    n,m = map(int,input().split())
    s = 0
    for j in range(n,m+1):
        s += d[j][m+1] - d[j][j]
    print(s)

Submission status: Time Limit Exceeded

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

train = []
for i in range(0, N):
	train.append([])
for i in range(0, M):
	L, R = map(int, raw_input().split())
	train[L-1].append(R)
for i in range(0, N):
	train[i-1].sort()

counter = []
for i in range(0, N):
	lst = []
	for j in range(0, N):
		lst.append(0)
	for j in range(0, len(train[i])):
		lst[train[i][j]-1] = lst[train[i][j]-1] + 1
	for j in range(1, len(lst)):
		lst[j] = lst[j-1] + lst[j]
	counter.append(lst)

for i in range(0, Q):
	p, q = map(int, raw_input().split())
	cnt = 0
	for j in range(p-1, q):
		cnt = cnt + counter[j][q-1]
	print cnt

Submission status: Time Limit Exceeded

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

train = []
for i in range(0, N):
	train.append([])
for i in range(0, M):
	L, R = map(int, raw_input().split())
	train[L-1].append(R)
for i in range(0, N):
	train[i-1].sort()

counter = []
for i in range(0, N):
	lst = []
	for j in range(0, N):
		lst.append(0)
	for j in range(0, len(train[i])):
		lst[train[i][j]-1] = lst[train[i][j]-1] + 1
	counter.append(lst)

for i in range(0, Q):
	p, q = map(int, raw_input().split())
	cnt = 0
	for j in range(p-1, q):
		for k in range(j, q):
			cnt = cnt + counter[j][k]
	print cnt

Submission status: Time Limit Exceeded

Solution code:
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)]

for i in range(Q):
    ans = 0
    for j in range(M):
        ans += PQ[i][0] <= LR[j][0] and LR[j][1] <= PQ[i][1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = list(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)]
for i in range(M):
  L[i], R[i] = list(map(int, input().split()))
for i in range(Q):
  p[i], q[i] = list(map(int, input().split()))

for i in range(Q):
  count = 0
  for j in range(M):
    if p[i] <= L[j] and R[j] <= q[i]:
      count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:

def solve(s,e):
	res=0
	for i in range(s,e+1):
		res+=train[i][e]-train[i][s-1]
	return res

city,dnum,qnum=map(int,input().split())

train=[[0 for i in range(city+1)] for i in range(city+1)]

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

for i in range(city+1):
	tmp=0
	for j in range(city+1):
		tmp+=train[i][j]
		train[i][j]=tmp
		
	
querry=[list(map(int,input().split())) for i in range(qnum)]

for q in querry:
	print(solve(*q))

Submission status: Time Limit Exceeded

Solution code:
train_list = []
town_pair_list = []
# 答えになる
train_counter_list = []

# 以下入力処理
max_town_num, train_num, q_num = list(map(int, input().split()))

for _ in range(train_num):
    train_list.append(list(map(int, input().split())))

for _ in range(q_num):
    town_pair_list.append(list(map(int, input().split())))


# 街のペア毎に調べていく
for town_pair in town_pair_list:
    counter = 0
    for check_num in range(train_num):
        if town_pair[0] <= train_list[check_num][0] <= town_pair[1] \
                and town_pair[0] <= train_list[check_num][1] <= town_pair[1]:
            counter += 1
    train_counter_list.append(counter)

# 出力
for _ in range(q_num):
    print(train_counter_list[_])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
#グリッド
grid = [[0 for i in range(N)] for j in range(N)]
#列車の情報
for i in range(M):
    L,R = map(int,input().split())
    grid[L-1][R-1] += 1
#クエリ
q = [[0,0] for i in range(Q)]
for i in range(Q):
    q[i][0],q[i][1] = map(int,input().split())

#検索
for i in range(Q):
    s = 0
    for j in range(q[i][0]-1,q[i][1]):
        for k in range(q[i][0]-1,q[i][1]):
            s += grid[j][k]
    print(s)

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))

k = [[0 for i in range(a[0])] for j in range(a[0])]

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

for i in range(a[2]):
    p = 0
    m,n = map(int,input().split())
    for j in range(m-1,n):
        for l in range(j,n):
            p += k[j][l]
    print(p)

Submission status: Time Limit Exceeded

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

for j in range(Q):
    cnt = 0
    p, q = map(int, input().split())
    for i in range(M):
        if p <= L[i] and R[i] <= q:
            cnt += 1
        else:
            pass
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
lis = []
ris = []
for i in range(m):
    li, ri = map(int, input().split())
    lis.append(li)
    ris.append(ri)
pis = []
qis = []

for i in range(q):
    pi, qi = map(int, input().split())
    pis.append(pi)
    qis.append(qi)

for (pi, qi) in zip(pis, qis):
    total = 0
    for (li, ri) in zip(lis, ris):
        if pi <= li and ri <= qi:
            total += 1
    print(total)

Submission status: Time Limit Exceeded

Solution code:

N,M,Q=map(int,input().split())
list1=[]
for i in range(N+1):
    list2=[]
    for j in range(N+1):
        list2.append(0)
    list1.append(list2)
#print(list1)
list3=list1
for k in range(M):
    s,g=map(int,input().split())
    list1[s][g]+=1
#print(list1)
for l in range(1,N+1):
    for o in range(N+1):
        list3[l][o]=list3[l-1][o]+list1[l][o]
#print(list3)
for m in range(Q):
    s,g=map(int,input().split())
    ans=0
    for n in range(s-1,g+1):
        ans+=list3[g][n]-list3[s-1][n]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def solve(s,e):
	return np.sum(train[s:e+1,s:e+1])

city,dnum,qnum=map(int,input().split())

train=np.zeros((city+1,city+1),dtype='int16')


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

for q in querry:
	print(solve(*q))

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
d=[[0 for i in range(n)]for I in range(n)]

for i in range(m):
    l,r=map(int,input().split())
    d[r-1][l-1]+=1
#print(d)
pq=[list(map(int,input().split()))for i in range(q)]
for i in pq:
    print(sum([sum(d[I][i[0]-1:]) for I in range(i[1])]))

Submission status: Time Limit Exceeded

Solution code:
def solve(s,e):
	res=0
	for i in range(s,e+1):
		for j in range(s,e+1):
			res+=train[i][j]
	return res

city,dnum,qnum=map(int,input().split())

train=[[0 for i in range(city+1)] for i in range(city+1)]

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

for q in querry:
	print(solve(*q))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
X = np.zeros((N, N), dtype=int)
ends = np.zeros((M, 2), dtype=int)
queries = np.zeros((Q, 2), dtype=int)
for i in range(M):
    ends[i] = [int(item) for item in input().split()]
for i in range(Q):
    queries[i] = [int(item) for item in input().split()]
np.add.at(X, [ends[:,0] - 1, ends[:, 1] - 1], 1)
for items in queries:
    print(np.sum(X[items[0] - 1:items[1], items[0] - 1:items[1]]))

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M, Q = map( int, input().split())
NN = [ [ 0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L, R = map( int, input().split())
    NN[L][R] += 1
Sum = [ [ 0 ] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        Sum[i].append(Sum[i][-1]+NN[i][j])
for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p,q+1):
        ans += Sum[i][q] - Sum[i][p-1]
    print(ans)