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 , M , Q = [int(i) for i in input().split()]
table = [[0 for j in range(N)] for i in range(N)]

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

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

Submission status: Time Limit Exceeded

Solution code:
inputs = raw_input().replace("\n", "")
N, M, Q = map(int, inputs.split(" "))

m_inputs = []
for i in xrange(M):
    inputs = raw_input().replace("\n", "")
    L, R = map(int, inputs.split(" "))
    m_inputs.append([L, R])

q_inputs = []
for i in xrange(Q):
    inputs = raw_input().replace("\n", "")
    p, q = map(int, inputs.split(" "))
    q_inputs.append([p, q])

for q_input in q_inputs:
    p, q = q_input
    count = 0
    for m_input in m_inputs:
        L, R = m_input
        if p <= L and R <= q:
            count += 1
    print count

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

A = np.zeros((N, N))

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

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

Submission status: Time Limit Exceeded

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)]
trains.sort(key = lambda x: x[1])

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

def ans(left, right):
    if dp[left][right] > 0:
        return dp[left][right]
    elif left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        return A[left][right]
    else:
        x = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        dp[left][right] = x
        return x

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
L = []
R = []
ANS = []
for i in range(M) :
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
for j in range(Q) :
    p,q = map(int,input().split())
    ans = 0
    for k in range(len(L)) :
        if p <= L[k] and R[k] <= q :
            ans += 1
    ANS.append(ans)
for z in range(len(ANS)) :
    print(ANS[z])

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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

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

for i in range(m):
    l, r = map(int, input().split())
    for j in range(0, l):
        for k in range(r-1, n):
            ans[j][k]+=1
            
ope=[]
            
for i in range(q):
    l, r = map(int, input().split())
    ope.append([l-1, r-1])
    
for i in range(q):
    print(ans[ope[i][0]][ope[i][1]])

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M, Q = [int(i) for i in input().strip().split(' ')]

flag  = False
Ls = []
Rs = []
counter = M

d = []
for i in range(N):
    d.append([0] * N)


for line in sys.stdin:
    L, R = [int(i) for i in line.strip().split(' ')]
    if not flag:
        for i in range(L):
            for j in range(N - R + 1):
                d[i][R + j - 1] += 1
        counter -= 1
        if counter == 0:
            flag = True
    else:
        print(d[L-1][R-1])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict
import bisect


def solve():
    n, m, q = map(int, input().split())
    d = defaultdict(list)
    for i in range(m):
        l, r = map(int, input().split())
        bisect.insort_left(d[l], r)
    table = [[0 for i in range(n + 1)] for j in range(n + 1)]
    dk = [p for p in d.keys()]
    dk.sort()
    for i in range(1, n + 1):
        ri = bisect.bisect_left(dk, i)
        dk = dk[ri:]
        if not dk:
            break
        for j in range(1, n + 1):
            tans = 0
            for k in [p for p in dk if p <= j]:
                tans += bisect.bisect_right(d[k], j)
            table[i][j] = tans
    for i in range(q):
        l, r = map(int, input().split())
        print(table[l][r])


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

for i in question:
    print(len([j for j in LR if i[0] <= j[0] and i[1] >= j[1]]))

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
ab=[]
for _ in range(M):
    ab.append(tuple(map(int, input().split())))
ab.sort()

for j in range (Q):
    count=0
    l,r= map(int,input().split())
    for a,b in ab:
        if a>=l and b<=r:
            count+=1
    print  (count)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
lr=[list(map(int,input().split())) for i in range(0,m)]
pq=[list(map(int,input().split())) for i in range(0,q)]
print("\n".join([str(sum([1 for i in lr if x[0]<=i[0] and x[1]>=i[1]]))for x in pq]))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int,input().split())
L_list = [0 for _ in range (M)]
R_list = [0 for _ in range (M)]
p_list = [0 for _ in range (Q)]
q_list = [0 for _ in range (Q)]

