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: Runtime Error

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

temp = [ [0 for _ in range(n)] for _ in range(n)]
tables = [ [0 for _ in range(n)] for _ in range(n)]

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

pq = [tuple(int(x) - 1 for x in input().split()) for _ in range(q)]

for i in range(m):
    hoge = 0
    for j in range(m):
        hoge += temp[i][j]
        tables[i][j] = hoge

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

Submission status: Runtime Error

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

    n_list = [[0 for _ in range(N+1)] for _ in range(N+1)]
    for _ in range(M):
        l1, l2 = map(int, input().split())
        n_list[l1][l2] += 1

    question_list = []

    for _ in range(Q):
        ans = 0

        p1, p2 = map(int, input().split()))

        p1, p2

        n_exp = 0
        for i in range(p1, p2+1):
            n_exp += sum(n_list[i][p1:p2+1])

        print(n_exp)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

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

    express_list = []
    for _ in range(M):
        express_list.append(list(map(int, input().split())))

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

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

    for l in express_list:
        l1, l2 = l[:]
        n_list[l1][l2] += 1


    for q in question_list:
        ans = 0

        p1, p2 = q[:]

        n_exp = 0
        for i in range(p1):
            n_exp += sum(n_list[i][0:p2])

        print(n_exp)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
    N, M, Q = map(int, input().split())
    rail = []
    for i in range(M):
        r = list(map(int, input().split()))
        rail.append(r)
     
    query = []
    for i in range(Q):
        q = list(map(int, input().split()))
        query.append(q)
     
    f = [[0 for i in range(N)] for j in range(N)]
    g = [[0 for i in range(N)] for j in range(N)]
     
    for i in range(M):
        f[rail[i][0]-1][rail[i][1]-1] += 1
     
    for i in range(N):
        j = 0
        while j + i < N:
            if i == 0:
                g[j][j+i] = f[j][j+i]
            else:
                g[j][j+i] = f[j][j+i] + g[j+1][j+i] + g[j][j+i-1] - g[j+1][j+i-1]
            j += 1
     
    for i in range(Q):
        print(g[query[i][0]-1][query[i][1]-1])

Submission status: Runtime Error

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

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

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


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

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

for _ in range(q):
    l,r = map(int,input().split())
    print(field[r][r]-field[l-1][l-1]-field[l-1][q]-field[q][l-1])

Submission status: Runtime Error

Solution code:
N,M,Q = map(int,input().split())
t,ans = [[0 for j in range(N+1)] for i in range(N+1)],[[-1 for j in range(N+1)] for i in range(N+1)]
def solve(x, y):
	global ans,N,t
	if x > N or y == 0:
		return 0
	elif ans[x][y] != -1:
		return ans[x][y]
	else:
		ans[x][y] = solve(x,y-1) + solve(x+1,y) - solve(x+1,y-1) + t[x][y]
		return ans[x][y]
for i in range(M):
	l,r = map(int,input().split())
	t[l][r] += 1
for i in range(Q):
	p,q = map(int,input().split())
	print(solve(p,q))

Submission status: Runtime Error

Solution code:
input_s = str(input())
[l, m, q] = list(map(int, input_s.split(" ")))
rosen = []
for i in range(0,m):
    input_tmp = str(input())
    rosen.append(list(map(int, input_tmp.split(" "))))
results = []
for i in range(0, q):
    result = 0
    input_tmp = str(input())
    list_tmp = list(map(int, input_tmp.split(" ")))
    result = [r for r in l if list_tmp[0] <= r[0] and r[1] <= list_tmp[1]]
    results.append(result)

for result in results:
    print(len(result))

Submission status: Runtime Error

Solution code:
##answer##
N, M, Q = map(int,input().split())
MAP = [[[0] *N ] * N ]

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

for i in range(N):
    for j in range(1, N):
        k = N - j - 1
        MAP[i][k] += MAP[i][k + 1]

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

Submission status: Runtime Error

Solution code:
##answer##
N, M, Q = map(int,input().split())
MAP = [[[0] *N ] * N ]

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

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

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

Submission status: Runtime Error

