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

import numpy as np
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]))

Submission status: Time Limit Exceeded

Solution code:
buf = input().split()
N = int(buf[0])
M = int(buf[1])
Q = int(buf[2])
import numpy as np
train = np.zeros((N+1, N+1))
for i in range(M):
	buf = input().split()
	train[int(buf[0])][int(buf[1])] += 1
for i in range(Q):
	buf = input().split()
	p = int(buf[0])
	q = int(buf[1])
	print(int(np.sum(train[p:q+1, p:q+1])))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
ans = [0] * Q
Mi = [list(map(int, input().split())) for _ in range(M)]
Qi = [list(map(int, input().split())) for _ in range(Q)]
Mi.sort()
# Qi.sort()

for mi in Mi:
    for i in range(Q):
        if mi[0] >= Qi[i][0] and mi[1] <= Qi[i][1]:
            ans[i] += 1
for a in ans:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
alist=[]
for i in range(m):
    l,r=map(int,input().split())
    alist.append([l,r])
alist.sort()
for t in range(q):
    count=0
    blist=[]
    p,q=map(int,input().split())
    for j in range (len(alist)):
        if p<=alist[0][0]:
            alist.sort(key=lambda x:x[1])
            break
        blist.append(alist[0])
        alist.remove(alist[0])
    for j in range (len(alist)):
        if q>=alist[j][1]:
            count+=1
        else:
            break
    for k in blist:
        alist.append(k)
    print(count)
    alist.sort(key=lambda x:x[0])

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m, q = map(int, input().split())
bridge = []

for _ in range(m):
    l, r = map(int, input().split())

    bridge.append([l, r])

bridge.sort(key=lambda x: x[1])

end = [i[1] for i in bridge]

# print(bisect.bisect_right(end, 3))
for _ in range(q):

    total = 0

    l, r = map(int, input().split())

    index = bisect.bisect_right(end, r)

    for b in bridge[:index]:
        if b[0] >= l:
            total += 1

    print(total)

Submission status: Time Limit Exceeded

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

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

for i in range(n-1):
  num[i+1][1] = num[i][0] + num[i][1]

for i in range(q):
  l,r = map(int,input().split())
  ans = 0
  for j in range(l,r+1):
    s = num[j-1][0]
    t = num[j-1][1]
    u = 0
    for k in range(s):
      if(train[t+s-1-k][1] <= r):
        u = s - k
        break
    ans += u
  print(ans)

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

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

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):
        dk = [p for p in dk if i <= p]
        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 = map(int, input().split())
tL = []
tR = []
for i in range(M):
    a, b = map(int, input().split())
    tL.append(a)
    tR.append(b)
ql = []
qr = []
for j in range(Q):
    c, d = map(int, input().split())
    ql.append(c)
    qr.append(d)

for j in range(Q):
    count = 0
    for i in range(M):
        if ql[j] <= tL[i] and tR[i] <= qr[j]:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = tuple(map(int, input().split()))
exp = [[0, 0] for i in range(m)]
for i in range(m):
    exp[i] = list(map(int, input().split()))
que = [[0, 0, 0, 0] for i in range(q)]
for i in range(q):
    nu, pa = list(map(int, input().split()))
    que[i] = [nu, pa, i, 0]


def ge(x):
    return x[0] * 501 + x[1]


def modosu(x):
    return x[2]

que.sort(key=ge)
for e in exp:
    for q in que:
        if q[0] > e[0]:
            break
        if q[1] >= e[1]:
            q[3] += 1

    
que.sort(key=modosu)
for e in que:
    print(e[3])

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]
        if p <= L:
            R = LR[j][1]
            if R <= q:
                count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

L = np.zeros(N, dtype=int)
R = np.zeros(N, dtype=int)
for m in range(M):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    
    L *= 2
    R *= 2
    
    L[:l+1] += 1
    R[r:] += 1

for _ in range(Q):
    p, q = map(int, input().split())
    
    print (bin(L[p - 1] & R[q - 1]).count("1"))

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())
for i in range(Q):
    p,q = map(int,input().split())
    I = bisect.bisect_left(lr_t[0],p)
    r = sorted(lr_t[1][I:])
    I = bisect.bisect(r,q)
    print(I)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=[int(i) for i in input().split()]