for m in range (M):
    L_list[m], R_list[m] = map(int,input().split())
    
new_L_list = list(zip(L_list,range(M)))
new_R_list = list(zip(R_list,range(M)))
new_L_list.sort(key=lambda x:x[0])
new_R_list.sort(key=lambda x:x[0])
new_LR_list = list(zip(L_list,R_list,range(M)))
new_LR_list.sort(key=lambda x:x[0])

for q in range (Q):
    p_list[q], q_list[q] = map(int,input().split())


for q in range (Q):
    ans = 0
    for m in range(M):
        if p_list[q] <= new_LR_list[m][0] and new_LR_list[m][1]<= q_list[q]:
             ans +=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
inp = input().split()
n = int(inp[0])
m = int(inp[1])
q = int(inp[2])
lr = [input() for _ in range(m)]
pq = [input() for _ in range(q)]
count = 0

for i in pq:
  i = i.split()
  p = int(i[0])
  q = int(i[1])
  for j in lr:
    j = j.split()
    l = int(j[0])
    r = int(j[1])
    if p <= l and r <= q:
      count += 1
  print(count)
  count = 0

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M,Q = (int(i) for i in input().split())

L = np.zeros(M)
R = np.zeros(M)
p = np.zeros(Q)
q = np.zeros(Q)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""
import bisect
n, m, qn = list(map(int, input().split()))

l= []
r = []
lr = []
p = []
q = []

for i in range(m):
    lri = list(map(int, input().split()))
    lr.append(lri)
    l.append(lri[0])
    r.append(lri[1])

lr.sort(key=lambda x:(x[0],x[1]))
l.sort()

for i in range(qn):
    pi, qi = list(map(int, input().split()))
    idxl =  bisect.bisect_left(l, pi)
    lrtmp2 = [z[1] for z in lr[idxl:]]
    lrtmp2.sort()
    idxr = bisect.bisect_right(lrtmp2, qi)
    print(idxr)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N,M,Q = map(int,input().split())
lines = []
questions = []
for i in range(M+Q):
    if i < M:
        lines.append(list(map(int,input().split())))
    else:
        questions.append(list(map(int,input().split())))
answers = []
lines.sort(key = itemgetter(1))

for question in questions:
    tmp = 0
    for line in lines:
        if question[1] < line[1]:
            break
        if question[0] <= line[0] and line[1] <= question[1]:
            tmp = tmp + 1
    answers.append(tmp)

for ans in answers:
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int,input().split())
l = []
p = []
for i in range(m):
    l.append(list(map(int, input().split())))
l.sort(reverse = True)
for i in range(q):
    a = 0
    p = list(map(int, input().split()))
    for j in l:
        if j[0] >= p[0]:
            if j[1] <= p[1]:
                a += 1
        else:
          break
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M,Q=map(int, input().split())
L = [0]*M
R = [0]*M
p = [0]*Q
q = [0]*Q
for i in range(M):
    L[i],R[i] = map(int, input().split())
for i in range(Q):
    p[i],q[i] = map(int, input().split())
num = 0
aL = np.array(L)
aR = np.array(R)
for i in range(Q):
    arrayL = (np.sign(aL-p[i]+0.5)+1)/2
    arrayR = (np.sign(q[i]-aR+0.5)+1)/2
    print(int(np.dot(arrayL,arrayR)))

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
N, M, Q = [int(x) for x in stdin.readline().rstrip().split()]

LR = []
for i in range(M):
    tmp = list(map(int,stdin.readline().rstrip().split()))
    LR.append(tmp)
pq = []
for i in range(Q):
    tmp = list(map(int,stdin.readline().rstrip().split()))
    pq.append(tmp)

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]

N,M,Q = Is()
lis = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = Is()
    lis[l][r] += 1

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

for _ in range(Q): 
    p,q = Is()
    t = 0
    for i in range(p,q+1):
        if dp[i][q]:
            t += dp[i][q]
        else:
            dp[i][q] = sum(lis[i][i:q+1])
            t += dp[i][q]
    print(t)