Solution code:
import numpy as np
def solve(tX,tY,qX,qY):
    qX = np.array(qX, dtype = 'int16')
    qY = np.array(qY, dtype = 'int16')
    qX = tX - qX
    qY = qY - tY
    qX = qX>=0
    qY = qY>=0
    qY = qX * qY
    ans = np.sum(qY, axis=1)
    answer.extend(ans.tolist())

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

trainX = []
trainY = []
questX = []
questY = []
answer = []
for i in range(setting[1]):
    x, y = map(int, input().split())
    trainX.append(x)
    trainY.append(y)

trainX = np.array(trainX, dtype = 'int16')
trainY = np.array(trainY, dtype = 'int16')
count = 0

for i in range(setting[2]):
    count+=1
    x, y = map(int, input().split())
    questX.append([x])
    questY.append([y])
    if count>4095:
        tX = np.copy(trainX)
        tY = np.copy(trainY)
        solve(tX,tY,questX,questY)
        questX.clear()
        questY.clear()

solve(trainX,trainY,questX,questY)
for item in answer:
    print(item)

Submission status: Runtime Error

Solution code:
import numpy as np
def solve(tX,tY,qX,qY):
    qX = np.array(qX, dtype = 'int16')
    qY = np.array(qY, dtype = 'int16')
    qX = tX - qX
    qY = qY - tY
    qX = qX>=0
    qY = qY>=0
    qY = qX * qY
    ans = np.sum(qY, axis=1)
    answer.extend(ans.tolist())

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

trainX = []
trainY = []
questX = []
questY = []
answer = []
for i in range(setting[1]):
    x, y = map(int, input().split())
    trainX.append(x)
    trainY.append(y)

trainX = np.array(trainX, dtype = 'int16')
trainY = np.array(trainY, dtype = 'int16')
count = 0

for i in range(setting[2]):
    x, y = map(int, input().split())
    questX.append([x])
    questY.append([y])
    if count>63:
        tX = np.copy(trainX)
        tY = np.copy(trainY)
        solve(tX,tY,questX,questY)
        questX.clear()
        questY.clear()

solve(trainX,trainY,questX,questY)
for item in answer:
    print(item)

Submission status: Runtime Error

Solution code:
import numpy as np
def solve(tX,tY,qX,qY):
    qX = np.array(qX)
    qY = np.array(qY)
    qX = tX - qX
    qY = qY - tY
    qX = qX>=0
    qY = qY>=0
    qY = qX * qY
    ans = np.sum(qY, axis=1)
    answer.extend(ans.tolist())

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

trainX = []
trainY = []
questX = []
questY = []
answer = []
for i in range(setting[1]):
    x, y = map(int, input().split())
    trainX.append(x)
    trainY.append(y)

trainX = np.array(trainX)
trainY = np.array(trainY)
count = 0

for i in range(setting[2]):
    x, y = map(int, input().split())
    questX.append([x])
    questY.append([y])
    if count >128:
        tX = np.copy(trainX)
        tY = np.copy(trainY)
        solve(tX,tY,questX,questY)
        questX.clear()
        questY.clear()

solve(trainX,trainY,questX,questY)
for item in answer:
    print(item)

Submission status: Runtime Error

Solution code:
import numpy as np
def solve(tX,tY,qX,qY):
    qX = np.array(qX)
    qY = np.array(qY)
    qX = tX - qX
    qY = qY - tY
    qX = qX>=0
    qY = qY>=0
    qY = qX * qY
    ans = np.sum(qY, axis=1)
    answer.extend(ans.tolist())

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

trainX = []
trainY = []
questX = []
questY = []
answer = []
for i in range(setting[1]):
    x, y = map(int, input().split())
    trainX.append(x)
    trainY.append(y)

trainX = np.array(trainX)
trainY = np.array(trainY)
count = 0

for i in range(setting[2]):
    x, y = map(int, input().split())
    questX.append([x])
    questY.append([y])
    if count >1024:
        tX = np.copy(trainX)
        tY = np.copy(trainY)
        solve(tX,tY,questX,questY)
        questX.clear()
        questY.clear()

solve(trainX,trainY,questX,questY)
for item in answer:
    print(item)

Submission status: Runtime Error

