Problem:


Score: 400 points

Problem Statement

In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east.
A company called AtCoder Express possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i).
Takahashi the king is interested in the following Q matters:

The number of the trains that runs strictly within the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.

Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Constraints

N is an integer between 1 and 500 (inclusive).

M is an integer between 1 and 200 \ 000 (inclusive).

Q is an integer between 1 and 100 \ 000 (inclusive).

1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)

1 \leq p_i \leq q_i \leq N (1 \leq i \leq Q)

Input

Input is given from Standard Input in the following format:

N M Q
L_1 R_1
L_2 R_2
:
L_M R_M
p_1 q_1
p_2 q_2
:
p_Q q_Q

Output

Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City p_i to City q_i.

Sample Input 1

2 3 1
1 1
1 2
2 2
1 2

Sample Output 1

3

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.

Sample Input 2

10 3 2
1 5
2 8
7 10
1 7
3 10

Sample Output 2

1
1

The first query is on the section from City 1 to 7. There is only one train that runs strictly within that section: Train 1.
The second query is on the section from City 3 to 10. There is only one train that runs strictly within that section: Train 3.

Sample Input 3

10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10

Sample Output 3

7
9
10
6
8
9
6
7
8
10



Sample input:
2 3 1
1 1
1 2
2 2
1 2


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m,q=map(int,input().split())
s=[[] for i in range(n+1)]
t=[]
ss=[]
for i in range(m):
    x,y=map(int,input().split())
    s[x]+=[y]

for i in range(q):
    x,y=map(int,input().split())
    ss=s[x:]
    ww=[]
    for j in range(n-x+1):
        ww+=ss[j]
    ww=np.array(ww)
    print(len(ww[ww<=y]))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map( int, input().split())