Submission status: Time Limit Exceeded

Solution code:
a,b,c = map(int, input().split())
d = []
g = []
for i in range(b):
    e,f = map(int,input().split())
    d.append([e,f])
for i in range(c):
    h,j = map(int,input().split())
    g.append([h,j])
for i in g:
    cnt = 0
    for k in d:
        if i[0] <= k[0] and k[1] <= i[1]:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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)
    
for i in range(Q):
    answer=0
    for j in range(m):
        if p[i]<=l[j]:
            if r[j]<=q[i]:
                answer+=1
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
a = input().split(" ")
n = int(a[0])
m = int(a[1])
q = int(a[2])
b = []
c = []
for i in range(0, m):
	d = input().split(" ")
	b.append(int(d[0]))
	c.append(int(d[1]))
for j in range(0, q):
	f = 0
	e = input().split(" ")
	l = int(e[0])
	r = int(e[1])
	for k in range(0, m):
		if b[k] >= l:
			if c[k] <= r:
				f += 1
	print(f)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int, input().split())
l=[set() for _ in range(n)]
r=[set() for _ in range(n)]

for i in range(m):
    li,ri=map(int, input().split())
    for j in range(li):
        l[j].add(i)
    for j in range(ri-1,n):
        r[j].add(i)

for i in range(q):
    pi,qi=map(int, input().split())
    print(len(l[pi-1]&r[qi-1]))

Submission status: Time Limit Exceeded

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)]
trains.sort(key = lambda x: x[1])

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 for _ in range(N)] for __ in range(N)]

def ans(left, right):
    if dp[left][right] > 0:
        return dp[left][right]
    elif left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        return dp[left][right]
    else:
        dp[left][right] = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        return dp[left][right]

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""
import bisect
n, m, qn = list(map(int, input().split()))

l= []
r = []
lr = []
p = []
q = []

for i in range(m):
    lri = list(map(int, input().split()))
    lr.append(lri)
    l.append(lri[0])
    r.append(lri[1])

lr.sort(key=lambda x:(x[0],x[1]))
l.sort()

for i in range(qn):
    pi, qi = list(map(int, input().split()))
    idxl =  bisect.bisect_left(l, pi)
    lrtmp = lr[idxl:]
    #print(lrtmp)
    lrtmp2 = [z[1] for z in lrtmp]
    lrtmp2.sort()
    idxr = bisect.bisect_right(lrtmp2, qi)
    print(idxr)

Submission status: Time Limit Exceeded

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

L = []
R = []
p = []
q = []

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

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

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
Exp = [list(map(int,input().split())) for i in range(M)]
Exp.sort()
memo = [[0 for i in range(N)] for j in range(N)]
for e in Exp:
    memo[e[0]-1][e[1]-1] += 1
for i in range(N):
    for j in range(N):
        if i < j:
            memo[i][j] += memo[i][j-1] + sum(memo[j-k][j] for k in range(j-i))
Query = [list(map(int,input().split())) for i in range(Q)]
for q in Query:
    print(memo[q[0]-1][q[1]-1])

Submission status: Time Limit Exceeded

Solution code:
input_s = str(input())
[l, m, q] = list(map(int, input_s.split(" ")))
rosen = []
for i in range(0,m):
    input_tmp = str(input())
    rosen.append(list(map(int, input_tmp.split(" "))))
results = []
for i in range(0, q):
    result = 0
    input_tmp = str(input())
    list_tmp = list(map(int, input_tmp.split(" ")))
    for r in rosen:
        if list_tmp[0] <= r[0] and r[1] <= list_tmp[1]:
            result += 1
    results.append(result)

for result in results:
    print(result)

Submission status: Time Limit Exceeded

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)]
trains.sort(key = lambda x: x[1])

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 for _ in range(N)] for __ in range(N)]

def ans(left, right):
    if left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        return dp[left][right]
    else:
        dp[left][right] = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        return dp[left][right]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