Solution code:
import numpy as np
def solve(tX,tY,qX,qY):
    qX = np.array(qX)
    qY = np.array(qY)
    qX = tX - qX
    qY = qY - tY
    qX = qX>=0
    qY = qY>=0
    qY = qX * qY
    ans = np.sum(qY, axis=1)
    print(ans)
    answer.extend(ans.tolist())

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

trainX = []
trainY = []
questX = []
questY = []
answer = []
for i in range(setting[1]):
    x, y = map(int, input().split())
    trainX.append(x)
    trainY.append(y)

trainX = np.array(trainX)
trainY = np.array(trainY)
count = 0

for i in range(setting[2]):
    x, y = map(int, input().split())
    questX.append([x])
    questY.append([y])
    if count >1024:
        tX = np.copy(trainX)
        tY = np.copy(trainY)
        solve(tX,tY,questX,questY)
        questX.clear()
        questY.clear()

solve(trainX,trainY,questX,questY)
for item in answer:
    print(item)

Submission status: Runtime Error

Solution code:
city,dnum,qnum=map(int,input().split())

data,querry=[],[]
dapp=data.append()
qapp=querry.append()
for i in range(dnum):
	dapp(list(map(int,input().split())))

for i in range(qnum):
	qapp(list(map(int,input().split())))
	
def solve(start,end):
	res=0
	for j in range(dnum):
		if start<=data[j][0] and data[j][1]<=end:
			res+=1
	return res
	
for i in range(qnum):
	print(solve(querry[i][0],querry[i][1]))

Submission status: Runtime Error

Solution code:
import numpy as np
 
setting = list(map(int, input().split()))
 
trainX = []
trainY = []
questX = []
questY = []
for i in range(setting[1]):
    x, y = map(int, input().split())
    trainX.append(x)
    trainY.append(y)
 
for i in range(setting[2]):
    x, y = map(int, input().split())
    questX.append([x])
    questY.append([y])
 
trainX = np.array(trainX, dtype = 'int16')
trainY = np.array(trainY, dtype = 'int16')
questX = np.array(questX, dtype = 'int16')
questY = np.array(questY, dtype = 'int16')
 
questX = trainX - questX
questY = questY - trainY
 
questX = questX>=0
questY = questY>=0
 
questY = questX * questY
 
questY = questY==1
 
questY = np.sum(questY, axis=1)
answer = questY.tolist()
 
for item in answer:
    print(item)

Submission status: Runtime Error

Solution code:
import numpy as np
 
setting = list(map(int, input().split()))
 
trainX = []
trainY = []
questX = []
questY = []
for i in range(setting[1]):
    x, y = map(int, input().split())
    trainX.append(x)
    trainY.append(y)
 
for i in range(setting[2]):
    x, y = map(int, input().split())
    questX.append([x])
    questY.append([y])
 
trainX = np.array(trainX, dtype = 'int16')
trainY = np.array(trainY, dtype = 'int16')
questX = np.array(questX, dtype = 'int16')
questY = np.array(questY, dtype = 'int16')
 
stockX = trainX - questX
stockY = questY - trainY
 
questX = stockX>=0
questY = stockY>=0
 
stock = questX * questY
 
num = stock==1
 
ans = np.sum(num, axis=1)
answer = ans.tolist()
 
for item in answer:
    print(item)

Submission status: Runtime Error

Solution code:
import numpy as np

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

trainX = []
trainY = []
questX = []
questY = []
for i in range(setting[1]):
    x, y = map(int, input().split())
    trainX.append(x)
    trainY.append(y)

for i in range(setting[2]):
    x, y = map(int, input().split())
    questX.append([x])
    questY.append([y])

trainX = np.array(trainX)
trainY = np.array(trainY)
questX = np.array(questX)
questY = np.array(questY)

stockX = trainX - questX
stockY = questY - trainY

questX = stockX>=0
questY = stockY>=0

stock = questX * questY

num = stock==1

ans = np.sum(num, axis=1)
answer = ans.tolist()

for item in answer:
    print(item)

Submission status: Runtime Error

Solution code:
import numpy as np

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

trainX = []
trainY = []
questX = []
questY = []
for i in range(setting[1]):
    x, y = map(int, input().split())
    trainX.append(x)
    trainY.append(y)