NN = [ [ 0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L, R = map( int, input().split())
    NN[L][R] += 1
Sum = [ [ 0 ] for _ in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        Sum[i].append(Sum[i][-1]+NN[i][j])
for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p,q+1):
        ans += Sum[i][q] - Sum[i][p-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m,q = map(int,input().split())
lr = []
for i in range(m):
    l = list(map(int,input().split()))	
    lr.append(l)
 
ass = np.zeros((n,n))
ans = np.zeros((n,n))   
        
for i in range(m):
    ass[lr[i][0]-1][lr[i][1]-1] += 1
        
#print(ass)

for i in range(n):
    for j in range(n):
        if i == 0:
            ans[n-1][j] = sum(ass[n-1][:j+1:])
        else:
            ans[n-1-i][j] = sum(ass[n-1-i][:j+1:]) + ans[n-i][j]
#print(ass)
#print(ans)

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

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, raw_input().split())
L = []
R = []
for i in range(M):
	_l, _r = map(int, raw_input().split())
	L.append(_l)
	R.append(_r)

p = []
q = []
for i in range(Q):
	_p, _q = map(int, raw_input().split())
	p.append(_p)
	q.append(_q)


start_end_mat = [[0] * (N + 1) for i in range(N + 1)]

for i in range(M):
	start = L[i]
	end = R[i]
	for j in range(start, -1, -1):
		for k in range(end, N + 1):
			start_end_mat[j][k] += 1


for i in range(Q):
	start = p[i]
	end = q[i]
	print(start_end_mat[start][end])

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
lr = tuple(tuple(map(int, input().split())) for _ in range(m))
pq = tuple(tuple(map(int, input().split())) for _ in range(q))

lr = sorted(lr, key=lambda x: x[1] - x[0])

for i in range(q):
    p, q = pq[i]
    c = 0
    for j in range(m):
        l, r = lr[j]
        if r - l > q - p:
            break
        if p <= l and r <= q:
            c += 1
    print(c)

Submission status: Time Limit Exceeded

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

# sortしておく
# for i in range(1, N+1):
#    LR[i].sort()

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

for i in range(Q):
    re = 0
    p, q = PQ[i][0] , PQ[i][1]
#    print(i, p, q)
    for j in range(p,q + 1):
        if len(LR[j]) > 0: 
            re += sum(x <= q for x in LR[j]) #binarySearch(LR[j], q) + 1
    print(re)

Submission status: Time Limit Exceeded

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)
for item in query:
    print(np.sum(a[(item[0]-1):, :item[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())])

    for (p,q),k in PQi:
        r = 0
        for i in range(p,q+1):
            c = TABLE[i-1]
            for dst,num in c:
                if dst<=q:
                    r+=num
                else:
                    break
        print(r)




    # 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())

C = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(M):
	L,R = map(int,input().split())
	C[L][R] += 1


D = [[0 for i in range(N+4)] for j in range(N+4)]
for i in range(N+1):
	for j in range(N+1):
		D[i][j+1] = D[i][j] + C[i][j]

buf = []
for j in range(Q):
	p,q = map(int,input().split())
	s = 0
	for i in range(p,q+1):
		s += (D[i][q+1] - D[i][i])
	buf.append(s)
print("\n".join(map(str,buf)))

Submission status: Time Limit Exceeded

Solution code:
import sys

ns = lambda: sys.stdin.readline().rstrip()
ni = lambda: int(ns())
na = lambda: [int(x) for x in ns().split()]
nall = lambda: [int(x) for x in sys.stdin.readlines()]


def main():
    n, m, q = na()
    lrs = [na() for _ in range(m)]
    pqs = [na() for _ in range(q)]

    map = {}
    for l, r in lrs:
        x = r - l
        if l in map:
            if x in map[l]:
                map[l][x] += 1
            else:
                map[l][x] = 1
        else:
            map[l] = {}
            map[l][x] = 1

    for p, q in pqs:
        cnt = 0
        for l in range(p, q+1):
            if l in map:
                for x in range(q-l+1):
                    if x in map[l]:
                        cnt += map[l][x]

        print(cnt)
                

main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np
N, M, Q = map(int, input().split())
trains = np.array([list(map(int, input().split())) for i in range(M)])
queries =np.array([list(map(int, input().split())) for i in range(Q)])

A  =np.zeros([N, N])#A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1, ri - 1] += 1
dp = np.zeros([N, N])

def ans(left, right):
    if dp[left, right] > 0:
        return dp[left, right]
    elif left > right:
        return 0
    elif left == right:
        dp[left, right] = A[left, right]
        return dp[left, right]
    else:
        dp[left, right] = ans(left, right-1) + ans(left + 1, right) + A[left, right] - ans(left + 1, right - 1)
        return dp[left, right]

for q in range(Q):
    pi, qi = queries[q]
    print(int(ans(pi - 1, qi - 1)))

Submission status: Time Limit Exceeded

Solution code:
n, m, q = list(map(int, input().split()))
import numpy as np
line_list = []
for i in range(m):
  line_list.append(list(map(int, input().split())))
line_arr = np.array(line_list)
for i in range(q):
  s1, s2 = input().split()
  flg1=line_arr[:, 0] >= int(s1)
  flg2=line_arr[:, 1] <= int(s2)
  print(np.sum(flg1 & flg2))

Submission status: Time Limit Exceeded

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

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

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

# sortしておく
for i in range(1, N+1):
    LR[i].sort()

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

for i in range(Q):
    re = 0
    p, q = PQ[i][0] , PQ[i][1]
#    print(i, p, q)
    for j in range(p,q + 1):
        if len(LR[j]) > 0: 
            re += sum(x <= q for x in LR[j]) #binarySearch(LR[j], q) + 1
    print(re)

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

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

A = []
B = []

for i in range(M):
  A.append(map(int, raw_input().split()))
  
for i in range(Q):
  B.append(map(int, raw_input().split()))
  
  
for i in range(Q):
  b = sorted(A, key=itemgetter(0))
  c = sorted(b, key=itemgetter(1), reverse=True)
  
  k = 0
  for j in range(M):
    if c[j][0] >= B[i][0] and c[j][1]<=B[i][1]:
      k=k+1
   
  print k

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split(" "))
lr = [tuple(map(int, input().split(" "))) for _ in range(m)]
pq = [tuple(map(int, input().split(" "))) for _ in range(q)]

for pq_i in pq:
    count = 0
    p_i, q_i = pq_i
    for lr_i in lr:
        l_i, r_i = lr_i
        if p_i <= l_i and r_i <= q_i:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

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

LRs = []

for i in range(M):
	l,r = input().split()
	l = int(l)
	r = int(r)

	LRs.append((l,r))


pqs = []
qs = []
cnts = []
for j in range(Q):
	cnt = 0

	p,q = input().split()
	p = int(p)
	q = int(q)

	pqs.append((p,q))

	for k in range(len(LRs)):
		if(p<=LRs[k][0] and LRs[k][1]<=q):
			cnt += 1

	cnts.append(cnt)

for n in range(len(cnts)):
	print(cnts[n])

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))
 
