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:
import collections
import bisect
import copy
def main():

    N, M, Q = map(int, input().split())
    train = []
    for _ in range(M):
        l, r = map(int, input().split())
        train.append([l, r])
    train.sort()
    # print(train)

    end = []
    ends = []
    j = M-1
    for i in range(N, 0, -1):
        while j >= 0 and train[j][0] >= i:
            l, r = train[j]
            bisect.insort(end, r)
            j -= 1
        ends.append(copy.copy(end))
    ends.append([])
    ends = ends[::-1]
    # print(N)
    # print(ends)

    for _ in range(Q):
        p, q = map(int, input().split())
        j = bisect.bisect_right(ends[p], q)
        print(j)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_right
from operator import itemgetter

N,M,Q = II()
x = []
for _ in range(M):
    L,R = II()
    x.append((L-1, R-1))
query = []
for _ in range(Q):
    p0,q0 = II()
    query.append((p0-1,q0-1))

x.sort(key=itemgetter(1))

y = [[float('inf')]*M for _ in range(N)]
c = [0]*N
for i in range(M):
    for j in range(x[i][0]+1):
        y[j][c[j]] = x[i][1]
        c[j] += 1

ans = 0
for q in query:
    print(bisect_right(y[q[0]], q[1]))

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_right

N,M,Q = II()
x = []
for i in range(M):
    L,R = II()
    x.append([L-1, R-1])
p,q = Line(Q)


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

y = [[float('inf')]*M for _ in range(N)]
c = [0]*N
for i in range(M):
    for j in range(x[i][0]+1):
        y[j][c[j]] = x[i][1]
        c[j] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

from bisect import bisect_right

N,M,Q = II()
x = []
for i in range(M):
    L,R = II()
    x.append([L-1, R-1])
p,q = Line(Q)


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

y = [[] for _ in range(N)]
for i in range(M):
    for j in range(x[i][0]+1):
        y[j].append(x[i][1])

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

Submission status: Time Limit Exceeded

Solution code:
import os, sys, re, math

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

table = [[0 for j in range(N)] for i in range(N)]
for i in range(M):
    l,r = map(int,input().split(' '))
    table[l-1][r-1] += 1

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

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1
 