for i in range(setting[2]):
    x, y = map(int, input().split())
    questX.append([x])
    questY.append([y])

trainX = np.array(trainX)
trainY = np.array(trainY)
questX = np.array(questX)
questY = np.array(questY)

questX = trainX - questX
questY = questY - trainY

questX = questX>=0
questY = questY>=0

questY = questX * questY

questY = questY==1

ans = np.sum(questY, axis=1)
ans = ans.tolist()

for item in ans:
    print(item)

Submission status: Runtime Error

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

LR = sorted(LR)

W = []
x = 0
for i in range(N):
    while x < M and LR[x][0] < i:
        x += 1
    W.append(x)

from itertools import accumulate

for p, q in PQ:
    xs = LR[W[p]:]
    ys = [0] * (N+1)
    for x in xs:
        ys[x[1]] += 1
    zs = list(accumulate(ys))
    print(zs[q])

Submission status: Runtime Error

Solution code:
N, M, Q = map( int, input().split())
NN = [ [0]*N for _ in range(N)]
for _ in range(M):
    L, R = map( int, input().split())
    NN[L-1][R-1] += 1

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

Submission status: Runtime Error

Solution code:
N, M, Q = map( int, input().split())
NN = [ [ 0 for _ in range(N)] for _ in range(N)]
for _ in range(M):
    L, R = map( int, input().split())
    NN[L-1][R-1] += 1

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

Submission status: Runtime Error

Solution code:
def memoize(f):
    table = {}

    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func


@memoize
def memo(a, b):
    if a == b:
        return e[a].count(a)
    elif b - a == 1:
        return memo(b, b) + memo(a, a) + e[a].count(b)
    else:
        return memo(a+1, b)+memo(a, b-1) + e[a].count(b) - memo(a+1, b-1)


n, m, q = map(int, input().split())
e = []
for i in range(n+1):
    e.append([])
for i in range(m):
    x, y = map(int, input().split())
    e[x].append(y)
for i in range(q):
    x, y = map(int, input().split())
    print(memo(x, y))

Submission status: Runtime Error

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


for (i,(p,q)) in enuq:
    removelist=[]
    for (j,(l,r)) in enumerate(rails):
        if p<=l and r<=q:
            ansli[i]=ansli[i]+1
        elif l<p:
            removelist.append(j)
    for jj in removelist:
        rails.pop(jj)



for a in ansli:
    print(a)

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
lines = sys.stdin.read().splitlines()
n, m, q = [int(item) for item in input().split(" ")]
# n, m, q = [int(item) for item in lines[0].split(" ")]

end = np.zeros((m,2),dtype=int)
query = np.zeros((q,2),dtype=int)
for i in range(m):
    end[i] = [int(item) for item in input().split(" ")]
#     end[i] = [int(item) for item in lines[1+i].split(" ")]

for i in range(q):
    query[i] = [int(item) for item in input().split(" ")]
#     query[i] = [int(item) for item in lines[1+m+i].split(" ")]

a = np.zeros((n,n), dtype=int)
np.add.at(a, [end[:,0]-1,end[:,1]-1], 1)
b = np.cumsum(a[::-1,:], axis=0)[::-1,:]
c = np.cumsum(b, axis=1)
for item in query:
    print(c[item[0]-1, item[1]-1])
    # print(np.sum(a[(item[0]-1):, :item[1]]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

mat = np.zeros((n, n), dtype=int)

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

ans = np.cumsum(mat, axis=1)[::-1], axis=0)[::-1]

for _ in range(q):
    l, r = map(int, input().split())
    print(ans[l-1][r-1])

Submission status: Runtime Error

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(m):
    for j in range(m):
        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: Runtime Error

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,b2] += 1
for i in range(Q):
    a,b = map(int,input().split())
    p[i] = a-1
    q[i] = b-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: Runtime Error

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]:
            elif j[1] <= i[1]:
                count += 1

    print(count)

Submission status: Runtime Error

Solution code:
import math, string, fractions, heapq, re, array, bisect, sys, random, time, copy
import itertools as it
import operator as op
import collections as cl
import functools as ft
import pandas as pd
import numpy as np