b = [[] for i in range(a[0])]
 
c = [0 for i in range(a[2])]
 
co = 0
for i in range(a[1]):
    n,m = map(int,input().split())
 
    b[m-1].append(n)
  
for i in range(len(b)):
    b[i].sort()
    
for i in range(a[2]):
    n,m = map(int,input().split())
    for j in range(n-1,m):
        for k in range(len(b[j])):
            if b[j][k] >= n:
                co += 1
    print(co)
    co = 0

Submission status: Time Limit Exceeded

Solution code:
NMQ = list(map(int,input().split()))
N=NMQ[0]
M=NMQ[1]
Q=NMQ[2]
reg=[]
for i in range(M):
	r=list(map(int,input().split()))
	reg.append(r)
que=[]
for i in range(Q):
	q=list(map(int,input().split()))
	que.append(q)
hyo=[[0 for i in range(N)] for j in range(N)]
for i in range(M):
	Li=reg[i][0]
	Ri=reg[i][1]
	for k in range(Li):
		for l in range(N-Ri+1):
			hyo[k][N-l-1]=hyo[k][N-l-1]+1
for i in range(Q):
	pi=que[i][0]
	qi=que[i][1]
	print(hyo[pi-1][qi-1])

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

    print(count)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

from operator import itemgetter

def main():
    n, m, qs = map(int, input().split())

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

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

    lr_list = sorted(lr_list, key=itemgetter(0))

    lr_index_start = 0
    index_memo = [0] * n
    for p, q in pq_list:
        count = 0
        left_matched = False
        lr_index_start = 0
        i = p - 1
        while i >= 0 and lr_index_start == 0:
            lr_index_start = index_memo[i]
            i = i - 1

        for i in range(lr_index_start, m):
            l, r = lr_list[i]
            if p <= l and r <= q:
                count = count + 1
            if p <= l and not left_matched:
                left_matched = True
                index_memo[p - 1] = i
        print(count)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

for route in routes:
    ans = 0
    p = route[0]
    q = route[1]
    for train in trains:
        l = train[0]
        r = train[1]
        if (p <= l and r <= q):
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, k = list(map(int, input().split()))
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(k)]

for i in range(k):
    cnt = 0
    for j in range(m):
        if lr[j][0] >= pq[i][0] and lr[j][1] <= pq[i][1]:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, m, Q = map(int, input().split())
lr = sorted([list(map(int, input().split())) for _ in range(m)])
pq = [list(map(int, input().split())) for _ in range(Q)]
a = [k[0] for k in lr]
for i in pq:
  p = i[0]
  q = i[1]
  ans = 0
  b = a[:]
  b.append(p)
  b = sorted(b)
  for j in lr[b.index(p):]:
    l = j[0]
    r = j[1]
    if p <= l and r <= q:
      ans += 1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
a = list(map(int,input().split()))

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

c = [0 for i in range(a[2])]

co = 0
for i in range(a[1]):
    n,m = map(int,input().split())

    b[m-1].append(n)
    