memo_g = {}
def g(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_g:
        memo_g[(p, q)] = st_ed.get((p, q), 0) + g(p + 1, q)
    return memo_g[(p, q)]
 
def f(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    return f(p, q - 1) + g(p, q)
 
memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = f(p, q)
        memo[(p, q)] = temp
    print(memo[(p, q)])

Submission status: Time Limit Exceeded

Solution code:
line = raw_input()
N, M, Q = [int(s) for s in line.split(' ')]
starts = dict()
ends =  dict()

lrs = []
for i in range(M):
    line = raw_input()
    l, r = [int(s) for s in line.split(' ')]
    lrs.append((l, r))
    s = starts.get(l, set())
    s.add(i)
    starts[l] = s
    e = ends.get(r, set())
    e.add(i)
    ends[r] = e

pqs = []
rets = []
for i in range(Q):
    line = raw_input()
    p, q = [int(s) for s in line.split(' ')]
    pqs.append((p, q))
    pset = set()
    qset = set()
    for d in range(p, q + 1): 
        pset |= starts.get(d, set())
        qset |= ends.get(d, set())
    ret = len(pset & qset)
    rets.append(ret)

for ret in rets:
    print ret

Submission status: Time Limit Exceeded

Solution code:
import os, sys, re, math

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

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

p = []
q = []
memo = dict()
for i in range(Q):
    (pi, qi) = [int(j) for j in input().split()]
    if (pi, qi) in memo:
        count = memo[(pi, qi)]
    else:
        count = 0
        for j in range(M):
            if (pi <= L[j] and R[j] <= qi):
                count += 1
        memo[(pi, qi)] = count
    print (str(count))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1

memo_s = {}
# memo[(p, q)] = memo[(p, q-1)] + sum([st_ed.get((i, q), 0) for i in [1,2,3...p]])
def f(p, q):
    if p == q:
        return st_ed.get((p, q), 0)
    if not (p, q) in memo_s:
        temp = f(p, q - 1)
        for i in range(p, q + 1):
            temp += st_ed.get((i, q), 0)
        memo_s[(p, q)] = temp
    return memo_s[(p, q)]

memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = f(p, q)
        memo[(p, q)] = temp
    print(memo[(p, q)])

Submission status: Time Limit Exceeded

Solution code:
import os, sys, re, math

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

L = []
R = []
for i in range(M):
    (Li, Ri) = [int(j) for j in input().split()]
    L.append(Li)
    R.append(Ri)
p = []
q = []
for i in range(Q):
    count = 0
    (pi, qi) = [int(j) for j in input().split()]
    for j in range(M):
        if (pi <= L[j] and R[j] <= qi):
            count += 1
    print (str(count))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1

memo_s = {}
# memo[(p, q)] = memo[(p, q-1)] + sum([st_ed.get((i, q), 0) for i in [1,2,3...p]])
def f(p, q):
    if (p, q) in memo_s:
        return memo_s[(p, q)]
    if p == q:
        return st_ed.get((p, q), 0)
    temp = f(p, q - 1)
    for i in range(p, q + 1):
        temp += st_ed.get((i, q), 0)
    return temp
    
memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = f(p, q)
        memo[(p, q)] = temp
    print(memo[(p, q)])

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = list(map(int, input().split(' ')))
st_ed = {}
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    st_ed[(l, r)] = st_ed.get((l, r), 0) + 1
memo = {}
for i in range(Q):  # 1e5
    p, q = list(map(int, input().split(' ')))
    if not (p, q) in memo:
        temp = 0
        for j in range(p, q + 1):  # * 5e2 = 5e7
            for k in range(j, q + 1):  # * 5e2 = 2.5e10 > 2e10 ...
                temp += st_ed.get((j, k), 0)
        memo[(p, q)] = temp
    print(memo[(p, q)])

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = list(map(int, input().split(' ')))
LR = []
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    LR.append((l, r))
pq = []
for i in range(Q):
    p, q = list(map(int, input().split(' ')))
    pq.append((p, q))

memo = {}
for p, q in pq:
    if (p, q) not in memo:
        memo[(p, q)] = sum([(p <= l and r <= q) for l, r in LR])
    print(memo[(p, q)])

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = list(map(int, input().split(' ')))
LR = []
for i in range(M):
    l, r = list(map(int, input().split(' ')))
    LR.append((l, r))
pq = []
for i in range(Q):
    p, q = list(map(int, input().split(' ')))
    pq.append((p, q))

for p, q in pq:
    print(sum([(p <= l and r <= q) for l, r in LR]))

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

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

for i in range(m):
    l = lr[i][0]
    r = lr[i][1]
    sq[l-1][r-1] += 1

c = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if j == 0:
            c[i][j] = sq[i][j]
        else:
            c[i][j] = sq[i][j] + c[i][j-1]
            
for i in range(q):
    p = pq[i][0]
    q = pq[i][1]
    ans = 0
    for j in range(p, q + 1):
        if p != 1:
            ans += c[j-1][q-1] - c[j-1][p-2]
        else:
            ans += c[j-1][q-1]
    print(ans)

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

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

for i in range(m):
    l = lr[i][0]
    r = lr[i][1]
    sq[l-1][r-1] += 1

for i in range(q):
    p = pq[i][0]
    q = pq[i][1]
    ans = 0
    for j in range(p, q + 1):
        ans += sum(sq[j-1][:q]) - sum(sq[j-1][: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)]
D = [[0 for _ in range(N+1)] for _ in range(N)]

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

Submission status: Time Limit Exceeded

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

X = np.zeros((N, N))
D = np.zeros((N, N+1))

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

Submission status: Time Limit Exceeded

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

D = np.zeros((N,N+1))
for i in range(M):
  L, R = map(int, input().split())
  D[L-1][:R] += 1
for i in range(Q):
  p, q = map(int, input().split())
  p -= 1
  q -= 1
  ans = 0
  for j in range(p,q+1):
    ans += D[j][p] - D[j][q+1]
  print (int(ans))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

D = dd(list)
for i in range(M):
  L, R = map(int, input().split())
  D[L-1].append(R-1)
#  D[R-1] = L-1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = np.zeros((n+1,n+1))

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

a = np.zeros((n+1,n+1))

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

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

Submission status: Time Limit Exceeded

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

s = [[0 for i in range(n+1)] for j in range(n+1)]
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())
  s[l][r] += 1

for i in range(n+1):
  ss = 0
  for j in range(n+1):
    ss += s[i][j]
    c[i][j] += ss

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

Submission status: Time Limit Exceeded

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

X = [[0 for j in range(510)] for i in range(510)]
C = [[0 for j in range(510)] for i in range(510)]

LR = []
for i in range(M):
    L, R = map(int, 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):
    p, q = map(int, input().split())
    sum = 0
    for j in range(p, q+1):
        sum += C[j][q]-C[j][p-1]
    print(sum)

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

XY = [[0 for _ in range(N)] for _ in range(N)]
for l, r in LR:
    XY[l - 1][r - 1] += 1

for i in range(N):
    for j in range(N - 1):
        XY[i][j + 1] += XY[i][j]

for p, q in pq:
    count = 0
    for i in range(p - 1, q):
        if p - 2 >= 0:
            count += XY[i][q - 1] - XY[i][p - 2]
        else:
            count += XY[i][q - 1] - 0
    print(count)

Submission status: Time Limit Exceeded

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

n, m, q = map(int, input().split())
t = [ [0] * (n+1) for _ in range(n+1) ]
qq = []
for _ in range(m):
    l, r = map(int, input().split())
    t[l][r] += 1
for _ in range(q):
    tmp = list(map(int, input().split()))
    qq.append(tmp)

s = [ [0] * (n+1) for _ in range(n+1) ]
for i in range(1, n+1):
    tmp = 0
    for j in range(1, n+1):
        tmp += t[i][j]
        s[j][i] = tmp

x = [ [0] * (n+1) for _ in range(n+1) ]
for i in range(1, n+1):
    for j in range(i, n+1):
        tmp = 0
        for k in range(i, j+1):
            tmp += s[j][k]
        x[i][j] = tmp

for qqq in qq:
    print(x[qqq[0]][qqq[1]])

Submission status: Time Limit Exceeded

Solution code:

sortsecond = lambda val: val[1]
N, M, Q = map(int, input().split())
l=[]
p=[]
for i in range(M):
    t=input().split()
    l.append((int(t[0]),int(t[1])))
for i in range(Q):
    t=input().split()
    p.append((int(t[0]),int(t[1])))

ans = int(0)
count = int(0)
sumTrain = [[0 for i in range(N+1)] for j in range(N+1)]
ansTrain = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    sumTrain[l[i][0]][l[i][1]] += 1

for i in range(N):
    for j in range(N):
        for k in range(i,j+1):
            for l in range(k,j+1):
                ansTrain[i+1][j+1] += sumTrain[k+1][l+1]


for i in range(Q):
    ans = ansTrain[p[i][0]][p[i][1]]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys, math, fractions, itertools


def solve(X, N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    C = [[0 for _ in range(509)] for _ in range(509)]
    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):
        su = 0
        for j in range(p[i], q[i]+1):
            su += C[j][q[i]] - C[j][p[i]-1]
        print(su)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]" 
    R = [int()] * (M)  # type: "List[int]" 
    X = [[0 for _ in range(509)] for _ in range(509)]
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
        X[L[i]][R[i]] += 1
    p = [int()] * (Q)  # type: "List[int]" 
    q = [int()] * (Q)  # type: "List[int]" 
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(X, N, M, Q, L, R, p, q)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