def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))
def LF(): return list(map(float, input().split()))
def LS(): return input().split()
def I(): return int(input())
def F(): return float(input())
def S(): return input()


if __name__ != "__main__":
    N, M, Q = LI()
    LR = np.ndarray((M, 3), dtype='uint32')

    for i in range(M):
        LR[i][0], LR[i][1] = LI()
        LR[i][2] = i

    L = pd.DataFrame(LR).sort_values(0)
    R = pd.DataFrame(LR).sort_values(1)

    for _ in range(Q):
        l = L.copy()


if __name__ != "__main__":
    N, M, Q = LI()
    LR = np.ndarray((M, 4), dtype='uint32')

    for i in range(M):
        LR[i][0], LR[i][1] = LI()

    LR = pd.DataFrame(LR)

    for _ in range(Q):
        p, q = LI()
        LR[2] = p <= LR[0]
        LR[3] = LR[1] <= q
        print(sum(LR[2]*LR[3]))


if __name__ == "__main__":
    N, M, Q = LI()
    LR = np.ndarray((4, M), dtype='uint32')

    for i in range(M):
        LR[0][i], LR[1][i] = LI()

    for _ in range(Q):
        p, q = LI()
        LR[2] = p <= LR[0]
        LR[3] = LR[1] <= q
        print(sum(LR[2]*LR[3]))

Submission status: Runtime Error

Solution code:
import numpy as np

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

mat = np.zeros((n, n), dtype=np.uint32)

for i in range(m):
    l, r = map(int, input().split())
    mat[l-1, r-1] += 1
mat = np.flipud(mat)
matmul = np.cumsum(mat, axis=0)
matmul = np.flipd[matmul]
matmul2 = np.cumsum(matmul, axis=1)

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

Submission status: Runtime Error

Solution code:
def spaceinput():
    return list(map(int,input().split(" ")))

def f(l,r):
    global a,nl,nr
    #print(l,r)
    #print(a[l][r])
    if a[l][r]>=0:
        return a[l][r]

    if nl[l-1]>0:
        tmp=f(l-1,r)-nl[l-1]
        a[l][r]=tmp
        return tmp

    if nr[r+1]>0:
        tmp=f(l,r+1)-nr[r+1]
        a[l][r]=tmp
        return tmp

    return f(l,r+1)



N,M,Q=spaceinput()

nr=[0]*(N+1)
nl=[0]*(N+1)

for i in range(M):
    s=spaceinput()
    nl[s[0]]+=1
    nr[s[1]]+=1

a=[[-1 for j in range(N+1)]for i in range(N+1)]
a[1][N]=M

for i in range(Q):
    s=spaceinput()
    #print(s)
    ssss=f(s[0],s[1])
    #print("ans")
    #print(type(ssss))
    print(ssss)






#print(a)

Submission status: Runtime Error

Solution code:
from operator import itemgetter

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

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

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

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

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

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

Submission status: Runtime Error

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

for i in range(M):
    a, b = map(int, input().split())
    train = make_range(a, b)
    if train in trains:
        trains[train] += 1
    else:
        trains[train] = 1
    
def combine_answer(answers, question, res):
    for other_question in answers:
        combine_question = other_question + question
        if other_question | question == combine_question:
            combine_res = answers[other_question] + res
            combine_answer(answers, combine_question, combine_res)
            answers[combine_question] = combine_res

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

for result in results:
    print(result)


# 000011 + 111100 = 111111

Submission status: Runtime Error

Solution code:
import numpy as np

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

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

ans_L = np.array
ans_R = np.array

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


for i in range(1,N+1):
    tmp_ans_L = np.zeros(M,dtype = int)
    tmp_ans_R = np.zeros(M,dtype = int)
    for j in range(M):
        if  i <= L[j]:
            tmp_ans_L[j] = 1
        if  R[i][j] <= i:
            tmp_ans_R[j] = 1
    if  i == 1:
        ans_L[i] = tmp_ans_L
        ans_R[i] = tmp_ans_R

ans = np.zeros(Q,dtype = int)

for i in range(Q):
    tmp = ans_L[p[i]+1] + ans_L[p[q]+1]
    ans[i] = tmp.index(2)

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