M_lis=[]
Q_lis=[]
for i in range(M):
    m=[]
    L,R=[int(j) for j in input().split()]
    m.append(L)
    m.append(R)
    M_lis.append(m)
for i in range(Q):
    u=[]
    p,q=[int(j) for j in input().split()]
    u.append(p)
    u.append(q)
    Q_lis.append(u)
for i in range(Q):
    W=0
    for j in range(M):
        if Q_lis[i][0]<=M_lis[j][0] and M_lis[j][1]<=Q_lis[i][1]:
            W+=1
    print(W)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

import numpy as np

N, M, Q = map(int, input().split())
tr =[]
for i in range(M):
    tr.append(list(map(int, input().split())))
qu = []
for i in range(Q):
    qu.append(list(map(int, input().split())))

tr_np = np.array(tr)
qu_np = np.array(qu)
#print(tr_np)
#print(qu_np)

#ans = []
#for p, q in qu:
for p, q in qu_np:
    #print(p, q)
    num = 0
    for l, r in tr_np:
        #print(l, r)

        if p <= l and r <= q:
            #print(p, l, r, q)
            num += 1

    #ans.append(num)
    print(num)

# for a in ans:
#     print(a)

Submission status: Time Limit Exceeded

Solution code:
n,m,qu=map(int,input().split())
l=[];r=[]
for i in range(m):
  l0,r0=map(int,input().split())
  l.append(l0);r.append(r0)

for i in range(qu):
  honsu=0
  p,q=map(int,input().split())
  for j in range(m):
    if l[j]>=p and r[j]<=q:
      honsu+=1
  print(honsu)

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
LR = np.array([tuple(map(int, input().split())) for i in range(M)])
pq = np.array([tuple(map(int, input().split())) for i in range(Q)])

ans = [str(sum((pq[i,0] <= LR[:,0]) * (pq[i,1] >= LR[:,1]))) for i in range(pq.shape[0])]

print("\n".join(ans))

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] and r[j]<=q[i]:
            answer+=1
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M, Q = map(int, input().split())
L = []
R = []
for i in range(M):
    tmp = list(map(int, input().split()))
    L.append(tmp[0])
    R.append(tmp[1])
p = []
q = []
for i in range(Q):
    tmp = list(map(int, input().split()))
    p.append(tmp[0])
    q.append(tmp[1])

L = np.array(L)
R = np.array(R)

ans = []
for i in range(len(p)):
    cnt = sum((L >= p[i]) * (R <= q[i]))
    ans.append(cnt)

for i in range(len(p)):
    print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
lrs = []
pqs = []
for i in range(M):
    temp = list(map(int, input().split()))
    temp.append(1)
    if(temp in lrs):
        lrs[lrs.index(temp)][2] += 1
    else:
        lrs.append(temp)
for i in range(Q):
    temp = list(map(int, input().split()))
    pqs.append(temp)
for ques in pqs:
    count = 0
    for rail in lrs:
        if((ques[0] <= rail[0]) and (ques[1] >= rail[1])):
            count += rail[2]
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]
 
rails.sort(key = lambda x:x[0],reverse=True)


for p,q in qs:
    ans=0
    for l,r in rails:
        if p<=l and r<=q:
            ans=ans+1
        elif p>l:
            break
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

trains.sort(key=itemgetter(0))
index = [-1 for _ in range(n+1)]
index[trains[0][0]] = 0
tmp = trains[0][0]

for i in range(len(trains)):
  if tmp != trains[i][0]:
    tmp = trains[i][0]
    index[tmp] = i
    
for i in range(len(index)-2, 0, -1):
    if index[i] == -1:
      index[i] = index[i+1]

questions = []
for i in range(q):
  a, b = map(int, input().split())
  questions.append((a,b))