station = [[0]*N for i in range(N)]

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

DP = [[0]*(N) for i in range(N)]

for i in range(N):
    for j in range(N):
        for a in range(i,j+1):
            for b in range(i,j+1):
                DP[i][j] += station[a][b]

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

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
Left = [0 for _ in range(N)]
Right = [0 for _ in range(N)]
V = [[] for _ in range(N)]
for _ in range(M):
    l, r = map(int, input().split())
    Left[l-1] += 1
    Right[r-1] += 1
    V[r-1].append(l-1)

PQ = [list(map(int, input().split())) for _ in range(Q)]

T = [[0 for _ in range(N)] for _ in range(N)]
a = M
nextl = 0
for l in range(N):
    b = a - nextl
    nextl = Left[l]
    nextr = 0
    for r in range(N-1, l-1, -1):
        T[l][r] = max(b - nextr, 0)
        nextr += Right[r]
        for li in V[r]:
            if li < l:
                nextr -= 1
    a = b


for p, q in PQ:
    print(T[p-1][q-1])

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
 
tr_li = [list(map(int, input().split())) for _ in range(m)]
q_li = [list(map(int, input().split())) for _ in range(q)]
for i in q_li:
    tr_li_copy = tr_li.copy()
    tr_li_copy.append([i[0], 0])
    tr_li_copy.append([501, i[1]])
    tr_li_copy.sort(key = lambda x: (x[0], x[1]))
    tr_li_copy = tr_li_copy[tr_li_copy.index([i[0],  0]) + 1:]
    tr_li_copy.sort(key = lambda x: (x[1], x[0]))
    tr_li_copy = tr_li_copy[:tr_li_copy.index([501,  i[1]])]
    print(len(tr_li_copy))
    del tr_li_copy