Submission status: Runtime Error

Solution code:
import math, string, fractions, heapq, re, array, bisect, sys, random, time, copy
import itertools as it
import operator as op
import collections as cl
import functools as ft
import pandas as pd
import numpy as np

def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))
def LF(): return list(map(float, input().split()))
def LS(): return input().split()
def I(): return int(input())
def F(): return float(input())
def S(): return input()


if __name__ != "__main__":
    N, M, Q = LI()
    LR = np.ndarray((M, 3), dtype='uint32')

    for i in range(M):
        LR[i][0], LR[i][1] = LI()
        LR[i][2] = i

    L = pd.DataFrame(LR).sort_values(0)
    R = pd.DataFrame(LR).sort_values(1)

    for _ in range(Q):
        l = L.copy()


if __name__ == "__main__":
    N, M, Q = LI()
    LR = np.ndarray((M, 3), dtype='uint32')

    for i in range(M):
        LR[i][0], LR[i][1] = LI()

    LR = pd.DataFrame(LR)

    for _ in range(Q):
        p, q = LI()
        LR[2] = p <= LR[0]
        LR[3] = LR[1] <= q
        print(sum(LR[2]*LR[3]))

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
M,N,Q=map(int,input().split())
LR=[]
pq=[]
ans=[]
count=0
for i in range(M):
    LR.append(list(map(int, input().split())))
for j in range(Q):
    pq.append(list(map(int, input().split())))
for k in range(Q):
    for l in range(M):
        if(LR[l][0]>=pq[k][0]) and (LR[l][1]<=pq[k][1]):
            count+=1
    ans.append(count)
    count=0
for m in ans:
    print(m)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class SegmentTree():
    # to par: (n-1) // 2
    # to chr: 2n+1, 2n+2
    def __init__(self, N):
        self.__N = 2**int(math.ceil(math.log(N, 2)))
        self.__table = [set([]) for _ in range(self.__N * 2 - 1)]

    def update(self, idx, x):
        i = self.__N - 1 + idx  # target leaf
        self.__table[i].add(x)
        while i != 0:
            pi = (i - 1) // 2  # parent
            self.__table[pi].add(x)
            # if self.__table[i] < self.__table[pi]:
            #     self.__table[pi] = self.__table[i]
            # else:
            #     break
            i = pi

    def __query(self, a, b, k, l, r):
        if r <= a or b <= l:
            return set([])
        if a <= l and r <= b:
            return self.__table[k]

        vl = self.__query(a, b, 2 * k + 1, l, (l + r) // 2)
        vr = self.__query(a, b, 2 * k + 2, (l + r) // 2, r)

        return vl | vr

    def query(self, a, b):
        return self.__query(a, b, 0, 0, self.__N)

    def print(self):
        print(self.__table)


@mt
def slv(N, M, Q, LR, PQ):

    st = SegmentTree(N)
    for i, (l, r) in enumerate(LR):
        st.update(l, ('s', i))
        st.update(r, ('e', i))

    for p, q in PQ:
        l = st.query(p, q+1)
        n = len(l)
        m = len(set(map(lambda x: x[1], l)))
        print(n-m)


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import bisect
import numpy

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

trains = numpy.array([[0, 0] for i in range(M)])
for i in range(M):
	trains[i][0], trains[i][1] = map(int, input().split())

for i in range(Q):
	p, q = map(int, input().split())
	trains_L = trains[:,0]
	L_index = bisect.bisect_left(trains_L, p)
	ans_L = numpy.array(sorted(trains[L_index:], key=lambda x: x[1]))
	trains_R = ans_L[:,1]
	R_index = bisect.bisect_right(trains_R, q)
	ans = ans_L[:R_index]
	print(len(ans))

Submission status: Runtime Error

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

for i in range(M):
    a, b = map(int, input().split())
    train = make_range(a, b)
    if train in trains:
        trains[train] += 1
    else:
        trains[train] = 1
    
def combine_answer(answers, question, res):
    for other_question in answers:
        combine_question = other_question + question
        if other_question | question == combine_question:
            combine_res = answers[other_question] + res
            answers[combine_question] = combine_res

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

for result in results:
    print(result)


# 000011 + 111100 = 111111