for i in range(a[2]):
    n,m = map(int,input().split())
    for j in range(n-1,m):
        for k in range(len(b[j])):
            if b[j][k] >= n:
                co += 1
    print(co)
    co = 0

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

    cities_l = [[] for i in range(n+1)]
    cities_r = [[] for i in range(n+1)]
    cities_qp = [[] for i in range(n+1)]
    cities_qq = [[] for i in range(n+1)]

    table = {(i, j): 0 for i in range(n+1) for j in range(n+1)}

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        for j in range(0, l+1):
            for k in range(r, n+1):
                table[(j, k)] += 1
        #cities_l[l].append(i)
        #cities_r[r].append(i)

    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        print(table[(qp, qq)])
        #cities_qp[qp].append(i)
        #cities_qq[qq].append(i)

    #z = set()
    #ans = [[[], []] for i in range(q)]
    #for i in range(1,n+1):
    #    z |= set(cities_qp[i])
    #    for j in z:
    #        ans[j][0] += cities_l[i]
    #       ans[j][1] += cities_r[i]
    #    z -= set(cities_qq[i])

    #for i in range(q):
    #    print(len(set(ans[i][0]) & set(ans[i][1])))

if __name__=='__main__':
    main()

Submission status: Time Limit Exceeded

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 = mat[::-1]
matmul = np.cumsum(mat, axis=0)
matmul = matmul[::-1]
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: Time Limit Exceeded

Solution code:
def run(n, m, qq, l, r, p, q):
    cnt = []
    # lでソート済みと仮定
    # lr = []
    # for i in range(m):
    #     lr.append([l[i], r[i]])
    # print(lr)
    # sort_l = sorted(lr, key=lambda x: -x[1][0])
    # print(sort_l)
    dic = {}
    for i in range(qq):
        tmp_cnt = 0
        if (p[i], q[i]) in dic:
            cnt.append(dic[(p[i], q[i])])
        else:
            for j in range(m):
                if p[i] <= l[j] and r[j] <= q[i]:
                    tmp_cnt += 1
            cnt.append(tmp_cnt)
            dic[(p[i], q[i])] = tmp_cnt
    return cnt


def search_li(l, p):
    left = 0
    right = len(l) - 1

    while left <= right:
        mid = (left + right) // 2
        if l[mid] >= p:
            left = mid
            result = mid
        else:
            right = mid - 1
        return result


def read_line():
    n, m, qq = map(int, input().split())
    l = []
    r = []
    for i in range(m):
        tl, tr = map(int, input().split())
        l.append(tl)
        r.append(tr)
    p = []
    q = []
    for i in range(qq):
        tp, tq = map(int, input().split())
        p.append(tp)
        q.append(tq)
    return (n, m, qq, l, r, p, q)


def main():
    n, m, qq, l, r, p, q = read_line()
    ret = run(n, m, qq, l, r, p, q)
    for i in range(len(ret)):
        print(ret[i])


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

A=[]
for i in range(m):
    b,c=map(int,input().split())
    A.append([b,c])
B=[]
for i in range(q):
    b,c=map(int,input().split())
    B.append([b,c,i])

C=[[0 for i in range(n+3)] for j in range(n+3)]
#print(C)
for i in range(m):
    C[A[i][0]][A[i][1]]+=1


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

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

D=[]

E=[[[0 for i in range(n+3)] for j in range(n+3)] for k in range(n+3)]
for l in range(n+2):
    for mrp1 in range(l,n+2):
        for rp1 in range(mrp1,n+2):

            for j in range(mrp1,rp1):
                for k in range(l,rp1):
                    E[l][mrp1][rp1]+=C[k][j]

co=0
ml=0
mr=0
for i in range(q):
    l=B[i][0]
    r=B[i][1]
    nu=B[i][2]
    if ml<l :
        co=0
        for j in range(l,r+1):
            for k in range(j,r+1):
                co+=C[j][k]
        D.append([co,nu])
    else:
        #for j in range(mr+1,r+1):
        #    for k in range(l,r+1):
        #        co+=C[k][j]
        co+=E[l][mr+1][r+1]
        D.append([co,nu])
    ml=l
    mr=r

D.sort(key=lambda x:x[1])
for i in range(q):
    print(D[i][0])

Submission status: Time Limit Exceeded

Solution code:
import bisect
import numpy as np
N,M,Q = map(int,input().split())
lr = [0]*M
for i in range(M):
    l,r = map(int,input().split())
    lr[i] = [l,r]
lr = sorted(lr,key=lambda x:x[0])
lr_t = list(np.array(lr).transpose())
index_dict={}
r_dict={} 
d = {}
for i in range(N):
    index_dict[i+1]=bisect.bisect_left(lr_t[0],i+1)
    r_dict[i+1]=sorted(lr_t[1][index_dict[i+1]:])
