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:
# 79
# ABC106 D


def solve():
    N, M, Q = map(int, input().split())
    LR_L = tuple([int(x) for x in input().split()] for y in range(M))
    Q_L = tuple([int(x) for x in input().split()] for y in range(Q))

    imos_l = [[0] * (N+2) for _ in range(N+1)]

    for l, r in LR_L:
        imos_l[l][l] += 1
        imos_l[l][r+1] -= 1
    for i in range(1, N+1):
        for j in range(1, N+2):
            imos_l[i][j] += imos_l[i][j-1]

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


solve()

Submission status: Time Limit Exceeded

Solution code:
# 79
# ABC106 D

N, M, Q = map(int, input().split())
LR_L = tuple([int(x) for x in input().split()] for y in range(M))
Q_L = tuple([int(x) for x in input().split()] for y in range(Q))

imos_l = [[0] * (N+2) for _ in range(N+1)]

for l, r in LR_L:
    imos_l[l][l] += 1
    imos_l[l][r+1] -= 1
for i in range(1, N+1):
    for j in range(1, N+2):
        imos_l[i][j] += imos_l[i][j-1]

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import stdout

def getval():
    n,m,q = map(int,stdin.readline().split())
    rw = [[] for i in xrange(n)]
    for i in xrange(m):
        l,r = map(int,stdin.readline().split())
        rw[r-1].append(l-1)
    for i in xrange(n):
        rw[i].sort()
    return n,m,q,rw

def main(n,m,q,rw):

    def mybs(arr,key):
        lo = 0
        hi = len(arr)-1
        while lo<=hi:
            idx = (lo+hi)//2
            if arr[idx]<key:
                lo = idx + 1
            else:
                hi = idx - 1
        return lo

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    #print(rw)
    for i in [0]*q:
        key,r = map(int,stdin.readline().split())
        ans = 0
        key -= 1
        for j in xrange(key,r):
            ans += len(rw[j]) - mybs(rw[j],key)
        ans = "".join([str(ans),'\n'])
        stdout.write(ans)
    

if __name__=="__main__":
    n,m,q,rw = getval()
    main(n,m,q,rw)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import stdout

def getval():
    n,m,q = map(int,stdin.readline().split())
    rw = [[] for i in xrange(n)]
    for i in xrange(m):
        l,r = map(int,stdin.readline().split())
        rw[r-1].append(l-1)
    for i in xrange(n):
        rw[i].sort()
    return n,m,q,rw

def main(n,m,q,rw):

    def mybs(arr,key):
        lo = 0
        hi = len(arr)-1
        while lo<=hi:
            idx = (lo+hi)//2
            if arr[idx]<key:
                lo = idx + 1
            else:
                hi = idx - 1
        return lo

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    #print(rw)
    for i in xrange(q):
        key,r = map(int,stdin.readline().split())
        key -= 1
        ans = 0
        for j in xrange(key,r):
            temp = rw[j]
            ans += len(temp) - mybs(temp,key)
        ans = "".join([str(ans),'\n'])
        stdout.write(ans)
    

if __name__=="__main__":
    n,m,q,rw = getval()
    main(n,m,q,rw)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import stdout

def getval():
    n,m,q = map(int,stdin.readline().split())
    rw = [[] for i in xrange(n)]
    for i in xrange(m):
        l,r = map(int,stdin.readline().split())
        rw[r-1].append(l-1)
    for i in xrange(n):
        rw[i].sort()
    qu = [list(map(int,stdin.readline().split())) for i in xrange(q)]
    return n,m,q,rw,qu

def main(n,m,q,rw,qu):

    def mybs(arr,key):
        lo = 0
        hi = len(arr)-1
        while lo<=hi:
            idx = (lo+hi)//2
            if arr[idx]<key:
                lo = idx + 1
            else:
                hi = idx - 1
        return lo

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    #print(rw)
    for i in qu:
        ans = 0
        key = i[0]-1
        for j in xrange(key,i[1]):
            ans += len(rw[j]) - mybs(rw[j],key)
            #print(mybs(rw[j],key),i)
        ans = "".join([str(ans),'\n'])
        stdout.write(ans)
    

if __name__=="__main__":
    n,m,q,rw,qu = getval()
    main(n,m,q,rw,qu)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import stdout

def getval():
    n,m,q = map(int,stdin.readline().split())
    r = [list(map(int,stdin.readline().split())) for i in xrange(m)]
    qu = [list(map(int,stdin.readline().split())) for i in xrange(q)]
    return n,m,q,r,qu

