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:
a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])
ll = list()
r = list()

for _ in range(m):
    a = input().split()
    ll.append(int(a[0]))
    r.append(int(a[1]))

p = list()
q = list()

for _ in range(qq):
    a = input().split()
    p.append(int(a[0]))
    q.append(int(a[1]))

x = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    x[ll[i] - 1][r[i] - 1] += 1

c = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    for j in range(n):
        c[i][j] = x[i][j]
        if 0 < j:
            c[i][j] += c[i][j - 1]

for i in range(qq):
    r = 0

    for j in range(p[i] - 1, q[i]):
        r += c[j][q[i] - 1]
        if 1 < p[i]:
            r -= c[j][p[i] - 2]

    print(r)

Submission status: Time Limit Exceeded

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

LR = [[0 for i in range(2)] for j in range(M)]
pq = [[0 for i in range(2)] for j in range(Q)]

for i in range(M):
    LR[i] = list(map(int, input().split()))

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

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

# print(LR[0][0])

for i in range(M):
    x[LR[i][1] - 1][LR[i][0] - 1] = x[LR[i][1] - 1][LR[i][0] - 1] + 1

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

for i in range(N):
    for j in range(N):
        if j == 0:
            xacu[i][j] = x[i][j]
        else:
            xacu[i][j] = xacu[i][j - 1] + x[i][j]

# print(xacu)

for i in range(Q):
    count = 0
    p = pq[i][0]
    for j in range(pq[i][1]):
        if p == 1:
            count = count + xacu[j][N - 1]
        else:
            count = count + xacu[j][N - 1] - xacu[j][p - 2]

    print(count)

Submission status: Time Limit Exceeded

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

for i in range(N):
    trains[i+1] = {}
    for j in range(N):
        trains[i+1][j+1] = 0

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

for i in range(Q):
    p,q = map(int,input().split())
    cnt = 0
    for j in range(N-p+1):
        train = trains[N-j]
        for k in range(q):
            cnt += train[k+1]
    print(cnt)

Submission status: Time Limit Exceeded

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

import bisect
import array


def solve():
    n, m, q = map(int, input().split())
    nl = [[] for j in range(n + 1)]
    for e in (input().split() for _ in [0] * m):
        l, r = int(e[0]), int(e[1])
        bisect.insort_left(nl[l], r)
    table = [array.array("i", [0] * (n + 1)) for j in range(n + 1)]
    ran = array.array("i", range(n + 1))
    for i in ran:
        table[i] = [bisect.bisect_right(nl[i], j) for j in ran]

    a = [0] * q
    s = array.array("i", a)
    for i, e in enumerate(input().split() for _ in a):
        l, r = int(e[0]), int(e[1])
        s[i] = sum(table[j][r] - table[j][l - 1] for j in range(l, r + 1))
    print("\n".join(str(e) for e in s))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m,q = [int(i) for i in input().split()]
l = [[int(i) for i in input().split()] for j in range(m)]
p =[[int(i) for i in input().split()] for j in range(q)]

a = np.zeros((n,n))
for i in range(m):
    s = l[i][0]
    t = l[i][1]
    a[:s,t-1:] += 1 
for i in range(q):    
    u = p[i][0]
    v = p[i][1]
    print(int(a[u-1][v-1]))

Submission status: Time Limit Exceeded

Solution code:
buf = input().split()
N = int(buf[0])
M = int(buf[1])
Q = int(buf[2])
import numpy as np
train = np.zeros((N+1, N+1))
for i in range(M):
	buf = input().split()
	L = int(buf[0])
	R = int(buf[1])
	a = np.ones((N-L+1, N-R+1))
	b = np.zeros((N-L+1, R))
	c = np.zeros((L, N+1))
	d = np.concatenate((c, np.concatenate((b, a), axis=1)), axis=0)
	train += d
#print(train)
for i in range(Q):
	buf = input().split()
	p = int(buf[0])
	q = int(buf[1])
	r = train[q][q] - train[p-1][q] -train[q][p-1] + train[p-1][p-1]
	print(int(r))# your code goes here