Submission status: Time Limit Exceeded

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

tr_li = [list(map(int, input().split())) for _ in range(m)]
q_li = [list(map(int, input().split())) for _ in range(q)]
for i in q_li:
    li = [1 for j in tr_li if (j[0] >= i[0] and j[1] <= i[1])]
    print(len(li))

Submission status: Time Limit Exceeded

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

tr_li = [list(map(int, input().split())) for _ in range(m)]
q_li = [list(map(int, input().split())) for _ in range(q)]
for i in q_li:
    
    li = [j for j in tr_li if (j[0] >= i[0] and j[1] <= i[1])]
    print(len(li))
    del li

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
m_list = [list(map(int, input().split())) for _ in range(m)]
q_list = [list(map(int, input().split())) for _ in range(q)]
for q in q_list:
  count = 0
  for m in m_list:
    if q[0] <= m[0] and m[1] <= q[1]:
      count += 1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
LR = [list(map(int,input().split())) for i in range(m)]
PQ = [list(map(int,input().split())) for i in range(q)]
#print(LR,PQ)

d = [[0]*n for i in range(n)]

for i in range(m):
    l = LR[i][0]-1
    r = LR[i][1]-1
    d[l][r] += 1
#print(d)

for i in range(q):
    l = PQ[i][0]-1
    r = PQ[i][1]-1
    cnt = 0
    for j in range(l,r+1):
        for k in range(l,r+1):
            cnt += d[j][k]
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int, input().split())
train = []
quest = []
ans = []
for i in range(M):
    train.append([int(x) for x in input().split()])
for j in range(Q):
    quest.append([int(x) for x in input().split()])
for k in range(Q):
    c = 0
    for l in range(M):
        if quest[k][0] <= train[l][0] and train[l][1] <= quest[k][1]:
            c += 1
    ans.append(c)
for m in range(Q):
    print(ans[m])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

    check = np.array([[0] * (N+1) for i in range(N+1)])

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

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

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

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

check = np.array([[0] * (N+1) for i in range(N+1)])

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

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

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

Submission status: Time Limit Exceeded

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

check = np.array([[0] * (N+1) for i in range(N+1)])

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

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for s in range(p, q+1):
        for end in start[s]:
            if end <= q:
                ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
N=550
A=[]
for i in range(M+Q):
    L,R=map(int,input().split())
    A.append([L,R])
#print(A)
B = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    B[A[i][0]][A[i][1]] +=1
#print(*B,sep='\n')
C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    for k in range(N):
        if k==0:
            C[i][k] = B[i][k]
        else:
            C[i][k] += C[i][k-1]+B[i][k]
#print('\n')
#print(*C,sep='\n')
for i in range(M,M+Q):
    total=0
    for k in range(N):
        if A[i][0]<=k<=A[i][1]:
            total+=C[k][A[i][1]]-C[k][A[i][0]-1]
    print(total)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
N=800
A=[]
for i in range(M+Q):
    L,R=map(int,input().split())
    A.append([L,R])