N, M, Q = [int(i) for i in input().strip().split(' ')]

flag  = False
Ls = []
Rs = []
ps = []
qs = []
counter = M

d = []
for i in range(N):
    d.append([0] * N)


for line in sys.stdin:
    L, R = [int(i) for i in line.strip().split(' ')]
#    print(line.strip().split(' '))
#    L, R == line.strip().split(' ')
    if not flag:
        for i in range(L):
            for j in range(N - R + 1):
                d[i][R + j - 1] += 1
        Ls.append(L)
        Rs.append(R)
        counter -= 1
        if counter == 0:
            flag = True
    else:
        print(d[L-1][R-1])

Submission status: Time Limit Exceeded

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

import sys


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

    cities_l = [[] for i in range(n+1)]
    cities_r = [[] for i in range(n+1)]
    cities_qp = [[] for i in range(n+1)]
    cities_qq = [[] for i in range(n+1)]

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        cities_l[l].append(i)
        cities_r[r].append(i)

    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        cities_qp[qp].append(i)
        cities_qq[qq].append(i)

    z = set()
    ans = [[[], []] for i in range(q)]
    for i in range(1,n+1):
        z |= set(cities_qp[i])
        for j in z:
            ans[j][0] += cities_l[i]
            ans[j][1] += cities_r[i]
        z -= set(cities_qq[i])

    for i in range(q):
        print(len(set(ans[i][0]) & set(ans[i][1])))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n,m,q = map(int, input().split())
astart = []
aend = []
bstart = []
bend = []
ans = []
for i in range(m):
    a1,a2 = map(int, input().split())
    astart.append(a1)
    aend.append(a2)
for i in range(q):
    a1,a2 = map(int, input().split())
    bstart.append(a1)
    bend.append(a2)
cstart = deque(bstart)
cend = deque(bend)
while len(cstart) > 0:
    count = 0
    s = cstart.popleft()
    e = cend.popleft()
    for i in range(0,m):
        if s <= astart[i] and e >=aend[i]:
            count+=1
        if i == m-1:
            print(count)

Submission status: Time Limit Exceeded

Solution code:
a = input().split(" ")
n = int(a[0])
m = int(a[1])
q = int(a[2])
b = []
c = []
for i in range(0, m):
	d = input().split(" ")
	b.append(int(d[0]))
	c.append(int(d[1]))
for j in range(0, q):
	f = 0
	e = input().split(" ")
	l = int(e[0])
	r = int(e[1])
	for k in range(0, m):
		if b[k] >= l and c[k] <= r:
			f += 1
	print(f)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
LR = []
for i in range(M):
    li,ri = map(int,input().split())
    LR.append((li,ri,0))
pq = []
ans = []
for i in range(Q):
    pi,qi = map(int,input().split())
    pq.append((pi,qi,i+1))
    ans.append(0)
newl = LR+pq
newl.sort(key=lambda x:x[1])
llist = [0]*N
count = 0
for i in range(M+Q):
    now = newl[i]
    if now[2] == 0:
        llist[now[0]-1] += 1
    else:
        for j in range(now[0]-1,now[1]):
            count += llist[j]
        ans[now[2]-1] = count
        count = 0
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n,m,q = input().split()
list = []
for i in range(int(m)):
    l,r = input().split()
    list.append([int(l),int(r)])
for i in range(int(q)):
    p,q = input().split()
    count = 0
    for j in range(len(list)):
        if int(p) <= list[j][0] and int(q) >= list[j][1]:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
matmul = np.zeros((n, n), dtype=np.uint32)
matmul[n-1] = mat[n-1]
for i in range(n-2, -1, -1):
    matmul[i] = matmul[i+1] + mat[i]

matmul = matmul.T
matmul2 = np.zeros((n, n), dtype=np.uint32)
matmul2[0] = matmul[0]
for i in range(n-1):
    matmul2[i+1] = matmul2[i] + matmul[i+1]

