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:
# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/abc106/editorial.pdf
　　　https://www.hamayanhamayan.com/entry/2018/08/18/234325
・累積和
"""

N, M, Q = map(int, input().split())
lM, rM = [0] * M, [0] * M
pQ, qQ = [0] * Q, [0] * Q
LR = [[0] * N for i in range(N)]
# 都市番号を0-indexed
for i in range(M):
    l, r = map(int, input().split())
    lM[i], rM[i] = l-1, r-1
    LR[l-1][r-1] += 1
for i in range(Q):
    p, q = map(int, input().split())
    pQ[i], qQ[i] = p-1, q-1

# 始点固定で終点を動かした累積和を出す
cnt = [[0] * N for i in range(N)]
for i in range(N):
    cnt[i][i] = LR[i][i]
    for j in range(1, N):
        cnt[i][j] = cnt[i][j-1] + LR[i][j]

for i in range(Q):
    ans = 0
    for j in range(pQ[i], qQ[i]+1):
        # ある終点についてもう和が出てるので、
        # ここでは始点を動かして最終的な合計にする
        ans += cnt[j][qQ[i]]
    print(ans)

Submission status: Time Limit Exceeded

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

N, M, Q = map(int, input().split())
lM, rM = [0] * M, [0] * M
pQ, qQ = [0] * Q, [0] * Q
# 都市番号を0-indexed
for i in range(M):
    l, r = map(int, input().split())
    lM[i], rM[i] = l-1, r-1
for i in range(Q):
    p, q = map(int, input().split())
    pQ[i], qQ[i] = p-1, q-1

# (始点, 終点)
cities = [(set(), set()) for i in range(N)]
for i in range(M):
    cities[lM[i]][0].add(i)
    cities[rM[i]][1].add(i)

# 各質問
for i in range(Q):
    starts = set()
    ends = set()
    # 各都市を始点終点としている列車番号を集めていく
    for j in range(pQ[i], qQ[i]+1):
        starts |= cities[j][0]
        ends |= cities[j][1]
    print(len(starts & ends))

Submission status: Time Limit Exceeded

Solution code:
a,b,c = map(int,input().split(" "))
ar = []
br = []
for i in range(b):
    l = list(map(int,input().split(" ")))
    ar.append(l)
for i in range(c):
    l = list(map(int,input().split(" ")))
    count = 0
    for rr in ar:
        if l[0] <= rr[0] and l[1] >= rr[1]:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
a,b,c = map(int,input().split(" "))
ar = []
br = []
for i in range(b):
    l = list(map(int,input().split(" ")))
    ar.append(l)
for i in range(c):
    l = list(map(int,input().split(" ")))
    br.append(l)
for r in br:
    count = 0
    for rr in ar:
        if r[0] <= rr[0] and r[1] >= rr[1]:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from itertools import takewhile
def main():
    (n, m, q) = map(lambda x: int(x), input().split(' '))
    
    trains = []
    for i in range(m):
        (l, r) = map(lambda x: int(x), input().split(' '))
        section = r - l # n-1 .. 0 
        trains.append((section, l, r))
    trains.sort(key=lambda x: x[0])

    for i in range(q):
        (p, q) = map(lambda x: int(x), input().split(' '))
        count = 0
        for s, l, r in takewhile(lambda train: q-p>=train[0], trains):
            if p <= l and r <= q:
                count += 1
        print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from itertools import takewhile
def main():
    (n, m, q) = map(lambda x: int(x), input().split(' '))
    
    trains = []
    for i in range(m):
        (l, r) = map(lambda x: int(x), input().split(' '))
        section = r - l # n-1 .. 0 
        trains.append((section, l, r))
    trains.sort(key=lambda x: x[0])

    for i in range(q):
        (p, q) = map(lambda x: int(x), input().split(' '))
        count = 0
        options = list(takewhile(lambda train: q-p>=train[0], trains))
        for s, l, r in options:
            if p <= l and r <= q:
                count += 1
        print(count)

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

for i in range(QN):
    p, q = [int(x) for x in input().split()]
    ret = 0
    for j in range(p, q + 1):
        ret = ret + MAT[j][q] - MAT[j][p - 1]
    print(ret)

Submission status: Time Limit Exceeded

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

L = [None] * M
R = [None] * M

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

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

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

for i in range(QN):
    p, q = [int(x) for x in input().split()]
    ret = 0
    for j in range(p, q + 1):
        ret = ret + MAT[j][q] - MAT[j][p - 1]
    print(ret)

Submission status: Time Limit Exceeded

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

L = [None] * M
R = [None] * M

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

P = [None] * QNUM  # P
Q = [None] * QNUM  # Q

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

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

for i in range(M):
    for s in range(1, L[i] + 1):
        for e in range(R[i], N + 1):
            T[s][e] += 1


for i in range(QNUM):
    print(T[P[i]][Q[i]])

Submission status: Time Limit Exceeded

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

dp = [[0] * N for _ in range(N)]
for lr in LR:
    dp[lr[0] - 1][lr[1] - 1] += 1
for pq in PQ:
    print(sum([sum(dp[i][i:pq[1]]) for i in range(pq[0] - 1, pq[1])]))

Submission status: Time Limit Exceeded

Solution code:
#横にn個入力
n, m, q = map(int, input().split())
#行列
s = []
for i in range(m):#h:高さ
    s.append([int(m) for m in input().split()])
# 行列
t = []
for i in range(q):  # h:高さ
    t.append([int(m) for m in input().split()])
nnli = []
for i in range(n):
    nnli.append([])
for i in range(n):
    for j in range(n):
        nnli[i].append(0)
for h in range(m):
    for i in range(s[h][0]):
        for j in range(s[h][1] - 1, n):
            nnli[i][j] += 1

for g in range(q):
    print(nnli[t[g][0] - 1][t[g][1] - 1])

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = [int(v) for v in input().split()]
p = []
q = []
x = [[0] * (N+1) for i in range(N+1)]
c = [[0] * (N+1) for i in range(N+1)]

for i in range(M):
    l, r = [int(v) for v in input().split()]
    x[l][r] += 1
for i in range(1, N+1):
    for j in range(1, N+1):
        c[i][j] = c[i][j-1] + x[i][j]
for i in range(Q):
    a, b = [int(v) for v in input().split()]
    p.append(a)
    q.append(b)

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

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = [int(v) for v in input().split()]
L = []
R = []
p = []
q = []
for i in range(M):
    a, b = [int(v) for v in input().split()]
    L.append(a)
    R.append(b)
for i in range(Q):
    a, b = [int(v) for v in input().split()]
    p.append(a)
    q.append(b)

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
Town=[[int(i) for i in input().split()] for i in range(M)]
Town.sort(key=lambda x:x[0])

def BS_left(x,L,s):
  L_copy=L[:]
  left=0
  if L[s-1]<x:
    return s-1
  else:
    while s>2:
      if L_copy[s//2]<x:
        L_copy=L_copy[s//2:s]
        left+=s//2
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        s=s//2+1
    if L[left]>=x:
      return left-1
    else:
      return left

def BS_right(x,L,s):
  L_copy=L[:]
  right=s-1
  if L[0]>x:
    return 0
  else:
    while s>2:
      if L_copy[s//2]<=x:
        L_copy=L_copy[s//2:s]
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        right+=-s//2+1
        s=s//2+1
    if L[right]<=x:
      return right+1
    else:
      return right

ans=[0]*Q
for i in range(Q):
  p,q=map(int,input().split())
  for i in zip(*Town):
    TownL=i
    break
  a=BS_left(p,TownL,M)+1
  b=BS_right(q,TownL,M)
  newTown=Town[a:b]
  if b-a==0:
    print(0)
  else:
    newTown.sort(key=lambda x:x[1])
    e=0
    for i in zip(*newTown):
      if e==0:
        e+=1
      else:
        TownR=i
        break
    c=BS_right(q,TownR,b-a)
    if c==1 and TownR[0]>q:
      print(0)
    else:
      print(c)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
Town=[[int(i) for i in input().split()] for i in range(M)]
Town.sort(key=lambda x:x[0])

def BS_left(x,L,s):
  L_copy=L[:]
  left=0
  if L[s-1]<x:
    return s-1
  else:
    while s>2:
      if L_copy[s//2]<x:
        L_copy=L_copy[s//2:s]
        left+=s//2
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        s=s//2+1
    if L[left]>=x:
      return left-1
    else:
      return left

def BS_right(x,L,s):
  L_copy=L[:]
  right=s-1
  if L[0]>x:
    return 0
  else:
    while s>2:
      if L_copy[s//2]<=x:
        L_copy=L_copy[s//2:s]
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        right+=-s//2+1
        s=s//2+1
    if L[right]<=x:
      return right+1
    else:
      return right

ans=[0]*Q
for i in range(Q):
  p,q=map(int,input().split())
  TownL=list(zip(*Town))[0]
  a=BS_left(p,TownL,M)+1
  b=BS_right(q,TownL,M)
  newTown=Town[a:b]
  if b-a==0:
    print(0)
  else:
    newTown.sort(key=lambda x:x[1])
    TownR=list(zip(*newTown))[1]
    c=BS_right(q,TownR,b-a)
    if c==1 and TownR[0]>q:
      print(0)
    else:
      print(c)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
Town=[[0,0] for i in range(M)]
for i in range(M):
  Town[i][0],Town[i][1]=map(int,input().split())
Town.sort(key=lambda x:x[0])

def BS_left(x,L):
  L_copy=L[:]
  l=len(L_copy)
  left=0
  if L[l-1]<x:
    return l-1
  else:
    while l>2:
      if L_copy[l//2]<x:
        L_copy=L_copy[l//2:l]
        left+=l//2
      else:
        L_copy=L_copy[0:l//2+1]
      l=len(L_copy)
    if L[left]>=x:
      return left-1
    else:
      return left

def BS_right(x,L):
  L_copy=L[:]
  l=len(L_copy)
  right=l-1
  if L[0]>x:
    return 0
  else:
    while l>2:
      if L_copy[l//2]<=x:
        L_copy=L_copy[l//2:l]
      else:
        L_copy=L_copy[0:l//2+1]
        right+=-l//2+1
      l=len(L_copy)
    if L[right]<=x:
      return right+1
    else:
      return right

ans=[0]*Q
for i in range(Q):
  p,q=map(int,input().split())
  TownL=list(zip(*Town))[0]
  newTown=Town[BS_left(p,TownL)+1:BS_right(q,TownL)]
  if len(newTown)==0:
    print(0)
  else:
    newTown.sort(key=lambda x:x[1])
    TownR=list(zip(*newTown))[1]
    if BS_right(q,TownR)==1 and TownR[0]>q:
      print(0)
    else:
      print(BS_right(q,TownR))

Submission status: Time Limit Exceeded

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

ls = []
for _ in range(m):
    ls += [list(map(int, input().split()))]
qs = []
for _ in range(q):
    a, b = list(map(int, input().split()))
    qs += [range(a, b + 1)]

for qq in qs:
    c = 0
    for ll in ls:
        if ll[0] in qq and ll[1] in qq:
            c += 1
    print(c)

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, Q = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(M)]
pq = [[int(_) for _ in input().split()] for _ in range(Q)]

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

Submission status: Time Limit Exceeded

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

LR_bin = [2 ** (1 + _[1] - _[0]) - 1 << (_[0] - 1) for _ in LR]
pq_bin = [2 ** (1 + _[1] - _[0]) - 1 << (_[0] - 1) for _ in pq]

for i in pq_bin:
    print(sum([_ == i & _ for _ in LR_bin]))

Submission status: Time Limit Exceeded

Solution code:
import bisect
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(map(list, zip(*lr)))
index_dict={}
r_dict={}
d = {}
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())
    if p not in d:
        d[p]={}
        I = index_dict[p]
        r = r_dict[p]
        I = bisect.bisect(r,q)
        print(I)
        d[p][q]=I
    else:
        if q not in d[p]:
            I = index_dict[p]
            r = r_dict[p]
            I = bisect.bisect(r,q)
            print(I)
            d[p][q]=I
        else:
            print(d[p][q])

Submission status: Time Limit Exceeded

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

memo = [[0 for _ in range(N)] for _ in range(N)]
for l, r in LR:
    memo[l - 1][r - 1] += 1
for p, q in pq:
    print(sum([sum(memo[_][p - 1:q]) for _ in range(p - 1, q)]))

Submission status: Time Limit Exceeded

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

dp = [[0 for j in range(N - i)]for i in range(N)]
for k in range(M):
    for i in range(N):
        for j in range(N - i):
            dp[i][j] += 1 if i + 1 <= LR[k][0] and LR[k][1] <= i + j + 1 else 0
for l in range(Q):
    print(dp[pq[l][0] - 1][pq[l][1] - pq[l][0]])

Submission status: Time Limit Exceeded

Solution code:
nmq = list(map(int, input().split()))
n = nmq[0]
m = nmq[1]
q = nmq[2]
lr = list()
pq = list()
for i in range(m):
    lr_i = list(map(int, input().split()))
    lr.append(lr_i)
for i in range(q):
    pq_i = list(map(int, input().split()))
    pq.append(pq_i)
for i in range(q):
    ans_q = 0
    for j in range(m):
        if pq[i][0] <= lr[j][0] and lr[j][1] <= pq[i][1]:
            ans_q += 1
    print(ans_q)

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int,input().split())
lis = [list(map(int,input().split())) for i in range(m)]
li = [list(map(int,input().split())) for i in range(q)]
ans = [[0] * n for i in range(n)]
for a,b in lis:
  ans[a-1][b-1] += 1
for a,b in li:
  cou = 0
  for i in range(a-1,b):
    cou += sum(ans[i][i:b])
  print(cou)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

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

Station=[[0 for x in range(N+2)] for y in range(N+2)]

for i in range(M):
  s,t=map(int,input().split())
  Station[1][t]+=1
  Station[s+1][t]-=1
  Station[1][N+1]+=1
  Station[s+1][N+1]-=1
  ST1 = [list(accumulate(l)) for l in zip(*Station)]
  ST2 = [list(accumulate(l)) for l in zip(*ST1)]
  
for i in range(Q):
  l,r=map(int,input().split())
  print(ST2[l][r])

Submission status: Time Limit Exceeded

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

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

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

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

memo=[[-1]*(n+1) for _ in range(n+1)]

for i in range(q):
    P,Q=map(int,input().split())
    if(memo[P][Q]!=-1):
        print(memo[P][Q])
        continue
    tmp=0
    for j in range(P,Q+1):
        tmp+=mylist[j][Q]
    memo[P][Q]=tmp
    print(tmp)

Submission status: Time Limit Exceeded

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

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

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

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

for i in range(q):
    P,Q=map(int,input().split())
    tmp=0
    for j in range(P,Q+1):
        tmp+=mylist[j][Q]
    print(tmp)

Submission status: Time Limit Exceeded

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

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

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

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

for i in range(q):
    p,q=map(int,input().split())
    tmp=0
    for j in range(p,q+1):
        tmp+=mylist[j][q]
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
a,b,c= input().split()
l=[]
m=[]
for i in range (int(b)):
    l.append([int(i) for i in input().split() ])
for i in range (int(c)):
    m.append([int(i) for i in input().split() ])
# print (l,m)
s=0
for j in m:
    for i in l:
        if j[0]<=i[0] and i[1]<=j[1]:
            s+=1
    print(s)
    s=0

Submission status: Time Limit Exceeded

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

for i in range(Q):
    p,q = map(int,input().split())
    p_list.append(p)
    q_list.append(q)

for i in range(Q):
    count = 0
    for j in range(M):
        if p_list[i] <= L_list[j]:
            if  R_list[j] <= q_list[i]:
                count += 1
    print(count)

Submission status: Time Limit Exceeded

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

for i in range(Q):
    p,q = map(int,input().split())
    p_list.append(p)
    q_list.append(q)

for i in range(Q):
    count = 0
    for j in range(M):
        if p_list[i] <= L_list[j] and R_list[j] <= q_list[i]:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
def m():
    n, M, Q = map(int, input().split())
    a = [[0 for _ in range(n+1)] for _ in range(n+1)]
    for i in range(M):
        l, r = map(int, input().split())
        a[l][r] += 1

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

m()

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)
y = np.zeros([N, N], dtype=int)
for m in range(M):
    L, R = map(int, input().split())
    x[L-1, R-1] += 1
for i in range(N):
    y[i, :] = np.sum(x[:i+1, :], axis=0)
for i in range(Q):
    p, q = map(int, input().split())
    if p == 1:
        print(np.sum(y[q-1, p-1:q]))
    else:
        print(np.sum(y[q-1, p-1:q] - y[p-2, p-1: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)
for m in range(M):
    L, R = map(int, input().split())
    x[L-1, R-1] += 1
for i in range(Q):
    p, q = map(int, input().split())
    print(np.sum(x[p-1:q, p-1:q]))

Submission status: Time Limit Exceeded

Solution code:
# setting
import numpy as np
from collections import deque

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

LR = np.array([[0 for _ in range(n)] for i in range(n)])
for i in range(m):
    l, r = map(int, input().split())
    LR[l-1][r-1] += 1

res = list()
for i in range(q):
    p,q = list(map(int, input().split()))
    res.append(np.sum(LR[p-1:q, p-1:q]))
#------------------

#------------------
# print part
for r in res:
    print(r)
#------------------

Submission status: Time Limit Exceeded

Solution code:
# setting
import numpy as np
from collections import deque

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

LR = np.array([[0 for _ in range(n)] for i in range(n)])
for i in range(m):
    l, r = map(int, input().split())
    LR[(l-1,r-1)] += 1

res = deque()
for i in range(q):
    p,q = list(map(int, input().split()))
    res.append(np.sum(LR[p-1:q, p-1:q]))
#------------------

#------------------
# print part
for r in res:
    print(r)
#------------------

Submission status: Time Limit Exceeded

Solution code:
# setting
from collections import deque

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

LR = deque()
for i in range(m):
    LR.append(list(map(int, input().split())))

pq = deque()
for i in range(q):
    pq.append(list(map(int, input().split())))
#------------------

#------------------
# proccess part
res = [sum([1 for l,r in LR if l >= p and r <= q]) for p, q in pq]
#------------------

#------------------
# print part
for r in res:
    print(r)
#------------------

Submission status: Time Limit Exceeded

Solution code:
# setting
from collections import deque

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

LM = deque()
for i in range(m):
    LM.append(list(map(int, input().split())))

pq = deque()
for i in range(q):
    pq.append(list(map(int, input().split())))
#------------------

#------------------
# proccess part
res = deque()
for p,q in pq:
    count = 0
    for l,m in LM:
        if l >= p and m <= q:
            count += 1
    res.append(count)
#------------------

#------------------
# print part
for r in res:
    print(r)
#------------------

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int, input().split())
mmap = [ [ 0 for j in range(n+1) ] for i in range(n+1) ]
for i in range(m):
  s,e = map(int, input().split())
  mmap[s][e] += 1
for i in range(q):
  s,e = map(int, input().split())
  cnt = 0
  for j in range(s,e+1):
    for k in range(s,e+1):
      cnt += mmap[j][k]
  print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int, input().split())
m_start = []
m_end = []
for i in range(m):
  s,e = map(int, input().split())
  m_start .append(s)
  m_end.append(e)
for i in range(q):
  s,e = map(int, input().split())
  cnt = 0
  for j in range(m):
    if m_start[j] < s : continue
    if m_end[j] <= e : cnt += 1
  else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int, input().split())
m_start = []
m_end = []
for i in range(m):
  s,e = map(int, input().split())
  m_start .append(s)
  m_end.append(e)
for i in range(q):
  s,e = map(int, input().split())
  cnt = 0
  for j in range(m):
    if m_start[j] >= s and m_end[j] <= e : cnt += 1
  else:
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
x=[list(map(int,input().split())) for _ in range(m)]
y=[list(map(int,input().split())) for _ in range(q)]
ans=[]
for i in range(q):
  count=0
  for j in range(m):
    if y[i][0]<=x[j][0] and x[j][1]<=y[i][1]:
      count+=1
  ans.append(count)
for i in ans:
  print(i)

Submission status: Time Limit Exceeded

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

LR=[[int(j) for j in input().split()] for i in range(M)]
pq=[[int(j) for j in input().split()] for i in range(Q)]

for i in range(Q):
	num=0
	for j in range(M):
		if (LR[j][0]>=pq[i][0]) and (LR[j][1]<=pq[i][1]):
			num+=1
	print(num)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for _ in range(M)]
questions = [list(map(int, input().split())) for _ in range(Q)]
for q in questions:
    print(len([t for t in trains if q[0] <= t[0] and q[1] >= t[1]]))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for _ in range(M)]
questions = [list(map(int, input().split())) for _ in range(Q)]
for q in questions:
    count = 0
    for train in trains:
        if q[0] <= train[0] and q[1] >= train[1]:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

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

if __name__ == "__main__":
    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):
        l,r = map(int,input().split(" "))
        count = 0
        for i in range(M):
            L = LR[i][0]
            R = LR[i][1]
            if (l <= L)and(R <= r):
                count += 1
        print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = [int(_) for _ in input().split()]
listN = [[0] * (N+1) for i in range(N+1)]

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

retList = []
for i in range(Q):
	p, q = [int(_) for _ in input().split()]
	retList.append(sum(sum(_) for _ in [l[p:q+1] for l in listN[p:q+1]]))

for i in retList:
	print(i)

Submission status: Time Limit Exceeded

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

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

for i in range(q):
    x, y = map(int, input().split())
    cou = 0
    for j in range(m):
        if x > lines[j][0]:
            continue
        elif lines[j][1] <= y:
            cou += 1
    print(cou)

Submission status: Time Limit Exceeded

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

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

for i in range(q):
    x, y = map(int, input().split())
    cou = 0
    for j in range(m):
        if x <= lines[j][0] and lines[j][1] <= y:
            cou += 1
    print(cou)

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m, q = map(int, input().split())
    trains = [list(map(int, input().split())) for _ in range(m)]
    questions = [list(map(int, input().split())) for _ in range(q)]

    for question in questions:
        a, b = question
        # result = [train for train in trains if a <= train[0] and train[1] <= b]
        result = list(filter(lambda x: a <= x[0] and x[1] <= b, trains))
        print(len(result))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

for question in questions:
    x, y = question
    result = [train for train in trains if x <= train[0] and train[1] <= y]
    print(len(result))

Submission status: Time Limit Exceeded

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

for question in questions:
    x, y = question
    cnt = 0
    for train in trains:
        l, r = train
        if x <= l and r <= y: cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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

for q in Q:
    x, y = q
    cnt = 0
    for m in M:
        l, r = m
        if x <= l and r <= y:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

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


u =[0]*q
for i in range(0,q):
    cnt = 0
    for j in range(0,m):
        if (int(p[i][0])<=int(l[j][0])) and (int(p[i][1])>=int(l[j][1])):
            # print(p[i][0],p[i][1],l[j][0],l[j][1])
            cnt+=1
    u[i] = cnt
    
for i in range(0,q):
    print(u[i])

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	xmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	cmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	
	for train in trains:
		xmt[train[0]][train[1]] += 1

	for i in range(1, n + 1):
		for j in range(1, n + 1):
			cmt[i][j] = cmt[i][j - 1] + xmt[i][j]
	
	#for i in range(n + 1):
	#	print(cmt[i])

	for query in queries:
		ans = 0
		for j in range(query[0], query[1] + 1):
			ans += cmt[j][query[1]] - cmt[j][query[0] - 1] 
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	trains.sort()	
	frms = [x[0] for x in trains]
	tos = [x[1] for x in trains]

	for query in queries:
		start = bisect_left(frms, query[0])
		ans = len([x for x in tos[start:] if x <= query[1]])
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	trains.sort()	
	frms = [x[0] for x in trains]
	tos = [x[1] for x in trains]

	for query in queries:
		start = bisect_left(frms, query[0])
		tos_tmp = tos[start:]
		tos_tmp.sort()
		ans = bisect_left(tos_tmp, query[1] + 1)
		print(ans)

if __name__ == '__main__':
	main()