Submission status: Time Limit Exceeded

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

import bisect
import array


def solve():
    n, m, q = map(int, input().split())
    nran = range(n + 1)
    nl = [[] for j in nran]
    for e in [input().split() for _ in [0] * m]:
        l, r = int(e[0]), int(e[1])
        bisect.insort_left(nl[l], r)
    ran = array.array("i", nran)
    table = [array.array("i", [0] * (n + 1)) for j in nran]
    for i in ran:
        table[i] = [bisect.bisect_right(nl[i], j) for j in ran]

    a = [0] * q
    s = array.array("i", a)
    for i, e in enumerate([input().split() for _ in a]):
        l, r = int(e[0]), int(e[1])
        s[i] = sum(table[j][r] - table[j][l - 1] for j in range(l, r + 1))
    print("\n".join([str(e) for e in s]))


if __name__ == "__main__":
    solve()

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

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

def lsadd(L,R):
    L-=1
    R-=1
    for i in range(0,L+1):  
        res[i][R] += 1

for l,r in LR:
    lsadd(l,r)

for p,q in pq:
    print(sum(res[p-1][:q]))

Submission status: Time Limit Exceeded

Solution code:

n,m,q=map(int,input().split())
counts=[[0 for _ in range(n)] for _ in range(n)]
for _ in range(m):
    l,r=map(int,input().split())
    counts[l-1][r-1]+=1