matmul2 = matmul2.T

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np
N,M,Q = map(int,input().split())
lr = [0]*M
for i in range(M):
    l,r = map(int,input().split())
    lr[i] = [l,r]
lr = sorted(lr,key=lambda x:x[0])
lr_t = list(np.array(lr).transpose())
index_dict={}
r_dict={} 
for i in range(N):
    index_dict[i+1]=bisect.bisect_left(lr_t[0],i+1)
    r_dict[i+1]=sorted(lr_t[1][index_dict[i+1]:])
for i in range(Q):
    p,q = map(int,input().split())
    I = index_dict[p]
    r = r_dict[p]
    I = bisect.bisect(r,q)
    print(I)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def main():
    N, M, Q = map(int, input().split())
    LR = []
    for i in range(M):
        l, r = map(int, input().split())
        LR.append([l-1, r])
    PQ = []
    for i in range(Q):
        p, q = map(int, input().split())
        PQ.append([p-1, q-1])
    ar = np.zeros([M, N])
    for m in range(M):
        ar[m, LR[m][0]:LR[m][1]] = 1
    flags_start = [np.ones(M, dtype=np.bool)]
    flags_end = []
    for i in range(1, N):
        flags_start.append((ar[:, :i].max(axis=1)==0))# * (ar[:, i:].max(axis=1)==1))
        flags_end.append((ar[:, i:].max(axis=1)==0))# * (ar[:, :i].max(axis=1)==1))
    flags_end.append(np.ones(M, dtype=np.bool))
    for q in range(Q):
        left = PQ[q][0]
        right = PQ[q][1]
        print(sum(flags_start[left] * flags_end[right]))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m,Q = map(int,input().split())
l = np.zeros(m)
r = np.zeros(m)
p = np.zeros(Q)
q = np.zeros(Q)

for i in range(m):
    a,b = map(int,input().split())
    l[i] = a-1
    r[i] = b-1
for i in range(Q):
    a,b = map(int,input().split())
    p[i] = a-1
    q[i] = b-1

ldash = []
rdash = []
for i in range(n):
    ldash.append(l >= i)
    rdash.append(r <= i)

for i in range(Q):
    print(np.sum(ldash[int(p[i])] * rdash[int(q[i])]))

Submission status: Time Limit Exceeded

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

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

from operator import itemgetter

def main():
    n, m, qs = map(int, input().split())

    lr_list = []
    for _ in range(m):
        lr_list.append(list(map(int, input().split())))

    pq_list = []
    for _ in range(qs):
        pq_list.append(list(map(int, input().split())))

    lr_list = sorted(lr_list, key=itemgetter(0))

    lr_index_start = 0
    index_memo = {}
    for p, q in pq_list:
        count = 0
        left_matched = False
        lr_index_start = index_memo.get(p, 0)
        for i in range(lr_index_start, m):
            l, r = lr_list[i]
            if p <= l and r <= q:
                count = count + 1
            if p <= l and not left_matched:
                left_matched = True
                index_memo[p] = i
        print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
import numpy as np
n,m,q=map(int,input().split())
s=[]
t=[]
ss=[]
def aa(m):
    for i in range(m):
        x,y=map(int,input().split())
        ss.append((x,y))
    ss.sort()
    return ss
def bb(ss):
    global s,t
    for x,y in ss:
        s+=[x]
        t+=[y]
    return s,t
def cc(q,s,t):
    for i in range(q):
        x,y=map(int,input().split())
        bi=bisect_left(s,x)
        u=np.array(t[bi:])
        print(len(u[u<=y]))
    return
s,t=bb(aa(m))
cc(q,s,t)

Submission status: Time Limit Exceeded

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

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

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

for i in range(q):
    count = 0
    (ql, qr) = map(int, input().split(" "))
    for j in range(ql, qr + 1):
        for k in range(j, qr + 1):
            count += ns[j][k]
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M, Q = map(int, input().split())
result = np.zeros((N,N), dtype=int)

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

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