for i in range(Q):
    p,q = map(int,input().split())
    if p not in d:
        d[p]={}
        I = index_dict[p]
        r = r_dict[p]
        I = bisect.bisect(r,q)
        print(I)
        d[p][q]=I
    else:
        if q not in d[p]:
            I = index_dict[p]
            r = r_dict[p]
            I = bisect.bisect(r,q)
            print(I)
            d[p][q]=I
        else:
            print(d[p][q])

Submission status: Time Limit Exceeded

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


def main():
    n, m, q = (int(v) for v in input().strip().split())

    trains = []
    for _ in range(m):
        l, r = (int(v) for v in input().strip().split())
        trains.append((l, r))

    questions = []
    for _ in range(q):
        p, q = (int(v) for v in input().strip().split())
        questions.append((p, q))

    for question in questions:
        p, q = question

        count = 0
        for train in trains:
            l, r = train

            if p <= l and r <= q:
                count += 1
        print(count)


main()

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

dp = [[0]*(N+1) for _ in range(N+1)]
dp2 = [[0]*(N+1) for _ in range(N+1)]
for _ in range(Q): 
    p,q = Is()
    if dp2[p][q]:
        print(dp2[p][q])
        continue
    t = 0
    for i in range(p,q+1):
        if dp[i][q]:
            t += dp[i][q]
        else:
            dp[i][q] = sum(lis[i][i:q+1])
            t += dp[i][q]
    dp2[p][q] = t
    print(t)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int,input().split())
m =  [[0 for y in range(N+1)] for x in range(N+1)]
m2 =  [[0 for y in range(N+1)] for x in range(N+1)]

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

for i in range(1,N+1):
    s=m[i][i]
    m2[i][i]=s
    for j in range(i+1,N+1):
        for k in range(i,j+1):
            s+=m[k][j]
        m2[i][j]=s


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

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
Mi = [list(map(int, input().split())) for i in range(M)]
Qi = [list(map(int, input().split())) for i in range(Q)]
qi = [Qi[i].extend([0, i]) for i in range(Q)]
Mi.sort()
Qi.sort()

for mi in Mi:
    for i in range(Q):
        if mi[0] < Qi[i][0]:
            continue
        if mi[0] >= Qi[i][0] and mi[1] <= Qi[i][1]:
            Qi[i][2] += 1
Qi.sort(key=lambda x: x[3])
for a in Qi:
    print(a[2])

Submission status: Time Limit Exceeded

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

from collections import defaultdict
import bisect


def solve():
    n, m, q = map(int, input().split())
    d = defaultdict(list)
    for i in range(m):
        l, r = map(int, input().split())
        bisect.insort_left(d[l], r)
    table = [[0 for i in range(n + 1)] for j in range(n + 1)]
    dk = [p for p in d.keys()]
    dk.sort()
    for i in range(1, n + 1):
        ri = bisect.bisect_left(dk, i)
        dk = dk[ri:]
        if not dk:
            break
        for j in range(i, n + 1):
            tans = 0
            for k in [p for p in dk if p <= j]:
                tans += bisect.bisect_right(d[k], j)
            table[i][j] = tans
    for i in range(q):
        l, r = map(int, input().split())
        print(table[l][r])


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]

A  =[[0] * N for _ in range(N)] #A[i][j] = (i + 1) -> (j+1)なる列車の本数
for train in trains:
    li, ri = train
    A[li - 1][ri - 1] += 1
dp = [[0] * N for __ in range(N)]

def ans(left, right):
    if dp[left][right] > 0:
        return dp[left][right]
    elif left > right:
        return 0
    elif left == right:
        dp[left][right] = A[left][right]
        return A[left][right]
    else:
        x = ans(left, right-1) + ans(left + 1, right) + A[left][right] - ans(left + 1, right - 1)
        dp[left][right] = x
        return x

for q in range(Q):
    pi, qi = queries[q]
    print(ans(pi - 1, qi - 1))

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

l= []
r = []
lr = []
p = []
q = []

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

lr.sort(key=lambda x:x[0])
l.sort()

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)