for question in questions:
  cnt = 0
  for train in trains[index[question[0]]:]:
    if train[0] < question[0]:
      continue
    if train[1] > question[1]:
      continue
    cnt += 1
    
  print(cnt)

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]
    tmpLR = LR[::]
    tmpLR.append(tmp)
    tmpLR = sorted(tmpLR)
    ind = tmpLR.index(tmp)+1
    tmpLR = tmpLR[ind:]
    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:
# -*- coding: utf-8 -*-
from operator import itemgetter

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

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


LRi.sort(key=itemgetter(1))

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


for (p, q) in pqi:
    cnt = 0
    for (L,R) in LRi:
        if p <= L and R <= q:
            cnt += 1
        elif q < R:
            break
        elif L < p:
            continue
    print(cnt)

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 = np.array(lr).transpose()
for i in range(Q):
    p,q = map(int,input().split())
    I = bisect.bisect_left(lr_t[0],p)
    r = sorted(lr_t[1][I:])
    I = bisect.bisect(r,q)
    print(len(r[:I]))

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 (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:
N,M,Q=map(int,input().split(" "))
p=M
q=Q
train=[input() for i in range(p)]
for j in range(q):
    count=0
    a,b=map(int,input().split(" "))
    for k in range(p):
        c,d=map(int,train[k].split(" "))
        if a<=c and b>=d:
            count+=1
        else:
            pass
    else:
        print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m,qu=map(int,input().split())
l=[];r=[];p=[];q=[]
for i in range(m):
  l0,r0=map(int,input().split())
  l.append(l0);r.append(r0)
for i in range(qu):
  p0,q0=map(int,input().split())
  p.append(p0);q.append(q0)

for i in range(qu):
  honsu=0
  for j in range(m):
    if l[j]>=p[i] and r[j]<=q[i]:
      honsu+=1
  print(honsu)

Submission status: Time Limit Exceeded

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

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

for i in range(n-1):
  num[i+1][1] = num[i][0] + num[i][1]

for i in range(q):
  l,r = map(int,input().split())
  ans = 0
  for j in range(l,r+1):
    s = num[j-1][0]
    t = num[j-1][1]
    u = 0
    if(train[t+s-1][1] < r):
      ans += s
    else:
      for k in range(s):
        if(train[t+k][1] > r):
          u = s - k
          break
      ans += s - u
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
# stdin = open('sample.txt')


def get_start(p, tmp):
    for L, i in tmp:
        if L <= p:
            return i
    return 0


def get_end(q, tmp):
    for L, i in tmp:
        if q < L:
            return i
    return -1


def main():
    N, M, Q = [int(x) for x in stdin.readline().rstrip().split()]
    LR = [[int(x) for x in stdin.readline().split()] for _ in range(M)]
    LR = sorted(LR)
    pq = [[int(x) for x in stdin.readline().split()] for _ in range(Q)]

    tmp = []
    back = 0
    for i, (L, R) in enumerate(LR):
        if L == back:
            continue
        tmp.append((L, i))
        back = L

    for p, q in pq:
        count = 0

        start = get_start(p, tmp)
        end = get_end(q, tmp)
        end = len(LR) if end == -1 else end
        print(len([True for L, R in LR[start:end] if p <= L and R <= q]))


if __name__ == '__main__':
    main()

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]

for p, q in pqlist:
    cnt = 0
    i = bisect_left(llist, p)
    for r in rlist[i:]:
        if r <= q:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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)]
