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:
from bisect import bisect_left,bisect_right

N,M,Q=list(map(int,input().split()))
t=[list(map(int,input().split())) for _ in range(M)]
query=[list(map(int,input().split())) for _ in range(Q)]

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

for l,r in t:
    train[l][r]+=1

for l in range(1,N+1):
    for r in range(1,N+1):
        c[l][r]=c[l][r-1]+train[l][r]

for p,q in query:
    tmp=0
    for l in range(p,q+1):
        tmp+=c[l][q]-c[l][p-1]
    
    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if j > 0:
            r[i][j] = r[i][j-1] + p[i][j]
        else:
            r[i][j] = p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
        if j - 1> 0:
            q = q - r[j-1][j-2]
    print(q)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if j > 0:
            r[i][j] = r[i][j-1] + p[i][j]
        else:
            r[i][j] = p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
        if j - 1> 0:
            q = q - r[j-1][j-2]
    print(q)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        r[i][j] = r[i][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
        if j - 1> 0:
            q = q - r[j-1][j-2]
    print(q)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        r[i][j] = r[i][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
    print(q)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        r[i][j] = r[i][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
    print(q)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        for k in range(j+1):
            r[i][j] = r[i][j] + p[i][k]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
    print(q)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        for k in range(Qlist[i][0],Qlist[i][1]+1):
            if j <= k:
                if p[j-1][k-1] != 0:
                    q = q+ p[j-1][k-1]
    print(q)

Submission status: Time Limit Exceeded

Solution code:
# 累積和(1次元)を用いた解法
from itertools import accumulate
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M,Q,*lr = map(int, read().split())

    LR = [[0]*(N+1) for _ in range(N+1)]
    query = []
    for i, (l, r) in enumerate(zip(*[iter(lr)]*2)):
        if i < M:
            LR[l][r] += 1
        else:
            query.append((l, r))
    
    LR_acc = []
    for L in LR:
        LR_acc.append(list(accumulate(L)))
    
    for p, q in query:
        ans = 0
        for i in range(p,q+1):
            ans += LR_acc[i][q] - LR_acc[i][p-1]
        print(ans)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def main():
    N,M,Q,*lr = map(int, read().split())

    LR = []
    query = []
    for i, (l, r) in enumerate(zip(*[iter(lr)]*2)):
        if i < M:
            LR.append((l, r))
        else:
            query.append((l, r))
    
    LR.sort()
    L = [int(i[0]) for i in LR]
    R = [int(i[1]) for i in LR]
    for p, q in query:
        p_in_L = bisect_left(L, p)
        q_in_L = bisect_right(L, q)
        q_in_R = bisect_right(sorted(R[p_in_L:q_in_L]), q)
        print(q_in_R)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

# print(cumlr)
for _ in range(q):
    l, r = map(int, input().split())
    ans = 0
    for i in range(l-1, r):
        for j in range(l-1, r):
            ans += cumlr[i][j]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = [int(x) for x in input().split()]
ll = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
    l,r = [int(x) for x in input().split()]
    ll[l][r] += 1
for i in range(1,N+1):
    for j in range(1,N+1):
        ll[i][j] += ll[i-1][j]
for i in range(Q):
    ans = 0
    p,q = [int(x) for x in input().split()]
    for i in range(p,q+1):
        ans += ll[q][i]-ll[p-1][i]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
class BIT_2D():
    def __init__(self,h,w):
        self.h=h
        self.w=w 
        self.table=[[0]*(w+1) for _ in range(h+1)]

    def add(self,i,j,x):
        init_j=j
        while i<=self.h:
            while j<=self.w:
                self.table[i][j]+=x
                j+=(j&-j)
            j=init_j
            i+=(i&-i)
        return None

    def sum(self,i,j):
        s=0
        init_j=j
        while i>0:
            while j>0:
                s+=self.table[i][j]
                j-=(j&-j)
            j=init_j
            i-=(i&-i)
        return s
      
n,m,q=map(int,input().split())
bit2d=BIT_2D(n,n)
for i in range(m):
  i,j=map(int,input().split())
  bit2d.add(i,j,1)
for i in range(q):
  i,j=map(int,input().split())
  ans=bit2d.sum(j,j)-bit2d.sum(j,i-1)-bit2d.sum(i-1,j)+bit2d.sum(i-1,i-1)
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
Ls = [0] * N
Rs = [0] * N
for i in range(M):
  L, R = map(int, input().split())
  Ls[L-1] |= 1 << i
  Rs[R-1] |= 1 << i

for i in range(N-1):
  j = N - 1 - i
  Rs[i+1] |= Rs[i]
  Ls[j-1] |= Ls[j]

for i in range(Q):
  p, q = map(int, input().split())
  print(bin(Ls[p-1] & Rs[q-1]).count('1'))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
# LR = [list(map(int, input().split())) for i in range(M)]
Ls = [set() for i in range(N)]
Rs = [set() for i in range(N)]
for i in range(M):
  L, R = map(int, input().split())
  Ls[L-1].add(i)
  Rs[R-1].add(i)

for i in range(N-1):
  j = N - 1 - i
  Rs[i+1] |= Rs[i]
  Ls[j-1] |= Ls[j]

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

Submission status: Time Limit Exceeded

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

import numpy

def main():
  n, m, q = map(int, input().split())
  counts = numpy.zeros((n, n), dtype=numpy.int)
  llr = [], []
  for _ in range(m):
    l, r = map(int, input().split())
    counts[l-1, r-1] += 1
  
  cusum = numpy.zeros((n, n), dtype=numpy.int)
  cusum[0, 0] = counts[0, 0]
  for i in range(1, len(cusum)):
    cusum[i,0] = cusum[i-1, 0] + counts[i, 0]
  for i in range(1, len(cusum[0])):
    cusum[0, i] = cusum[0, i-1] + counts[0, i]
  for i in range(1, n):
    for j in range(1, n):
      cusum[i, j] = cusum[i, j-1] + cusum[i-1, j] - cusum[i-1, j-1] + counts[i, j]
          
  for _ in range(q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    
    if p-1 < 0:
      print(cusum[q, q])
    else:
      print(cusum[q, q] - cusum[p-1, q] - cusum[q, p-1] + cusum[p-1, p-1])

if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    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())

    temp = [[0]*N for _ in range(N)]
    #s[i][j]: 左がi、右が0からjまでのものの累積個数
    s = [[0]*(N+1) for _ in range(N)]
    for m in range(M):
        temp[L[m]-1][R[m]-1] += 1
    for i in range(N):
        for j in range(N):
            s[i][j+1] = s[i][j] + temp[i][j]

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

if __name__ == '__main__':
    resolve()

Submission status: Time Limit Exceeded

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

xmat,cmat=[],[]
for i in range(N+1):
  xmat.append([0]*(N+1))
  cmat.append([0]*(N+1))

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

for i in range(1,N+1):
  for j in range(1,N+1):
    cmat[i][j]=xmat[i][j]+cmat[i][j-1]
#print(cmat)

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
T = [[0]*N for _ in range(N)]
for _ in range(M):
    l,r = map(int,input().split())
    T[l-1][r-1] += 1
def f(x,y,T):
    ret = 0
    for i in range(y):
        for j in range(x):
            ret += T[i][j]
    return ret
query = []
res = []
for _ in range(Q):
    p,q = map(int,input().split())
    res.append(f(q,q,T) - f(p-1, q ,T)- f(q, p-1, T) + f(p-1, p-1, T))
for r in res:
    print(r)

Submission status: Time Limit Exceeded

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

T = [[0]*N for _ in range(N)]
for _ in range(M):
    l,r = map(int,input().split())
    T[l-1][r-1] += 1

def f(x,y,T):
    ret = 0
    for i in range(y):
        for j in range(x):
            ret += T[i][j]
    return ret

query = []
res = []
for _ in range(Q):
    p,q = map(int,input().split())
    res.append(f(q,q,T) - f(p-1, q ,T)- f(q, p-1, T) + f(p-1, p-1, T))

for r in res:
    print(r)

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M, Q, *X = map(int, open(0).read().split())
    L = [0]*M
    R = [0]*M
    p = [0]*Q
    q = [0]*Q
    for i in range(M):
        L[i], R[i] = X[2*i], X[2*i + 1]
    for i in range(Q):
        p[i], q[i] = X[2*M + 2*i], X[2*M + 2*i + 1]
    # print(N, M, Q, L, R, p, q)
    S = [[0]*(N+1) for i in range(N+1)]
    for i in range(M):
        S[L[i]][R[i]] += 1
    # for s in S:
    #     print(s)
    S2 = [[0]*(N+1) for i in range(N+1)]
    for i in range(N+1):
        S2[i][0] = S[i][0]
        for j in range(1, N+1):
            S2[i][j] = S2[i][j-1] + S[i][j]
    # for s in S2:
    #     print(s)
    for i in range(Q):
        pi, qi = p[i], q[i]
        ans = 0
        for j in range(pi, qi + 1):
            ans += (S2[j][qi] - S2[j][pi-1])
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

tr = [[0]*n for _ in range(n)]

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

for i in range(n):
    tr[i] = list(itertools.accumulate(tr[i]))

for i in range(q):
    p, q = map((lambda x:int(x)-1), input().split())
    ans = 0
    for j in tr[p:q+1]:
        ans += (j[q] - j[p-1]) if p>0 else j[q]

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
L,R=[],[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    if i>j:
      c[i][j]=0
    c[i][j]+=c[i][j-1]
ans=[0]*Q
for i in range(Q):
  for j in range(Pl[i],Ql[i]+1):
    ans[i]+=c[j][Ql[i]]-c[j][Pl[i]-1]
for i in range(Q):
  print(ans[i])

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
lr=[]
for i in range(M):
  lr.append(list(map(int,input().split())))
pq=[]
for i in range(Q):
  pq.append(list(map(int,input().split())))
ans=[0]*Q
for i in range(Q):
  for j in range(M):
    if pq[i][0]<=lr[j][0] and lr[j][1]<=pq[i][1]:
      ans[i]+=1
for i in range(Q):
  print(ans[i])

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
plane = [[0]*N for _ in range(N)]
for i in range(M):
    l,r = map(int,input().split())
    plane[l-1][r-1] += 1
acc = [[0]*(N+1) for _ in range(N)]

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
n,m,q=map(int,input().split())
num=[[0]*(n+1) for _ in range(n+1)]
for i in range(m):
	l,r=map(int,input().split())
	num[l][r]+=1
for i in range(n):
	for j in range(n):
		num[i+1][j+1]+=num[i+1][j]
for i in range(q):
	p,q=map(int,input().split())
	ans=0
	for i in range(p,q+1):
		ans+=num[i][q]-num[i][p-1]
	print(ans)

Submission status: Time Limit Exceeded

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


for _ in range(M):
    l, r = list(map(int, input().split()))
    X[l-1][r-1] += 1
C = []
for line in X:
    tmp = [0, ]
    for c in line:
        tmp.append(tmp[-1] + c)
    C.append(tmp)
query = [map(int, input().split()) for _ in range(Q)]
# print(X)
# print(C)

for p, q in query:
    ans = 0
    for i, line in enumerate(C):
        if p-1 <= i and i <= q-1:
            ans += line[q] - line[p-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect


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

trains = [list(map(int, input().split())) for _ in range(M)]
trains = sorted(trains)
trains1 = []
trains2 = []
for l, r in trains:
    trains1.append(l)
    trains2.append(r)
query = [map(int, input().split()) for _ in range(Q)]
bleft = bisect.bisect_left
bright = bisect.bisect_right
ans = []

for p, q in query:
    li = bleft(trains1, p)
    # print(trains[:li])
    tmpTrains = sorted(trains2[li:])
    ri = bright(tmpTrains, q)
    ans.append(ri)
print("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect
import numpy as np

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

trains = [list(map(int, input().split())) for _ in range(M)]
trains = np.array(sorted(trains, key=itemgetter(0)))
query = [map(int, input().split()) for _ in range(Q)]
bleft = bisect.bisect_left
bright = bisect.bisect_right
ans = []
for p, q in query:
    li = bleft(trains[:, 0].ravel(), p)
    # print(trains[:li])
    tmpTrains = sorted(trains[li:, 1].ravel())
    ri = bright(tmpTrains, q)
    ans.append(ri)
print("\n".join(map(str, ans)))

Submission status: Time Limit Exceeded

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

trains = [list(map(int, input().split())) for _ in range(M)]
trains = np.array(sorted(trains, key=itemgetter(0)))
query = [map(int, input().split()) for _ in range(Q)]
bleft = bisect.bisect_left
bright = bisect.bisect_right
for p, q in query:
    li = bleft(trains[:, 0].ravel(), p)
    #print(trains[:li])
    tmpTrains = np.array(sorted(trains[li:, 1].ravel()))
    ri = bright(tmpTrains, q)
    print(ri)

Submission status: Time Limit Exceeded

Solution code:
[n,m,q] = map(int,input().split())
lr = []
pq = []
a = []
#print('n:{}, m:{}, q:{}'.format(n,m,q))

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

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

#print('lr:{}'.format(lr))
#print('pq:{}'.format(pq))

for i in range(q):
  if i > 0:
    for k in range(i-1):
      if pq[k][0] == pq[i][0] and pq[k][1] == pq[i][1]:
        a.append(a[k])
  if len(a) != i+1:
    cnt = 0
    for j in range(m):
      if pq[i][0] <= lr[j][0] and lr[j][1] <= pq[i][1]:
        cnt += 1
    a.append(cnt)
  print('{}'.format(a[i]))

Submission status: Time Limit Exceeded

Solution code:
[n,m,q] = map(int,input().split())
lr = []
pq = []
#print('n:{}, m:{}, q:{}'.format(n,m,q))

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

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

#print('lr:{}'.format(lr))
#print('pq:{}'.format(pq))

for i in range(q):
  cnt = 0
  for j in range(m):
    if pq[i][0] <= lr[j][0] and lr[j][1] <= pq[i][1]:
      cnt += 1
  print('{}'.format(cnt))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M, Q = map(int, input().split())
d = np.zeros([N+1, N+1], np.int32)

for _ in range(M):
	tl,tr = map(int, input().split())
	d[N-tl,tr] += 1

d = np.add.accumulate(d, axis = 1)
d = np.add.accumulate(d)

ans = []
for _ in range(Q):
	tp,tq = map(int, input().split())

	ans.append(d[N-tp,tq])

for a in ans:
	print(a)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M, Q = map(int, input().split())
d = np.zeros([N+1, N+1], np.int32)

for _ in range(M):
	tl,tr = map(int, input().split())
	d[tl,tr] += 1

d = np.add.accumulate(d, axis = 1)
d = np.flipud(d)

d = np.add.accumulate(d)

d = np.flipud(d)

ans = []
for _ in range(Q):
	tp,tq = map(int, input().split())

	ans.append(d[tp,tq])

for a in ans:
	print(a)

Submission status: Time Limit Exceeded

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

#M trains
trn = []
for i in range(M):
  cmd = list(map(int, input().split()))
  trn.append(cmd)

#Q questions
qst = []
for i in range(Q):
  cmd = list(map(int, input().split()))
  qst.append(cmd)

#hoge 電車ごとにQの条件に入るかどうか判定
flags = []
for i in range(Q):
  flags.append([])

for i in range(Q):
  flag = [0]*M
  for j in range(M):
    if trn[j][0] >= qst[i][0] and trn[j][1] <= qst[i][1]:
      flag[j] = 1
  flags[i]=flag
  
#ans 完全に含まれる列車の本数
for i in range(Q):
  ans = 0
  for j in range(M):
    ans += flags[i][j]
  print(ans)

Submission status: Time Limit Exceeded

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

#M trains
trn = []
for i in range(M):
  cmd = list(map(int, input().split()))
  trn.append(cmd)

#Q questions
qst = []
for i in range(Q):
  cmd = list(map(int, input().split()))
  qst.append(cmd)

#hoge 電車ごとにQの条件に入るかどうか判定
for i in range(Q):
  flag = [0]*M
  for j in range(M):
    if trn[j][0] >= qst[i][0] and trn[j][1] <= qst[i][1]:
      flag[j] = 1
  
  #ans 完全に含まれる列車の本数
  for k in range(Q):
    ans = 0
    for k in flag:
      ans += k
  print(ans)

Submission status: Time Limit Exceeded

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

# 各Lについて累積和を取る
LR_rui = [[0] for _ in range(n)]
for i in range(n):
    for j in range(n):
        LR_rui[i].append(LR[i][j]+LR_rui[i][-1])

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

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

for i in range(Q):
	p, q = PQ[i]
	c = 0
	for j in range(M):
		l, r = LR[j]
		if p <= l and r <= q:
			c += 1
	print(c)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

Goal=[defaultdict(int) for _ in range(N)]
for i in range(M):
    L,R=map(int,input().split())
    Goal[L-1][R-1]+=1

Accumlate = [[0]*(N+1) for i in range(N)]
for g in range(N):
    for l in range(N):
        Accumlate[g][l+1]+=Accumlate[g][l]+Goal[g][l]

ans_list=[]
for l in range(Q):
    ans=0
    L,R=map(int,input().split())
    for l in range(L-1,R):
        ans+=Accumlate[l][R]-Accumlate[l][L-1]
    ans_list.append(ans)

for m in range(Q):
    print(ans_list[m])

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

Goal=[[] for _ in range(N)]
for i in range(M):
    L,R=map(int,input().split())
    Goal[L-1].append(R-1)

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

for i in range(N):
    Goal[i].sort()

ans=[]
for g in range(Q):
    p,q=map(int,input().split())
    ans.append(bisect.bisect_right(Goal[p-1],q-1))

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


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


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def main():
    N, M, Q = read_values()
    T = [list(read_index()) for _ in range(M)]
    L0 = [0] * N
    R0 = [0] * N
    for i, (l, r) in enumerate(T):
        L0[r] += 1 << i
        R0[l] += 1 << i

    for i in range(1, N):
        L0[i] += L0[i - 1]
        R0[-i - 1] += R0[-i]

    res = [0] * Q
    for i in range(Q):
        p, q = read_index()
        t = R0[p] & L0[q]
        res[i] = str(bin(t).count("1"))

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


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


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


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def main():
    N, M, Q = read_values()
    T = [list(read_index()) for _ in range(M)]
    L0 = [0] * N
    R0 = [0] * N
    for i, (l, r) in enumerate(T):
        L0[r] += 1 << i
        R0[l] += 1 << i

    for i in range(1, N):
        L0[i] += L0[i - 1]
        R0[-i - 1] += R0[-i]

    for _ in range(Q):
        p, q = read_index()
        t = R0[p] & L0[q]
        print(bin(t).count("1"))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import fractions
import itertools
from collections import deque
import copy
import bisect
import numpy as np

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()
N, M, Q = map(int, input().split())
sum_list = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    L, R = map(int, input().split())
    sum_list[L - 1][R - 1] += 1
for i in range(N):
    sum_list[i] = list(np.cumsum(sum_list[i]))
    sum_list[i].append(0)
for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for l in range(p - 1, q):
        ans += sum_list[l][q - 1] - sum_list[l][l - 1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())  # N個の駅, M本の列車, Q個のクエリ
# 始点と終点を全て格納する
X = [[0]*501 for _ in range(501)]
# 累積和を取るための二次元リスト(累積和自体は一次元, 最後に縦方向に和を取る)
C = [[0]*501 for _ in range(501)]

for _ in range(M):
    left, right = map(lambda x: int(x)-1, input().split())
    X[left][right] += 1  # 始点と終点を全て格納する

# 横方向に累積和を取る
for i in range(N):
    for j in range(N):
        C[i][j] = C[i][j-1] + X[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())  # N個の駅, M本の列車, Q個のクエリ
lines = [list(map(int, input().split())) for _ in range(M)]
query = [list(map(int, input().split())) for _ in range(Q)]
for p, q in query:
    # pが始点, qが終点
    ans = 0
    for l, r in lines:
        if l >= p and r <= q:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import collections
import bisect
import sys
input = sys.stdin.readline

N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]
LR.sort(key=lambda x: x[1])
table = collections.defaultdict(list)
for l, r in LR:
    table[l].append(r)
for i in range(Q):
    p, q = map(int, input().split())
    ret = 0
    for j in range(p, q+1):
        ret += bisect.bisect_right(table[j], q)
    print(ret)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdout
printn = lambda x: stdout.write(str(x))
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 999999999
R = 10**9 + 7
import bisect

def ddprint(x):
  if DBG:
    print(x)

n,m,qqq = inm()
sl = [ [] for i in range(n+1) ]
for i in range(m):
    l,r = inm()
    sl[l].append(r)
for i in range(n):
    sl[i].sort()
for qq in range(qqq):
    p,q = inm()
    cnt = 0
    for r in range(p,q+1):
        b = bisect.bisect_left(sl[r],q+1)
        cnt += b
    print(cnt)