cumsum=[[0 for _ in range(n+1)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        cumsum[i][j+1]=cumsum[i][j]+counts[i][j]
    
for _ in range(q):
    l,r=map(int,input().split())
    print(sum(cumsum[i][r]-cumsum[i][l-1] for i in range(l-1,r)))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

import bisect
import array


def solve():
    n, m, q = map(int, input().split())
    nl = [[] for j in range(n + 1)]
    for e in [input().split() for _ in [0] * m]:
        l, r = int(e[0]), int(e[1])
        bisect.insort_left(nl[l], r)
    table = [array.array("i", [0] * (n + 1)) for j in range(n + 1)]
    ran = array.array("i", range(1, n + 1))
    for i in ran:
        for j in ran:
            table[i][j] = bisect.bisect_right(nl[i], j)

    a = [0] * q
    s = array.array("i", a)
    for i, e in enumerate([input().split() for _ in a]):
        l, r = int(e[0]), int(e[1])
        for j in range(l, r + 1):
            s[i] += table[j][r] - table[j][l - 1]
    print("\n".join([str(e) for e in s]))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
from numpy import cumsum 
n, m, q = list(map(int, input().split()))
lst = [[0]*n for i in range(n)]
for i in range(m):
    l, r = list(map(lambda x: int(x)-1, input().split()))
    lst[l][r] += 1
newlst = cumsum(lst, axis=1)
for i in range(q):
    a, b = list(map(lambda x: int(x)-1, input().split()))
    ans = sum([newlst[i][b] for i in range(a, b+1)])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
 
n, m, q = map(int, input().split())
LR = [0]*m
for i in range(m):
    LR[i] = list(map(int, input().split()))
P = [0]*q
Q = [0]*q
for i in range(q):
    P[i], Q[i] = map(int, input().split())
 
LR.sort(key=lambda x: x[0])
L = list(map(lambda x: x[0], LR))
 
for i in range(q):
    l = bisect_left(L, P[i])
    r = bisect_left(L, Q[i]+1)-1
    cnt = 0
    for j in range(l, r+1):
        if LR[j][1] <= Q[i]:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from numpy import cumsum 
n, m, q = list(map(int, input().split()))
lst = [[0]*n for i in range(n)]
for i in range(m):
    l, r = list(map(lambda x: int(x)-1, input().split()))
    lst[l][r] += 1
newlst = cumsum(lst, axis=1)
pq = list(list(map(lambda x: int(x)-1, input().split())) for i in range(q))
for a, b in pq:
    ans = sum([newlst[i][b] for i in range(a, b+1)])
    print(ans)

Submission status: Time Limit Exceeded

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

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

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

# for i in range(n):
#     print(b[i])

for k in range(q):
    l,r=map(int,input().split())
    count=0
    for i in range(l-1,r):
        if l==1:
            count+=b[i][r-1]
        else:
            count+=b[i][r-1]-b[i][l-2]
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M,Q=map(int,input().split())
mat = np.zeros((N, N), dtype=int)
for i in range (M):
    l,r =map(int,input().split())
    mat[l-1][r-1]+=1

for j in range (Q):
     l2,r2 =map(int,input().split())
     print(sum(sum(mat[l2-1:r2,l2-1:r2])))

Submission status: Time Limit Exceeded

Solution code:
n, m, q = list(map(int, input().split()))
import numpy as np
line_arr1 = np.zeros(m)
line_arr2 = np.zeros(m)
for i in range(m):
  line_arr1[i], line_arr2[i] = list(map(float, input().split()))
s1_cache = {}
s2_cache = {}
for i in range(q):
  s1, s2 = input().split()
  if s1 in s1_cache:
    flg1= s1_cache[s1]
  else:
    flg1=line_arr1 >= float(s1)
    s1_cache[s1] = flg1
  if s2 in s2_cache:
    flg2= s2_cache[s2]
  else:
    flg2=line_arr2 <= float(s2)
    s2_cache[s2] = flg2
  print(np.sum(flg1 * flg2))

Submission status: Time Limit Exceeded

Solution code:
from copy import deepcopy

N, M, Q = [int(elem) for elem in input().split(' ')]
lines = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
queries = [[int(elem) for elem in input().split(' ')] for _ in range(Q)]


def cuml_1d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1

    cuml_coords = deepcopy(coords)
    for l in range(N):
        for r in range(1, N):
            cuml_coords[l][r] = cuml_coords[l][r - 1] + coords[l][r]

    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        num_lines = 0
        for l in range(p, max(q + 1, N)):
            if p == 0:
                num_lines += cuml_coords[l][q]
            else:
                num_lines += cuml_coords[l][q] - cuml_coords[l][p - 1]
        print(num_lines)

cuml_1d(N, lines, queries)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m,Q = map(int,input().split())
p = np.zeros(Q)
q = np.zeros(Q)
a = np.zeros((n,n))
for i in range(m):
    b1,b2 = map(int,input().split())
    a[b1-1,b2-1] += 1
for i in range(Q):
    b1,b2 = map(int,input().split())
    p[i] = b1-1
    q[i] = b2-1

for i in range(Q):
    print(int(np.sum(a[int(p[i]):int(q[i])+1,int(p[i]):int(q[i])+1])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

setting = list(map(int, input().split()))

train = []
quest = []
for i in range(setting[1]):
    num = list(map(int, input().split()))
    train.append(num)

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

train = np.array(train)
train = train * np.array([1,-1])
set = np.array([-1,1])
    
ansList = []
for qs in quest:
    sch = np.array(qs) * set
    b = train.copy() + sch
    ans = np.delete(b, np.where(b<0)[0], axis=0)
    ansList.append(ans.shape[0])

for an in ansList:
    print(an)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

Submission status: Time Limit Exceeded

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

import bisect
import array


def solve():
    n, m, q = map(int, input().split())
    nl = [[] for j in range(n + 1)]
    for i in range(m):
        l, r = map(int, input().split())
        bisect.insort_left(nl[l], r)
    table = [array.array("i", [0] * (n + 1)) for j in range(n + 1)]
    r = array.array("i", range(1, n + 1))
    for i in r:
        for j in r:
            table[i][j] = bisect.bisect_right(nl[i], j)

    s = array.array("i", [0] * q)
    for i in range(q):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            s[i] += table[j][r] - table[j][l - 1]
    print("\n".join([str(e) for e in s]))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
#encoding utf-8

import numpy as np

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)

p = []
q = []

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

EXP_map = np.zeros((N,N))
for i in range(M):
    EXP_map[L[i]-1][R[i]-1] += 1

def Answer(i):
    return int(EXP_map[(p[i]-1):(q[i]),(p[i]-1):(q[i])].sum())

for i in range(Q):
    print(Answer(i))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

Submission status: Time Limit Exceeded

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

import bisect
import array


def solve():
    n, m, q = map(int, input().split())
    nl = [[] for j in range(n + 1)]
    for i in range(m):
        l, r = map(int, input().split())
        bisect.insort_left(nl[l], r)
    table = [array.array("i", [0] * (n + 1)) for j in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = bisect.bisect_right(nl[i], j)

    s = array.array("i", [0] * q)
    for i in range(q):
        l, r = map(int, input().split())
        for j in range(l, r + 1):
            s[i] += table[j][r] - table[j][l - 1]
    print("\n".join([str(e) for e in s]))


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

Train = [[0 for j in range(N+1)] for i in range(N+1)]
for j in range(M):
    l,r = map(int,input().split())
    Train[r][l] += 1
    
for i in range(N+1):
    for j in range(1,N+1):
        Train[i][j] += Train[i][j-1]
        
#print(Train)
        
OUTPUT = []
for k in range(Q):
    p,q = map(int,input().split())
    ans = 0
    for i in range(p,q+1): ans += Train[i][q] - Train[i][p-1]
    OUTPUT.append(ans)

for o in OUTPUT:
    print(o)

Submission status: Time Limit Exceeded

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

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

a = np.zeros((n,n))
for i in range(m):
    a[int(l[i]),int(r[i])] += 1


for i in range(Q):
    print(int(np.sum(a[int(p[i]):int(q[i])+1,int(p[i]):int(q[i])+1])))

Submission status: Time Limit Exceeded

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

import bisect


def solve():
    n, m, q = map(int, input().split())
    nl = [[] for j in range(n + 1)]
    for i in range(m):
        l, r = map(int, input().split())
        bisect.insort_left(nl[l], r)
    table = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = bisect.bisect_right(nl[i], j)

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


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

for _ in range(M):
    l, r = list(map(int, input().split()))
    for i in range(l):
      #  print(rails[i][r-1], "-----")
        rails[i][r-1] += 1
for i in range(N-1):
    for j in range(1, N):
        rails[i][j] += rails[i][j - 1]

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

print('\n'.join(map(str,re)))

Submission status: Time Limit Exceeded

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

import bisect


def solve():
    n, m, q = map(int, input().split())
    nl = [[] for j in range(n + 1)]
    for i in range(m):
        l, r = map(int, input().split())
        bisect.insort_left(nl[l], r)
    table = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = len([1 for k in nl[i] if k <= j])

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


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

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

ans = [[0]*N for _ in range(N)]

for _ in range(M):
        L,R = map(int,input().split())
        for i in range(N):
                for j in range(i,N):
                        if i<=(L-1) and (R-1)<=j:
                                ans[i][j] += 1
for _ in range(Q):
        p,q = map(int,input().split())
        print(ans[p-1][q-1])

Submission status: Time Limit Exceeded

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

d = [[] for i in range(N)]
 
m = 0
while m < M:
  a,b = map(int, input().split())
  d[a-1].append(m)
  d[b-1].append(m)
  m += 1

q = 0
while q < Q:
  max = 0
  a,b = map(int, input().split())
  arr = functools.reduce(lambda x, y: x + y, d[a-1:b])
  print(len(set([i for i in arr if arr.count(i) == 2])))
  q += 1

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter


def bin(ll, target, key):  # リストにtargetが最初に含まれる位置
    if len(ll) < 100:
        if target in [key(a) for a in ll]:
            return [key(a) for a in ll].index(target)
        return -1

    length = len(ll)
    l, r = ll[:length // 2], ll[length // 2:]
    if key(r[0]) == target:
        if key(l[-1]) != target:
            return len(l)
        return bin(l, target, key)
    elif key(r[0]) > target:
        return bin(l, target, key)
    else:
        return len(l) + bin(r, target, key)


def main():
    n, m, q = [int(a) for a in input().split()]
    QQQ = q
    LRi = sorted([[int(a) for a in input().split()] for _ in range(m)], key=lambda it: it[0])

    PQi = [([int(a) for a in input().split()], k) for k in range(q)]
    # PQi = sorted(PQi, key=lambda a: a[0][1])
    # PQi = sorted(PQi, key=lambda a: a[0][0])

    TABLE = []  # iから始まる列車のRとその数
    ii = 0
    for i in range(1, n + 1):
        a = []  # iから伸びる列車の右端
        while True:
            if ii >= len(LRi):
                break
            l, r = LRi[ii]
            if l == i:
                a.append(r)
                ii += 1
            else:
                break
        # a = sorted(a)
        c = Counter(a)

        TABLE.append([(a, c[a]) for a in sorted(c.keys())])

    TABLE2 = []  # iから始まってjまでで終わる電車TABLE[i,j]
    for i in range(1, 1 + n):
        trains = TABLE[i - 1]  # iから始まる電車
        c = 0
        res = []  # jまでで終わる電車の数
        ccc = 0
        for j in range(1, n + 1):
            while True:
                if c >= len(trains):
                    break
                dst, num = trains[c]
                if dst <= j:
                    ccc += num
                    c += 1
                else:
                    break
            res.append(ccc)
        TABLE2.append(res)

    for (p, q), k in PQi:
        c = 0
        for i in range(p, q + 1):
            c += TABLE2[i - 1][q-1]
        print(c)

    # ii = 0
    # res = {}
    # while True:
    #     if ii >= len(PQi):
    #         break
    #
    #     (l, r), k = PQi[ii]# pqに対して、その範囲内のカウンタ全部取得
    #     counts = []
    #     for i in range(l, r + 1):
    #         count = TABLE[i - 1]  # タプル kまでの数v
    #         for rrrr, nnnnn in count:
    #             if rrrr <= r:
    #                 counts.append((rrrr, nnnnn))
    #             else:
    #                 break
    #     lls = [(r, k)]  # 同じlから始まるQ
    #     ii += 1
    #     while True:
    #         if ii >= len(PQi):
    #             break
    #         (ll, rr), kk = PQi[ii]
    #         if ll == r:
    #             lls.append((rr, kk))
    #             ii += 1
    #         else:
    #             break
    #
    #     lls = sorted(lls, key=lambda a: a[0])
    #     b = 0
    #     c = 0
    #     for r, k in lls:
    #         while True:
    #             if c >= len(counts):
    #                 break
    #             kk, v = counts[c]
    #             if kk <= r:
    #                 b += v
    #                 c += 1
    #             else:
    #                 break
    #         res[k] = b
    # for i in range(QQQ):
    #     print(res[i])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m, Q = map(int, input().split())
lr = [[0] * n for i in range(n)]
for _ in range(m):
  l, r = map(int, input().split())
  lr[l-1][r-1] += 1
pq = [list(map(int, input().split())) for _ in range(Q)]
for i in pq:
  p = i[0]
  q = i[1]
  ans = 0
  for j in range(p-1, q):
    for k in range(p-1, q):
      ans += lr[j][k]
  print(ans)

Submission status: Time Limit Exceeded

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

import sys


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

    x = [[0 for j in range(n+1)] for i in range(n+1)]
    c = [[0 for j in range(n+1)] for i in range(n+1)]

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().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):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        ans = 0
        for j in range(qp, qq+1):
            ans += c[j][qq] - c[j][qp-1]
        print(ans)


if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n, m, q = list(map(int, input().split()))
import numpy as np
line_arr1 = np.zeros(m)
line_arr2 = np.zeros(m)
for i in range(m):
  line_arr1[i], line_arr2[i] = list(map(float, input().split()))
for i in range(q):
  s1, s2 = input().split()
  flg1=line_arr1 >= float(s1)
  flg2=line_arr2 <= float(s2)
  print(np.sum(flg1 & flg2))

Submission status: Time Limit Exceeded

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

N_LR = [[0 for i in range(N+1)] for j in range(N+1)]

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

S_LR = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(1,N+1):
    S_LR[i][j] = S_LR[i-1][j] + N_LR[i][j]

for i in range(Q):
  x,y = map(int, input().split() )
  ans = 0
  for j in range(x, y+1):
    ans += S_LR[y][j] - S_LR[x-1][j]  
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = (int(i) for i in input().rstrip().split())

ds = [set() for _ in range(n)]
de = [set() for _ in range(n)]
for i in range(m):
    l, r = (int(i) for i in input().rstrip().split())
    for j in range(l):
        ds[j].add(i)
    for j in range(r - 1, n):
        de[j].add(i)

for i in range(q):
    pi, qi = (int(i) for i in input().rstrip().split())
    print(len(ds[pi - 1] & de[qi - 1]))

Submission status: Time Limit Exceeded

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

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

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

for i in range(q):
    l,r=map(int,input().split())
    count=0
    for j in range(r-l+1):
        for k in range(r-l+1):
            count+=a[j+l-1][k+l-1]
    print(count)

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
trains = list()
for i in range(M):
    trains.append(list(map(int,input().split())))
trains = sorted(trains, key=lambda x:x[0], reverse=True)

for i in range(Q):
    p,q = map(int,input().split())
    cnt = 0
    for train in trains:
        l = train[0]
        r = train[1]
        if (p <= l):
            if (r <= q):
                cnt+=1
        else:
            break
    print(cnt)

Submission status: Time Limit Exceeded

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

LR = []
pq = []

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

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

for i in pq:
    count = 0
    for j in LR:
        if j[0] >= i[0]:
            if j[1] <= i[1]:
                count += 1

    print(count)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = list(map(int, input().split()))
import numpy as np
line_arr1 = np.zeros(m)
line_arr2 = np.zeros(m)
for i in range(m):
  line_arr1[i], line_arr2[i] = list(map(int, input().split()))
for i in range(q):
  s1, s2 = input().split()
  print(np.sum((line_arr1 >= int(s1)) & (line_arr2 <= int(s2))))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

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

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

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

Submission status: Time Limit Exceeded

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

def main():
    N, M, Q = map(int, input().split())
    lr = [tuple(map(int, input().split())) for x in range(M)]
    pq = [tuple(map(int, input().split())) for x in range(Q)]
    for i, j in pq : print(sum(1 for l, r in lr if i<=l and r<=j))
    
if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n, m, q = list(map(int, input().split()))
import numpy as np
line_arr1 = np.zeros(m)
line_arr2 = np.zeros(m)
for i in range(m):
  line_arr1[i], line_arr2[i] = list(map(int, input().split()))
for i in range(q):
  s1, s2 = input().split()
  flg1=line_arr1 >= int(s1)
  flg2=line_arr2 <= int(s2)
  print(np.sum(flg1 & flg2))

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
line = input().split(" ")
N = int(line[0])
M = int(line[1])
Q = int(line[2])

memo = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    line = input().split(" ")
    l = int(line[0])
    r = int(line[1])
    memo[l][r] += 1

for _ in range(Q):
    line = input().split(" ")
    p = int(line[0])
    q = int(line[1])

    ret = 0
    for i in range(p,q+1):
        for j in range(i,q+1):
            ret += memo[i][j]
    print(ret)

Submission status: Time Limit Exceeded

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

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

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

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

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

res = []
for _ in range(qq):
    ans = 0
    p, q = map(int, input().split())
    for i in range(p, q + 1):
        ans += acc[i][q] - acc[i][i - 1]
    res.append(ans)

for row in res:
    print(row)