def main(n,m,q,r,qu):
    #Keep all railways sorted by their right index
    rw = [[] for i in xrange(n)]
    for i in xrange(m):
        temp = r[i]
        rw[temp[1]-1].append(temp[0]-1)
    for i in xrange(n):
        rw[i].sort()

    def mybs(arr,key):
        lo = 0
        hi = len(arr)-1
        while lo<=hi:
            idx = (lo+hi)//2
            if arr[idx]<key:
                lo = idx + 1
            else:
                hi = idx - 1
        return lo

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    #print(rw)
    for i in qu:
        ans = 0
        key = i[0]-1
        for j in xrange(key,i[1]):
            ans += len(rw[j]) - mybs(rw[j],key)
            #print(mybs(rw[j],key),i)
        ans = "".join([str(ans),'\n'])
        stdout.write(ans)
    

if __name__=="__main__":
    n,m,q,r,qu = getval()
    main(n,m,q,r,qu)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import stdout

def getval():
    n,m,q = map(int,stdin.readline().split())
    r = [list(map(int,stdin.readline().split())) for i in xrange(m)]
    qu = [list(map(int,stdin.readline().split())) for i in xrange(q)]
    return n,m,q,r,qu

def main(n,m,q,r,qu):
    #Keep all railways sorted by their right index
    rw = [[] for i in xrange(n)]
    for i in r:
        rw[i[1]-1].append(i[0]-1)
    for i in rw:
      i.sort()

    def mybs(arr,key):
        lo = 0
        hi = len(arr)-1
        while lo<=hi:
            idx = (lo+hi)//2
            if arr[idx]<key:
                lo = idx + 1
            else:
                hi = idx - 1
        return lo

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    for i in qu:
        ans = 0
        key = i[0]-1
        for j in xrange(key,i[1]):
            ans += len(rw[j]) - mybs(rw[j],key)
        ans = "".join([str(ans),"\n"])
        stdout.write(str(ans))
    

if __name__=="__main__":
    n,m,q,r,qu = getval()
    main(n,m,q,r,qu)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import stdout

def getval():
    n,m,q = map(int,stdin.readline().split())
    r = [list(map(int,stdin.readline().split())) for i in range(m)]
    qu = [list(map(int,stdin.readline().split())) for i in range(q)]
    return n,m,q,r,qu

def main(n,m,q,r,qu):
    r.sort()
    #Keep all railways sorted by their right index
    rw = [[] for i in range(n)]
    for i in r:
        rw[i[1]-1].append(i[0]-1)

    def mybs(arr,key):
        lo = 0
        hi = len(arr)-1
        while lo<=hi:
            idx = (lo+hi)//2
            if arr[idx]<key:
                lo = idx + 1
            else:
                hi = idx - 1
        return lo

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    for i in qu:
        ans = 0
        key = i[0]-1
        for j in range(key,i[1]):
            ans += len(rw[j]) - mybs(rw[j],key)
        ans = "".join([str(ans),"\n"])
        stdout.write(str(ans))
    

if __name__=="__main__":
    n,m,q,r,qu = getval()
    main(n,m,q,r,qu)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from sys import stdout

def getval():
    n,m,q = map(int,stdin.readline().split())
    r = [list(map(int,stdin.readline().split())) for i in range(m)]
    qu = [list(map(int,stdin.readline().split())) for i in range(q)]
    return n,m,q,r,qu

def main(n,m,q,r,qu):
    #Keep all railways sorted by their right index
    rw = [[] for i in range(n)]
    for i in r:
        rw[i[1]-1].append(i[0]-1)
    for i in range(n):
        rw[i].sort()

    def mybs(arr,key):
        lo = 0
        hi = len(arr)-1
        while lo<=hi:
            idx = (lo+hi)//2
            if arr[idx]<key:
                lo = idx + 1
            else:
                hi = idx - 1
        return lo

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    #print(rw)
    for i in qu:
        ans = 0
        key = i[0]-1
        for j in range(key,i[1]):
            ans += len(rw[j]) - mybs(rw[j],key)
            #print(mybs(rw[j],key),i)
        ans = "".join([str(ans),'\n'])
        stdout.write(ans)
    

if __name__=="__main__":
    n,m,q,r,qu = getval()
    main(n,m,q,r,qu)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from bisect import bisect_left

def getval():
    n,m,q = map(int,stdin.readline().split())
    r = [list(map(int,stdin.readline().split())) for i in range(m)]
    qu = [list(map(int,stdin.readline().split())) for i in range(q)]
    return n,m,q,r,qu