#print(A)
B = [[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
    B[A[i][0]][A[i][1]] +=1
#print(*B,sep='\n')
C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(N):
    for k in range(N):
        if k==0:
            C[i][k] = B[i][k]
        else:
            C[i][k] += C[i][k-1]+B[i][k]
#print('\n')
#print(*C,sep='\n')
for i in range(M,M+Q):
    total=0
    for k in range(N):
        if A[i][0]<=k<=A[i][1]:
            total+=C[k][A[i][1]]-C[k][A[i][0]-1]
    print(total)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

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

s = copy.deepcopy(train_map)

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

for i in range(n):
    tmp = 0
    for j in range(n):
        tmp += train_map[i][j]
        s[i][j] = tmp

for i in range(q):
    st, go = map(int, input().split())
    number = 0
    for j in range(st-1, go):
        if st ==1:
            number += s[j][go-1]
            continue
        number += s[j][go-1] - s[j][st-2]
    numbers.append(number)

for num in numbers:
    print(num)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

train_map = []
numbers = []

for i in range(n):
    train_map.append([])
    for j in range(n):
        train_map[i].append(0)

s = copy.deepcopy(train_map)

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

for i in range(n):
    tmp = 0
    for j in range(n):
        tmp += train_map[i][j]
        s[i][j] = tmp

for i in range(q):
    st, go = map(int, input().split())
    number = 0
    for j in range(st-1, go):
        if st ==1:
            number += s[j][go-1]
            continue
        number += s[j][go-1] - s[j][st-2]
    numbers.append(number)

for num in numbers:
    print(num)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

train_map = []
numbers = []

for i in range(n):
    train_map.append([])
    for j in range(n):
        train_map[i].append(0)

s = copy.deepcopy(train_map)

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

for i in range(n):
    tmp = 0
    for j in range(n):
        tmp += train_map[i][j]
        s[i][j] = tmp

for i in range(q):
    st, go = map(int, input().split())
    number = 0
    for j in range(st-1, go):
        number += s[j][go-1]
    numbers.append(number)

for num in numbers:
    print(num)

Submission status: Time Limit Exceeded

Solution code:
import copy

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

trains = []
sections = []

train_map = []
numbers = []

for i in range(n):
    train_map.append([])
    for j in range(n):
        train_map[i].append(0)

s = copy.deepcopy(train_map)

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

for i in range(n):
    tmp = 0
    for j in range(n):
        tmp += train_map[i][j]
        s[i][j] = tmp

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

for num in numbers:
    print(num)

Submission status: Time Limit Exceeded

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

lr = [ [0]*(N+1) for i in range(N+1)]
for i in range(M):
    l,r = LR[i][0],LR[i][1]
    lr[l][r] += 1

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

Submission status: Time Limit Exceeded

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

trains = []
sections = []

for i in range(m):
    trains.append(tuple(map(int, input().split())))

#print(trains)

for i in range(q):
    sections.append(tuple(map(int, input().split())))

#print(sections)

trains = sorted(trains, key=lambda x: x[0])


for section in sections:
    number = 0
    flag = False
    for train in trains:
        if section[0] <= train[0]:
            if train[1] <= section[1]:
                number += 1
                #print('in')
            flag = True
        elif flag:
            1
            print('out')
            #continue

    print(number)

Submission status: Time Limit Exceeded

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

trains = []
sections = []

for i in range(m):
    trains.append(tuple(map(int, input().split())))

#print(trains)

for i in range(q):
    sections.append(tuple(map(int, input().split())))

#print(sections)

trains = sorted(trains, key=lambda x: x[0])


for section in sections:
    number = 0
    flag = False
    for train in trains:
        if section[0] <= train[0]:
            if train[1] <= section[1]:
                number += 1
                #print('in')
            flag = True
        elif flag:
            #print('out')
            continue

    print(number)

Submission status: Time Limit Exceeded

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

trains = []
sections = []

for i in range(m):
    trains.append(tuple(map(int, input().split())))

#print(trains)

for i in range(q):
    sections.append(tuple(map(int, input().split())))

#print(sections)

for section in sections:
    number = 0
    for train in trains:
        if section[0] <= train[0] and train[1] <= section[1]:
            number += 1
    print(number)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int,input().split())
t = [list(map(int,input().split())) for i in range(m)]
cond = [list(map(int,input().split())) for j in range(q)]
for i in range(q):
    cond1 = [1 if t[j][0] >= cond[i][0] and t[j][1] <= cond[i][1] else 0 for j in range(m)]
    print(sum(cond1))