ans = [[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(i, N+1):
        accum[i][j] = accum[i][j-1] + table[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(ans[p][q])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

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

ans = np.zeros(Q,dtype = int)
for i in range(Q):
    for j in range(M):
        if  (p[i] <= L[j])and(q[i] >= R[j]):
            ans[i] += 1

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

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_l = [set() for i in range(n+1)]
    #cities_r = [set() 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)
        #cities_l[l].add(i)
        #cities_r[r].add(i)

    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        list_l = []
        list_r = []
        #set_l = set()
        #set_r = set()
        for j in range(qp, qq+1):
            list_l += cities_l[j]
            list_r += cities_r[j]
            #set_l |= cities_l[j]
            #set_r |= cities_r[j]
        print(len(set(list_l) & set(list_r)))
        #print(len(set_l & set_r))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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

max_L = 0
for L, R in LR:
    max_L = max(max_L, L)

LR_index = {}

for L, R in LR:
    if L in LR_index.keys():
        LR_index[L].append(R)
    else:
        LR_index[L] = [R]


for p, q in pq:
    count = 0
    for i in range(p, max_L+1):
        if i in LR_index.keys():
            count += len([j for j in LR_index[i] if j <= q])
    print(count)

Submission status: Time Limit Exceeded

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

L = [0] * N
R = [0] * N
for m in range(M):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    
    for n in range(N):
        L[n] *= 2
        R[n] *= 2
        if n <= l:
            L[n] += 1   
        if n >= r:
            R[n] += 1


for _ in range(Q):
    p, q = map(int, input().split())
    
    print (bin(L[p - 1] & R[q - 1]).count("1"))

Submission status: Time Limit Exceeded

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

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

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

for i in range(Q):
    l,r = [int(x)-1 for x in input().split()]
    ans =0
    for x in range(l,r+1):
        ans += sum(train[x][x:r+1])
    print(ans)

Submission status: Time Limit Exceeded

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

for p,q in pq:
  cnt = 0
  for l,r in LR:
    if q < l:
      break
    if p <= l and r <= q:
      cnt += 1
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

class Section:
  def __init__(self, left, right):
    self.left = left
    self.right = right

trains = [
  Section(*(int(s) for s in input().split(" "))) for i in range(M)
]

sections = [
  Section(*(int(s) for s in input().split(" "))) for i in range(Q)
]

left_trains = trains
left_trains.sort(key=lambda t: t.left)
lefts = [t.left for t in left_trains]

right_trains = trains.copy()
right_trains.sort(key=lambda t: t.right)
rights = [t.right for t in right_trains]

for sec in sections:
  left, right = (sec.left, sec.right)
  leftIdx = bisect.bisect_left(lefts, left)
  leftTrains = set(left_trains[leftIdx:])

  rightIdx = bisect.bisect_right(rights, right)
  rightTrains = set(right_trains[:rightIdx])
  matchedTrains = leftTrains & rightTrains
  print(len(matchedTrains))

Submission status: Time Limit Exceeded

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

x = [[] for _ in range(n)]
for l,r in lr:
    for i in range(l):
        x[i].append(r-1)
for p,q in pq:
    ans=0
    for j in x[p-1]:
        if j<q:
            ans+=1
    print(ans)
exit(0)

Submission status: Time Limit Exceeded

Solution code:
# cook your dish here
import numpy as np
n,m,q = map(int,input().split())
lr = []
for i in range(m):
    l = list(map(int,input().split()))	
    lr.append(l)
 
ass = np.zeros((n,n))
        
        
for i in range(m):
    ass[lr[i][0]-1][lr[i][1]-1] += 1
        
#print(ass)
 
for i in range(q):
    p,qa = map(int,input().split())
    ans = 0
    for i in range(p-1,qa):
        ans += sum(ass[i][:qa:])
    print(int(ans))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
N,M,Q = map(int,input().split())
T = [[0 for _ in range(N)] for _ in range(N)]
LR = []
for i in range(M):
  L,R = map(int, input().split())
  LR.append(L*1000+R)
LRD = Counter(LR)
for key in LRD:
  L,R=key//1000,key%1000
  v = LRD[key]
  for r in range(R-1,N):
    for l in range(L):
      T[l][r] += v
ans = []
for i in range(Q):
  p,q = map(int, input().split())
  ans.append(T[p-1][q-1])
print('\n'.join(map(str,ans)))

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
for i in range(q):
    p, q = map(int, input().split())
    mat2 = mat[p-1:q, p-1:q]
    print(np.sum(mat2))

Submission status: Time Limit Exceeded

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
	for j in xrange(f+1):
		imos[j][t] += 1

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

Solution code:
# -*- coding: utf-8 -*-
import math,string,itertools,fractions,heapq,collections,re,array,bisect
import numpy as np

def ln():
    return map(int, input().split())

N,M,Q_n = ln()
L = [0 for i in range(M)]
R = [0 for i in range(M)]

P = [0 for i in range(Q_n)]
Q = [0 for i in range(Q_n)]

for i in range(M):
    L[i],R[i] = ln()

for i in range(Q_n):
    P[i],Q[i] = ln()

for q_n in range(Q_n):
    p = P[q_n]
    q = Q[q_n]
    ans = 0
    for i in range(M):
        l = L[i]
        r = R[i]
        if p <= l and r <= q:
            ans +=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
trains = {}
answers = {}
results = []
def make_range(L, R):
    return (pow(2, (R-L+1))-1)<<L-1

for i in range(M):
    a, b = map(int, input().split())
    train = make_range(a, b)
    if train in trains:
        trains[train] += 1
    else:
        trains[train] = 1
    
for i in range(Q):
    a, b = map(int, input().split())
    question = make_range(a, b)
    if question in answers:
        results.append(answers[question])
    else:
        res = 0
        for train in trains:
            if question | train == question:
                res += trains[train]
        answers[question] = res
        results.append(res)

for result in results:
    print(result)

Submission status: Time Limit Exceeded

Solution code:
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

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][p:q+1])
    print(t)

Submission status: Time Limit Exceeded

Solution code:
# coding:utf-8

N, M, Q = map(int, input().split())
tr =[]
for i in range(M):
    tr.append(list(map(int, input().split())))
qu = []
for i in range(Q):
    qu.append(list(map(int, input().split())))

#print(tr)
#print(qu)

ans = []
for p, q in qu:
    #print(p, q)
    num = 0
    for l, r in tr:
        #print(l, r)

        if p <= l and r <= q:
            #print(p, l, r, q)
            num += 1

    ans.append(num)

for a in ans:
    print(a)

Submission status: Time Limit Exceeded

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

left=[]
right=[]

for i in range(m):
    l,r=map(int,input().split())
    left.append(l)
    right.append(r)

for i in range(q):
    l,r=map(int,input().split())
    count=0
    for j in range(m):
        if l <= left[j] and right[j] <= r:
            count += 1
    print(count)

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 = [set() for i in range(n+1)]
    cities_r = [set() 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].add(i)
        cities_r[r].add(i)

    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        set_l = set()
        set_r = set()
        for j in range(qp, qq+1):
            set_l |= cities_l[j]
            set_r |= cities_r[j]
        print(len(set_l & set_r))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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
for i in range(Q):
    for j in range(M):
        if p[i]<=L[j] and R[j]<=q[i]:
            num+=1
    print(num)
    num = 0

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
lrs = []
pqs = []
for i in range(M):
    temp = list(map(int, input().split()))
    lrs.append(temp)
for i in range(Q):
    temp = list(map(int, input().split()))
    pqs.append(temp)
for ques in pqs:
    count = 0
    for rail in lrs:
        if((ques[0] <= rail[0]) and (ques[1] >= rail[1])):
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = [int(i) for i in input().split()]
LR = []
PQ = []
for i in range(M):
    LR.append([int(i) for i in input().split()])
LR = sorted(LR)
for i in range(Q):
    PQ.append([int(i) for i in input().split()])
    
for p,q in PQ:
    tmp = [p,-1]
    tmpLR = LR[::]
    tmpLR.append(tmp)
    tmpLR = sorted(tmpLR)
    ind = tmpLR.index(tmp)+1
    tmpLR = tmpLR[ind:]
    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:
N,M,Q=map(int,input().split(" "))
train=[input() for i in range(M)]
for j in range(Q):
    count=0
    a,b=map(int,input().split(" "))
    for k in range(M):
        c,d=map(int,train[k].split(" "))
        if a<=c and b>=d:
            count+=1
        else:
            pass
    else:
        print(count)

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:
    for i in range(e[0]):
        for j in range(N-e[1]+1):
            memo[i][e[1]+j-1] += 1
Query = [list(map(int,input().split())) for i in range(Q)]
for q in Query:
    print(memo[q[0]-1][q[1]-1])