Submission status: Time Limit Exceeded

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

route = sorted(route, key=lambda x: x[1])
# question = sorted(question, key=lambda x: x[1])

ans = [0 for i in range(Q)]
chk = 0
for j in range(Q):
    for i in range(M):
        if route[i][1] > question[j][1]:
            break
        if (question[j][0] <= route[i][0]) and (route[i][1] <= question[j][1]):
            ans[j] += 1

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left


n, m, q = map(int, input().split())
lrlist = [[int(x) for x in input().split()] for _ in range(m)]
pqlist = [[int(x) for x in input().split()] for _ in range(q)]

lrlist.sort(key=lambda lr: lr[1])
lrlist.sort(key=lambda lr: lr[0])
llist = [lr[0] for lr in lrlist]
rlist = [lr[1] for lr in lrlist]

pqilist = [[pqlist[i][0], pqlist[i][1], i] for i in range(q)]
pqilist.sort(key=lambda pqi: pqi[1])
pqilist.sort(key=lambda pqi: pqi[0])

cntlist = []
j = 0
for p, q, i in pqilist:
    cnt = 0
    j = bisect_left(llist, p, j)
    for r in rlist[j:]:
        if r <= q:
            cnt += 1
    cntlist.append((cnt, i))

cntlist.sort(key=lambda cnti: cnti[1])
for cnt, _ in cntlist:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,m,l = list(map(int,input().split()))
ans = 0
data = []
for i in range(m):
  data.append( list( map(int,input().split()) ) )
que = []
for i in range(l):
  que.append(list( map(int,input().split()) ) )
for lis in que:
  ans = 0
  for i in filter(lambda s:s[0] >= lis[0] and s[1] <= lis[1],data):
    ans += 1
  print(ans)

Submission status: Time Limit Exceeded

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

for t in range(Q):
    count = 0
    for i in range(M):
        count+=1 if p_q[t][0] <= L_R[i][0] and p_q[t][1] >= L_R[i][1] else 0
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]

N,M,Q = Is()
lis = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = Is()
    lis[l][r] += 1
for _ in range(Q): 
    p,q = Is()
    t = 0
    for i in range(p,q+1):
        t += sum(lis[i][i:q+1])
    print(t)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = [int(i) for i in input().split()]
LR = [[int(i), int(j)] for i, j in [input().split() for i in range(M)]]
LR = sorted(LR)
PQ = [[int(i), int(j)] for i, j in [input().split() for i in range(Q)]]
    
for p,q in PQ:
    tmp = [p,-1]
    LR.append(tmp)
    LR = sorted(LR)
    ind = LR.index(tmp)+1
    tmpLR = LR[ind:]
    LR.remove(tmp)
    tmp = [N+1,q]
    tmpLR.append(tmp)
    tmpLR = sorted(tmpLR, key = lambda x:x[1])
    ind = tmpLR.index(tmp)
    tmpLR = tmpLR[:ind]
    print(len(tmpLR))

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np
N,M,Q = map(int,input().split())
lr = [0]*M
for i in range(M):
    l,r = map(int,input().split())
    lr[i] = [l,r]
lr = sorted(lr,key=lambda x:x[0])
lr_t = list(np.array(lr).transpose())
index_dict={}
for i in range(N):
    index_dict[i+1]=bisect.bisect_left(lr_t[0],i+1)
for i in range(Q):
    p,q = map(int,input().split())
    I = index_dict[p]
    r = sorted(lr_t[1][I:])
    I = bisect.bisect(r,q)
    print(I)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
lines = []
questions = []
for i in range(M+Q):
    if i < M:
        lines.append(list(map(int,input().split())))
    else:
        questions.append(list(map(int,input().split())))
answers = []
for question in questions:
    tmp = 0
    for line in lines:
        if question[0] <= line[0] and line[1] <= question[1]:
            tmp = tmp + 1
    answers.append(tmp)

for ans in answers:
    print(ans)