def main(n,m,q,r,qu):
    #Keep all railways sorted by their right index
    rw = [[] for i in range(n)]
    for i in r:
        rw[i[1]-1].append(i[0]-1)
    for i in range(n):
        rw[i].sort()

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    #print(rw)
    for i in qu:
        ans = 0
        key = i[0]-1
        for j in range(key,i[1]):
            temp = rw[j]
            ans += len(temp) - bisect_left(temp,key)
            #print(mybs(rw[j],key),i)
        print(ans)
    

if __name__=="__main__":
    n,m,q,r,qu = getval()
    main(n,m,q,r,qu)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

def getval():
    n,m,q = map(int,stdin.readline().split())
    r = [list(map(int,stdin.readline().split())) for i in range(m)]
    qu = [list(map(int,stdin.readline().split())) for i in range(q)]
    return n,m,q,r,qu

def main(n,m,q,r,qu):
    #Keep all railways sorted by their right index
    rw = [[] for i in range(n)]
    for i in r:
        rw[i[1]-1].append(i[0]-1)
    for i in range(n):
        rw[i].sort()

    def mybs(arr,key):
        lo = 0
        hi = len(arr)-1
        while lo<=hi:
            idx = (lo+hi)//2
            if arr[idx]<key:
                lo = idx + 1
            else:
                hi = idx - 1
        return lo

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    #print(rw)
    for i in qu:
        ans = 0
        key = i[0]-1
        for j in range(key,i[1]):
            ans += len(rw[j]) - mybs(rw[j],key)
            #print(mybs(rw[j],key),i)
        print(ans)
    

if __name__=="__main__":
    n,m,q,r,qu = getval()
    main(n,m,q,r,qu)

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time, copy,bisect
#from operator import itemgetter
#from heapq import heappush, heappop
#import numpy as np
#from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson
#from scipy.sparse import csr_matrix
#from decimal import Decimal, ROUND_HALF_UP, ROUND_HALF_EVEN
sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

stdin = sys.stdin

