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:
l=list(map(int,input().split()))
n=l[0]
m=l[1]
q=l[2]
lr=[]
pq=[]
for i in range(m):
    lr.append(input())
for i in range(q):
    pq.append(input())
w=0    
for i in range(q):
    ppqq=list(map(int,pq[i].split()))
    w=0
    for j in range(m):
        llrr=list(map(int,lr[j].split()))
        if llrr[0]>= ppqq[0] and llrr[1]<=ppqq[1]:
            w+=1
    print(w)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

list1 = []
for i in range(M):
    L, R = map(int, input().split())
    list1.append([L, R])
    
list2 = []
for i in range(Q):
    p, q = map(int, input().split())
    list2.append([p, q])
    
mat = np.zeros((N+2,N+2))

for i in range(M):
    mat[list1[i][0],list1[i][1]] += 1

for i in range(Q):
    print(int(np.sum(mat[list2[i][0]:, :list2[i][1]+1])))

Submission status: Time Limit Exceeded

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>1023:
        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: Time Limit Exceeded

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>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: Time Limit Exceeded

Solution code:
import bisect
n,m,Q = map(int,input().split())

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

question = []
for i in range(Q):
    p,q = map(int,input().split())
    question.append([p,q])
    table.append([p,q,1])

table.sort(key = lambda x: (x[1],x[2]))
cum = [0 for i in range(n+1)]


answer = dict()
for i in range(m+Q):
    if table[i][2] == 0:
        cum[table[i][0]] += 1
    else:
        ans = 0
        for k in range(table[i][0],table[i][1]+1):
            ans += cum[k]
        num = table[i][0]*10 + table[i][1]
        answer[num] = ans

for i in range(Q):
    ind = question[i][0]*10 + question[i][1]
    print(answer[ind])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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

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

Ci = np.zeros((N+1,N+1),dtype=np.int32)
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# print(Ci)

for r in range(N+1):
    tmp = 0
    for l in range(N+1):
        tmp += Ci[l][r]
        Ci[l][r] = tmp

# print(Ci)

# pqi = []
ans = []
for i in range(Q):
    p, q = map(int, input().split())
    # pqi.append((p,q))
    tmp = Ci[q][q] - Ci[q][p-1]  - Ci[p-1][q] + Ci[p-1][p-1]
    ans.append(tmp)

# print(Ci)

for a in ans:
    print(a)
#
# for (p, q) in pqi:
#     tmp = 0
#     for l in range(p,q+1):
#         tmp += Ci[l][q] - Ci[l][p-1]
#
#     print(tmp)

Submission status: Time Limit Exceeded

Solution code:

from collections import Counter
from itertools import product

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

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
sumsumlist = [[0 for j in range(n+1)] for i in range(n+1)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i


for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])

for (i,j) in product(range(n),range(n)):
    sumsumlist[i+1][j+1] = sum([sumlist[l][j+1] for l in range(0,i+1)])



for (p,q) in qs:
    ans = sumsumlist[q][q]- sumsumlist[q][p-1] -sumsumlist[p-1][q] + sumsumlist[p-1][p-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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

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

Ci = np.zeros((N+1,N+1),dtype=np.int32)
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# pqi = []
ans = []
for i in range(Q):
    tmp = 0
    p, q = map(int, input().split())
    # pqi.append((p,q))
    for l in range(p,q+1):
        tmp += Ci[l][q] - Ci[l][p-1]
    ans.append(tmp)

for a in ans:
    print(a)
#
# for (p, q) in pqi:
#     tmp = 0
#     for l in range(p,q+1):
#         tmp += Ci[l][q] - Ci[l][p-1]
#
#     print(tmp)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
from itertools import product

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

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i

for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])