ni = lambda: int(ns())
nf = lambda: float(ns())
na = lambda: list(map(int, stdin.readline().split()))
nb = lambda: list(map(float, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  # ignore trailing spaces

N, M, Q = na()
dp = [[0] * (N + 3) for _ in range(N + 3)]
for i in range(M):
    l, r = na()
    for x in range(1, l+1):
        for y in range(r, N+1):
            dp[x][y] += 1

for i in range(Q):
    p, q = na()
    print(dp[p][q])

Submission status: Time Limit Exceeded

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

a = [[0] * n for i in range(n)]
for l, r in lr:
    a[l - 1][r - 1] += 1

# cnt = [[0]*n for i in range(n)]
# for y in range(n):
#     v = 0
#     for x in range(y, -1, -1):
#         v += a[x][y]
#         cnt[x][y] = cnt[x][y - 1] + v

for _ in range(q):
    p, q = map(int, input().split())
    cnt = 0
    for l in range(p, q+1):
        for r in range(p, q+1):
            cnt += a[l-1][r-1]
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left

n,m,q=map(int,input().split()) #0-indexed
tree=[[] for i in range(n)]
lentree=[0]*n

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

for i in range(n):
  if tree[i]!=[]:
    tree[i].sort()


for i in range(n):
  lentree[i]+=len(tree[i])


for i in range(q):
  l,r=map(int,input().split())
  l-=1
  r-=1
  ans=0

  for j in range(l,r+1):
    xxx=tree[j]
    ans+=bisect_left(xxx,r+1)

  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
if __name__ == "__main__":
    N,M,Q = map(int,input().split())
    acc = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        l,r = map(int,input().split())
        acc[l][r] += 1
    pqs = [tuple(map(int,input().split())) for _ in range(Q)]
    for i in range(N):
        for j in range(1, N+1):
            acc[i][j] += acc[i][j-1]
    for p,q in pqs:
        ans = 0
        for i in range(p,q+1):
            ans += acc[i][q]-acc[i][p-1]
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
if __name__ == "__main__":
    N,M,Q = map(int,input().split())
    acc = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        l,r = map(int,input().split())
        acc[l][r] += 1
    pqs = []
    for _ in range(Q): 
        p,q = map(int,input().split())
        pqs.append((p,q))
    for i in range(N):
        for j in range(1, N+1):
            acc[i][j] += acc[i][j-1]
    for p,q in pqs:
        ans = 0
        for i in range(p,q+1):
            ans += acc[i][q]-acc[i][p-1]
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
if __name__ == "__main__":
    N,M,Q = map(int,input().split())
    acc = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        l,r = map(int,input().split())
        acc[l][r] += 1
    for i in range(N):
        for j in range(1, N+1):
            acc[i][j] += acc[i][j-1]
    for _ in range(Q):
        p,q = map(int,input().split())
        ans = 0
        for i in range(p,q+1):
            ans += acc[i][q]-acc[i][p-1]
        print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
acc = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l,r = map(int,input().split())
    acc[l][r] += 1
for i in range(N):
    for j in range(1, N+1):
        acc[i][j] += acc[i][j-1]
for _ in range(Q):
    p,q = map(int,input().split())
    ans = 0
    for i in range(p,q+1):
        ans += acc[i][q]-acc[i][p-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M,Q=map(int,input().split())
LR = []
for _ in range(M):
    LR.append(list(map(int,input().split())))
LR.sort()
L = [x for x,_ in LR]
R = [x for _,x in LR]

#事前に配列化 ans[i][j] i以降にスタート、j以前に完了の個数
ans = [[0]*510 for _ in range(510)]
for i in range(1,501):
    idx_L = bisect.bisect_left(L,i)
    arr=R[idx_L:]
    for ar in arr:
        ans[i][ar]+=1
    for j in range(1,501):
        ans[i][j]=ans[i][j-1]+ans[i][j]
    
for _ in range(Q):
    l,r = map(int,input().split())
    print(ans[l][r])

Submission status: Time Limit Exceeded

Solution code:
#開始がL以上のものかつR以下のものをにぶたんで抽出
#抽出した配列を終了でソートしてR以下のものを抽出
import bisect
N,M,Q=map(int,input().split())
LR = []
for _ in range(M):
    LR.append(list(map(int,input().split())))
LR.sort()
L = [x for x,_ in LR]
R = [x for _,x in LR]

for _ in range(Q):
    l,r = map(int,input().split())
    idx_L = bisect.bisect_left(L,l)
    idx_R = bisect.bisect_right(L,r)
    cnt =0
    for val in R[idx_L:idx_R+1]:
        if val<=r:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
#開始がL以上のものかつR以下のものをにぶたんで抽出
#抽出した配列を終了でソートしてR以下のものを抽出
import bisect
N,M,Q=map(int,input().split())
LR = []
for _ in range(M):
    LR.append(list(map(int,input().split())))
LR.sort()
L = [x for x,_ in LR]
R = [x for _,x in LR]

for _ in range(Q):
    l,r = map(int,input().split())
    idx_L = bisect.bisect_left(L,l)
    idx_R = bisect.bisect_right(L,r)
    tmp = R[idx_L:idx_R+1]
    tmp.sort()
    print(bisect.bisect_right(tmp,r))

Submission status: Time Limit Exceeded

Solution code:
from copy import copy
n_city, n_train, Q = map(int,input().split())
i_Redge = [0] * n_city
less_start_endls = [[] for _ in range(n_city)]
start_endls = [[] for _ in range(n_city)]
start_Nrange = [0] * n_city
section_ls = [[0,0] for _ in range(n_train)]
for i in range(n_train):
    L,R = map(int,input().split())
    i_Redge[R-1] += 1
    start_endls[L-1].append(R-1)

# less_start_endls[l]:=「lより左で始まる区間の右端のリスト」
now_ls = []
for l in range(n_city):
    less_start_endls[l] = copy(now_ls)
    for end in start_endls[l]:
        now_ls.append(end)

# まず、rをキーにして[0,r]内の電車の個数を返すリストを作成する
now = n_train
i_02r = [0] * n_city
for i in range(n_city-1,-1,-1):
    i_02r[i] = now
    now -= i_Redge[i]

# 街の各区間に対してその中にある路線数を求める
section_npath = {}
for r in range(n_city-1,-1,-1):
    for l in range(r+1):
        # [0,r]内の路線数
        n_zero2r = i_02r[r]
        # lより左を左端にもち、r以左を右端に持つ路線の数を求める
        to_subst = 0
        for end in less_start_endls[l]:
            if end <= r:
                to_subst += 1
        section_npath[(l,r)] = n_zero2r - to_subst

ans_ls = [0] * Q
for i in range(Q):
    l,r = map(int,input().split())
    ans_ls[i] = section_npath[(l-1,r-1)]

for ans in ans_ls:
    print(ans)

Submission status: Time Limit Exceeded

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

ab = [list(map(int, input().split())) for _ in range(m)]
abl = sorted(ab)
x = 501
dp =[]
import bisect
a = list(map(lambda x:x[0],abl))
b = list(map(lambda x:x[1],abl))

from collections import Counter
ca = Counter(a)
bil = []

for i in range(0,x):
    bil.append(ca[i])

import numpy
bill = numpy.cumsum(bil)

for i in range(1,x):
    bl = b[bill[i-1]:]
    cb = Counter(bl)
    bil = []    
    for j in range(1,x):
        bil.append(cb[j]) 
    bills = numpy.cumsum(bil)
    dp.append(bills)

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

Submission status: Time Limit Exceeded

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

ab = [list(map(int, input().split())) for _ in range(m)]
abl = sorted(ab)

import bisect
a = list(map(lambda x:x[0],abl))
b = list(map(lambda x:x[1],abl))
bil = []
for i in range(501):
    x = bisect.bisect(a,i)
    bil.append(x)

for i in range(q):
    l,r = map(int, input().split())
    x = bil[l-1]
    bl = sorted(b[x:])
    y = bisect.bisect(bl,r)
    print(y)

Submission status: Time Limit Exceeded

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

ab = [list(map(int, input().split())) for _ in range(m)]
abl = sorted(ab)

import bisect
a = list(map(lambda x:x[0],abl))
bil = []
for i in range(501):
    x = bisect.bisect(a,i)
    bil.append(x)

for i in range(q):
    l,r = map(int, input().split())
    x = bil[l-1]
    ablx = abl[x:]
    b = list(map(lambda x:x[1],ablx))
    bl = sorted(b)
    y = bisect.bisect(bl,r)
    print(y)

Submission status: Time Limit Exceeded

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

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

#ab = [[2, 9], [1, 6], [4, 5], [4, 7], [4, 7], [5, 8], [6, 6], [6, 7], [7, 9], [10, 10]]
abl = sorted(ab)

import bisect

for i in range(q):
    l,r = map(int, input().split())
    a = list(map(lambda x:x[0],abl))
    x = bisect.bisect(a,l-1)
    ablx = abl[x:]
    b = list(map(lambda x:x[1],ablx))
    bl = sorted(b)
    y = bisect.bisect(bl,r)
    print(y)

Submission status: Time Limit Exceeded

Solution code:
import sys
from itertools import accumulate

input = sys.stdin.readline


def main():
    N, M, Q = map(int, input().split())
    LR = [None] * M
    for i in range(M):
        LR[i] = tuple(map(int, input().split()))
    pq = [None] * Q
    for i in range(Q):
        pq[i] = tuple(map(int, input().split()))

    S = [[0] * (N + 1) for _ in range(N + 1)]
    for L, R in LR:
        S[L][R] += 1
    for i in range(N + 1):
        S[i] = list(accumulate(S[i]))

    ans = [0] * Q
    for i, (p, q) in enumerate(pq):
        for j in range(p, q + 1):
            ans[i] += S[j][q] - S[j][p - 1]

    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m, q = map(int, input().split())
    trains = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(m):
        l, r = map(int, input().split())
        trains[l][r] += 1
    for i in range(n + 1):
        for j in range(1, n + 1):
            trains[i][j] += trains[i][j - 1]
    for _ in range(q):
        p, q = map(int, input().split())
        ans = 0
        for i in range(p, q + 1):
            ans += trains[i][q] - trains[i][p - 1]
        print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m, q = map(int, input().split())
    trains = [list(map(int, input().split())) for _ in range(m)]
    for _ in range(q):
        p, q = map(int, input().split())
        print(len(list(filter(lambda x: p <= x[0] and x[1] <= q, trains))))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

cumsum = [[0 for _ in range(N + 1)]for _ in range(N + 1)]

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

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect
n,m,q=(int(i) for i in input().strip().split(" "))
from collections import defaultdict
d=defaultdict(list)
for _ in range(m):
    a,b=(int(i) for i in input().strip().split(" "))
    d[a].append(b)
for i in d.keys():
    d[i].sort()
for i in range(q):
    l,r=(int(i) for i in input().strip().split(" "))
    c=0
    for j in range(l,r+1):
        c+=bisect(d[j],r)
        c-=bisect(d[j],l-1)
    print(c)

Submission status: Time Limit Exceeded

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

lr=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    li,ri=map(int,input().split())
    lr[li][ri]+=1
    
for i in range(n+1):
    asum=0
    for j in range(n+1):
        asum+=lr[i][j]
        lr[i][j]=asum
            
for i in range(q):
    pi,qi=map(int,input().split())
#    pi-=1
#    qi-=1
    asum=0
    for j in range(pi,qi+1):
#        print("j:",j,"j-1",j-1,"qo:",qi,lr[j][qi]-lr[j][j-1])
        asum+=lr[j][qi]-lr[j][j-1]
    print(asum)

Submission status: Time Limit Exceeded

Solution code:
n , m , q = map(int, input().split())
table = [[0]*n for i in range(n)]

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

table_sum = table.copy()

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
trains = []
for _ in range(M):
    L, R = map(int, input().split())
    trains.append((L, R))

mem = []
for right in range(1, N+1):
    total_contains = set()
    total_overlaps = set()

    for i, (trainL, trainR) in enumerate(trains):
        if trainR <= right:
            total_contains.add(i)

        if trainL < right:
            total_overlaps.add(i)

    mem.append((total_contains, total_overlaps))

res = []
for _ in range(Q):
    QL, QR = map(int, input().split())
    res.append((mem[QR-1][0], mem[QL-1][1]))

for r in res:
    result = len(r[0]) - len(r[0]&r[1])
    print(result)

Submission status: Time Limit Exceeded

Solution code:
#TLE 5   AC 8  始点で辞書、bisect1回で数え上げる
# 初期入力
from bisect import bisect_right
from collections import defaultdict
import sys
input = sys.stdin.readline  #文字列では使わない
N,M,Q = map(int, input().split())
#LR =[[0]*(N) for i in range(N)]
LR_dic ={i:[] for i in range(1,N+1)}

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

for k in LR_dic.keys():
    LR_dic[k].sort()

#pq =[[0]*(N) for i in range(N)]
count =[]
for i in range(Q):
    cot =0
    p,q = map(int, input().split())
    for j in range(p,q+1):
        cot +=bisect_right(LR_dic[j],q)
    count.append(cot)
print(*count,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
from bisect import bisect_right
import sys
input = sys.stdin.readline  #文字列では使わない
N,M,Q = map(int, input().split())
LR =[[0]*(N) for i in range(N)]
LR_dic ={i:[] for i in range(1,N+1)}
for i in range(M):
    L,R = map(int, input().split())
    LR_dic[L].append(R)

for k in LR_dic.keys():
    LR_dic[k].sort()

#pq =[[0]*(N) for i in range(N)]
count =[]
for i in range(Q):
    cot =0
    p,q = map(int, input().split())
    for j in range(p,q+1):
        cot +=bisect_right(LR_dic[j],q)
    count.append(cot)
print(*count,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
# 初期入力
from bisect import bisect_right
import sys
input = sys.stdin.readline  #文字列では使わない
N,M,Q = map(int, input().split())
LR =[[0]*(N) for i in range(N)]
LR_dic ={i:[] for i in range(1,N+1)}
for i in range(M):
    L,R = map(int, input().split())
    LR_dic[L].append(R)

#pq =[[0]*(N) for i in range(N)]
count =[]
for i in range(Q):
    cot =0
    p,q = map(int, input().split())
    for j in range(p,q+1):
        LR_dic[j].sort()
        cot +=bisect_right(LR_dic[j],q)
    count.append(cot)
print(*count,sep="\n")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from itertools import accumulate

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

data = [[0]*500 for i in range(500)]
# data = [[0]*10 for i in range(10)]

for l, r in lr:
    data[l-1][r-1] += 1


for i in range(0, 500):
    data[i] = list(accumulate(data[i]))

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from itertools import accumulate

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

data = [[0]*500 for i in range(500)]
# data = [[0]*10 for i in range(10)]

for l, r in lr:
    data[l-1][r-1] += 1


for i in range(0, 500):
    data[i] = list(accumulate(data[i]))

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

Submission status: Time Limit Exceeded

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

answer = [0] * Q

for i in range(Q):
    p = pq[i][0]
    q = pq[i][1]
    for liri in LR:
        l = liri[0]
        r = liri[1]
        if p <= l and r <= q:
            answer[i] += 1

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def main():
    n,m,q=map(int,input().split())
    lst=np.zeros((n,n),dtype=int)

    for _ in range(m):
        s,t=map(int,input().split())
        lst[:s,t-1:]+=1
    
    for _ in range(q):
        s,t=map(int,input().split())
        print(lst[s-1][t-1])

main()