for (p,q) in qs:
    ans = 0
    for i in range(p-1,q):
        ans = ans+sumlist[i][q]-sumlist[i][p-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import numpy as np

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

# LRi = []
Xi = np.zeros((N+1,N+1),dtype=np.int32)
for i in range(M):
    L, R = map(int, input().split())
    # LRi.append((L,R))
    Xi[L][R] += 1

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

# for (L,R) in LRi:
#     Xi[L][R] += 1

# print(Xi)

Ci = np.zeros((N+1,N+1),dtype=np.int32)
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# print(Ci)

for (p, q) in pqi:
    tmp = 0
    for l in range(p,q+1):
        tmp += Ci[l][q] - Ci[l][p-1]

    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from operator import itemgetter
import numpy as np

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

LRi = []
for i in range(M):
    L, R = map(int, input().split())
    LRi.append((L,R))

#
# LRi.sort(key=itemgetter(1))
#
pqi = []
for i in range(Q):
    p, q = map(int, input().split())
    pqi.append((p,q))

Xi = np.zeros((N+1,N+1),dtype=np.int32)
for (L,R) in LRi:
    Xi[L][R] += 1

# print(Xi)

Ci = np.zeros((N+1,N+1),dtype=np.int32)
tmp = 0
for l in range(N+1):
    for r in range(N+1):
        tmp += Xi[l][r]
        Ci[l][r] = tmp

# print(Ci)

for (p, q) in pqi:
    tmp = 0
    for l in range(p,q+1):
        tmp += Ci[l][q] - Ci[l][p-1]

    print(tmp)

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

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

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

for row in res:
    print(row)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

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

sumlist = [[0 for j in range(n+1)] for i in range(n)]
for (l,r),i in Counter(rails).items():
    for j in range(r,n+1):
        sumlist[l-1][j] += i


for (p,q) in qs:
    ans = 0
    for i in range(p-1,q):
        ans = ans+sumlist[i][q]-sumlist[i][p-1]
    print(ans)

Submission status: Time Limit Exceeded

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

sumlist = [[0 for j in range(n+1)] for i in range(n)]
for (l,r) in rails:
    for i in range(r,n+1):
        sumlist[l-1][i] += 1

for (p,q) in qs:
    ans = 0
    for i in range(p-1,q):
        ans = ans+sumlist[i][q]-sumlist[i][p-1]
    print(ans)

Submission status: Time Limit Exceeded

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: Time Limit Exceeded

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

data,querry=[],[]

for i in range(dnum):
	data.append(list(map(int,input().split())))

for i in range(qnum):
	querry.append(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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""

n, m, qn = list(map(int, input().split()))

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

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
lrac = [[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    ac = 0
    for j in range(n+1):
        ac += lr[i][j]
        lrac[i][j] = ac

for _ in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = 0
    for i in range(pi, qi+1):
        ans += lrac[i][qi] - lrac[i][pi-1]
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""
import bisect
n, m, qn = list(map(int, input().split()))

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

for i in range(m):
    li, ri = list(map(int, input().split()))
    lr[li][ri] += 1
lrac = [[0]*(n+1) for _ in range(n+1)]
for i in range(n+1):
    ac = 0
    for j in range(n+1):
        ac += lr[i][j]
        lrac[i][j] = ac

for i in range(qn):
    pi, qi = list(map(int, input().split()))
    ans = 0
    for i in range(pi, qi+1):
        ans += lrac[i][qi] - lrac[i][pi-1]
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
L = []
R = []
ANS = []
for i in range(M) :
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
for j in range(Q) :
    p,q = map(int,input().split())
    ans = 0
    for k in range(len(L)) :
        if p <= L[k] :
            if R[k] <= q :
                ans += 1
    ANS.append(ans)
for z in range(len(ANS)) :
    print(ANS[z])

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Aug 18 21:50:39 2018
ABC106D
@author: maezawa
"""
import bisect
n, m, qn = list(map(int, input().split()))

lr = []

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

lr.sort(key=lambda x:(x[0],x[1]))
l = [z[0] for z in lr]

for i in range(qn):
    pi, qi = list(map(int, input().split()))
    idxl =  bisect.bisect_left(l, pi)
    lrtmp2 = [z[1] for z in lr[idxl:]]
    lrtmp2.sort()
    idxr = bisect.bisect_right(lrtmp2, qi)
    print(idxr)

Submission status: Time Limit Exceeded

Solution code:
a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])
ll = list()
rr = list()

for _ in range(m):
    a = input().split()
    ll.append(int(a[0]))
    rr.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]))

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

for i in range(m):
    c[ll[i] - 1][rr[i] - 1] += 1

for i in range(n):
    for j in range(1, n):
        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:
import numpy as np
n, m, q = list(map(int, input().split()))
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]
box = np.zeros(n*n)
box = box.reshape(n, n)

for i in lr:
  box[i[0]-1, i[1]-1] += 1

for j in pq:
  ans = np.sum(box[j[0]-1:j[1],j[0]-1:j[1]])
  print(int(ans))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n,m,q = LI()
    lr = [LI_() for _ in range(m)]
    pq = [LI_() for _ in range(q)]
    ls = [set() for _ in range(n)]
    rs = [set() for _ in range(n)]
    for i in range(m):
        l,r = lr[i]
        ls[l].add(i)
        rs[r].add(i)
    for i in range(n-2,-1,-1):
        ls[i] |= ls[i+1]
    for i in range(1,n):
        rs[i] |= rs[i-1]
    rr = []
    for p,q in pq:
        rr.append(len(ls[p] & rs[q]))

    return '\n'.join(map(str, rr))




print(main())

Submission status: Time Limit Exceeded

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

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

for _ in range(Q):
    p, q = map(int, input().split())
    c=0
    for i,j in list(itertools.combinations_with_replacement(range(p,q+1), 2)):
      c += d[i-1][j-1]
    print(c)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
import sys
sdin = sys.stdin.readline

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

lr = []
for i in range(m):
    l,r = map(int, sdin().split())
    lr.append(tuple([l-1, r-1]))
        
pq = []
for _ in range(q):
    p,q = map(int, sdin().split())
    pq.append(tuple([p-1, q-1]))


# n×nフィールドを用意して各列車のl,r点をプロット
field = [[0 for _ in range(n)] for _ in range(n)]
for l, r in lr:
    field[l][r] += 1
    
# fieldのx方向の累積和を取る
field_cum = [list(accumulate(field[i])) for i in range(n)]    

# 各クエリに対し、rがpからqの間に入っているものを足し合わせる
for p,q in pq:
    ans = 0
    for i in range(p,q+1):
        ans += field_cum[i][q]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
#かいせつ

import itertools

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

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

acc_lr = []
for l in lr:
    acc_lr.append([0] + list(itertools.accumulate(l)))

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

Submission status: Time Limit Exceeded

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

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

from itertools import accumulate

t = [list(accumulate(row)) for row in x]

for p, q in PQ:
    result = 0
    for i in range(p, q+1):
        result += t[i][q] - t[i][p-1]
    print(result)

Submission status: Time Limit Exceeded

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

A = [0] * (N * N)

for i in range(M):
    l, r = map(int, input().split())
    A = [a+1 if i%N < l and i//N >= (r-1) else a for i, a in enumerate(A)]

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]

N,M,Q = Is()
lis = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = Is()
    lis[l][r] += 1

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

for _ in range(Q): 
    p,q = Is()
    t = 0
    for i in range(p,q+1):
        t += cs[i][q] - cs[i][i-1]
    print(t)

Submission status: Time Limit Exceeded

Solution code:
import sys
from bisect import bisect_left

INDATA = sys.stdin.read().split('\n')
idx = -1
def input():
    global idx
    idx += 1
    return INDATA[idx]

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], x[1]))
L = list(map(lambda x: x[0], LR))
#print(LR)
 
C = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    l = bisect_left(L, i)
    r = bisect_left(L, i+1)-1
    R2 = list(map(lambda x: x[1], LR[l:r+1]))
    #print(l, r, R2)
    for j in range(i,n+1):
        C[i][j] = bisect_left(R2, j+1)
    #print(i, C[i])
 
for i in range(q):
    ans = 0
    for j in range(P[i], Q[i]+1):
        ans += C[j][Q[i]]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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], x[1]))
L = list(map(lambda x: x[0], LR))
#print(LR)
 
C = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    l = bisect_left(L, i)
    r = bisect_left(L, i+1)-1
    R2 = list(map(lambda x: x[1], LR[l:r+1]))
    #print(l, r, R2)
    for j in range(i,n+1):
        C[i][j] = bisect_left(R2, j+1)
    #print(i, C[i])
 
for i in range(q):
    ans = 0
    for j in range(P[i], Q[i]+1):
        ans += C[j][Q[i]]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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:
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())
    for j in range(1,l+1):
        for k in range(r,N+1):
            trains[j][k]+=1

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

Submission status: Time Limit Exceeded

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

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

for _ in range(m):
    l,r = map(int,input().split())
    for i in range(n+1):
        for j in range(n+1):
            if i<=l and j>=r:
                train[i][j] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
def Is(): return [int(x) for x in sys.stdin.readline().split()]

N,M,Q = Is()
lis = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r = Is()
    lis[l][r] += 1

cs = [[0]*(N+1) for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        cs[i][j] = cs[i][j-1] + sum(lis[i][:j+1])

for _ in range(Q): 
    p,q = Is()
    t = 0
    for i in range(p,q+1):
        t += cs[i][q] - cs[i][q-1]
    print(t)

Submission status: Time Limit Exceeded

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

train = []

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

for _ in range(q):
    p,q = map(int,input().split())
    ans = 0
    for l,r in train:
        if p<=l and q>=r:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().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 _ 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):
        x[i][j] += x[i][j - 1]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

inputs = raw_input().replace("\n", "")
N, M, Q = map(int, inputs.split(" "))

Ls = []
Rs = []
for i in xrange(M):
    inputs = raw_input().replace("\n", "")
    L, R = map(int, inputs.split(" "))
    Ls.append(L)
    Rs.append(R)

min_L = min(Ls)
max_L = max(Ls)
min_R = min(Rs)
max_R = max(Rs)

lr_counts = np.zeros((max_L-min_L+1, max_R-min_R+1))
for L, R in zip(Ls, Rs):
    lr_counts[L-min_L, R-min_R] += 1

q_inputs = []
for i in xrange(Q):
    q_input = raw_input().replace("\n", "")
    q_inputs.append(q_input)

relu = (lambda x: max(0, x))
for q_input in q_inputs:
    p, q = map(int, q_input.split(" "))
    print int(np.sum(lr_counts[relu(p-min_L):relu(q-min_L+1), relu(p-min_R):relu(q-min_R+1)]))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().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 _ 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] = sum(x[i][k] for k in range(1, j + 1))

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, m, q = map(int, input().split())
train_map = np.zeros((n, n))
for i in range(m):
    s, e = map(int, input().split())
    train_map[s-1, e-1] += 1
q_list = []
for i in range(q):
    q_list.append(list(map(int, input().split())))
for q_ in q_list:
    cnt = 0
    q_s, q_e = q_[0]-1, q_[1]
    print(int(np.sum(train_map[q_s:q_e, q_s:q_e])))

Submission status: Time Limit Exceeded

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


for i in range(Q):
    count=0
    for j in range(M):
        if que[i][0]<=tra[j][0] and que[i][1]>=tra[j][1]:
            count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n, m, q = map(int, input().split())
train_map = np.zeros((n, n))
for i in range(m):
    s, e = map(int, input().split())
    for j in range(s):
        for k in range(e-1, n):
            train_map[j, k] += 1
q_list = []
for i in range(q):
    q_list.append(list(map(int, input().split())))
for q_ in q_list:
    q_s, q_e = q_[0]-1, q_[1]-1
    print(max(int(train_map[q_s, q_e]), 0))

Submission status: Time Limit Exceeded

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))
rails.sort(key=lambda x:x[1])
 
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)
        if r>q:
            break
    for jj in sorted(removelist,reverse=True):
        rails.pop(jj)



for a in ansli:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])

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

for _ in range(m):
    a = input().split()
    x[int(a[0]) - 1][int(a[1]) - 1] += 1

c = list()

for i in range(n):
    c.append(list())
    for j in range(n):
        a = x[i][j]

        if 0 < j:
            a += c[i][j - 1]

        c[i].append(a)

for _ in range(qq):
    r = 0
    a = input().split()
    p = int(a[0])
    q = int(a[1])
    for j in range(p - 1, q):
        r += c[j][q - 1]
        if 1 < p:
            r -= c[j][p - 2]

    print(r)

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] * n for _ in range(n)]

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

c = list()

for i in range(n):
    c.append(list())
    for j in range(n):
        a = x[i][j]

        if 0 < j:
            a += c[i][j - 1]

        c[i].append(a)

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:
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 = list()

for i in range(n):
    c.append(list())
    for j in range(n):
        a = x[i][j]

        if 0 < j:
            a += c[i][j - 1]

        c[i].append(a)

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())
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 sorted(removelist,reverse=True):
        rails.pop(jj)



for a in ansli:
    print(a)

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
    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:
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),dtype = 'int8')
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(a[u-1][v-1])