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 bisect
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M,Q=mi()
    Ls = []
    Rs = []
    for i in range(M):
        L,R=mi()
        Ls.append((L,i))
        Rs.append((R,i))

    Ls.sort()
    Rs.sort()

    L_indexs = [set()] * (M+1)
    R_indexs = [set()] * (M+1)

    _Ls = []
    _Rs = []
    for i in range(M):
        L,L_i = Ls[M-1-i]
        R,R_i = Rs[i]

        L_indexs[i+1] = L_indexs[i] | set([L_i])
        R_indexs[i+1] = R_indexs[i] | set([R_i])

        _Ls.append(Ls[i][0])
        _Rs.append(R)

        
        
    # print(L_indexs)
    # print(L_indexs,R_indexs)
    for i in range(Q):
        p,q=mi()
        L_i = bisect.bisect_left(_Ls,p)

        # print(L_i)
        
        R_i = bisect.bisect_right(_Rs,q)
        if R_i == M:
            R_i -= 1
        elif Rs[R_i][0] != q:
            R_i -= 1

        ans = 0
        # print(M-L_i,R_i, L_indexs[M-L_i],R_indexs[R_i+1])
        if R_indexs[R_i+1] > L_indexs[M-L_i]:
            for j in L_indexs[M-L_i]:
                if j in R_indexs[R_i+1]:
                    ans += 1
        else:
            for j in R_indexs[R_i+1]:
                if j in L_indexs[M-L_i]:
                    ans += 1
        
        print(ans)



if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys
sys.setrecursionlimit(10**9)

def mi(): return map(int,input().split())
def ii(): return int(input())
def isp(): return input().split()
def deb(text): print("-------\n{}\n-------".format(text))

INF=10**20
def main():
    N,M,Q=mi()
    Ls = []
    Rs = []
    for i in range(M):
        L,R=mi()
        Ls.append((L,i))
        Rs.append((R,i))

    Ls.sort()
    Rs.sort()

    L_indexs = [set()] * (M+1)
    R_indexs = [set()] * (M+1)

    _Ls = []
    _Rs = []
    for i in range(M):
        L,L_i = Ls[i]
        R,R_i = Rs[i]

        L_indexs[i+1] = L_indexs[i] | set([L_i])
        R_indexs[i+1] = R_indexs[i] | set([R_i])

        _Ls.append(L)
        _Rs.append(R)

        
        

    # print(L_indexs,R_indexs)
    for i in range(Q):
        p,q=mi()
        L_i = bisect.bisect_left(_Ls,p)

        # print(L_i)
        
        R_i = bisect.bisect_right(_Rs,q)
        if R_i == M:
            R_i -= 1
        elif Rs[R_i][0] != q:
            R_i -= 1

        ans = 0
        # print(L_i,R_i,L_indexs[-1] - L_indexs[L_i],R_indexs[R_i+1])
        for j in R_indexs[R_i+1]:
            if j in L_indexs[-1] - L_indexs[L_i]:
                ans += 1
        
        print(ans)



        




if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect

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

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

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

for i in range(N+1):
  G[i].sort()

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    N,M,Q = map(int, input().split())
    l_sets_plain = [set() for i in range(N)]
    r_sets_plain = [set() for i in range(N)]

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

    l_sets = l_sets_plain.copy()
    r_sets = r_sets_plain.copy()

    tmp_l = set()
    tmp_r = set()
    for i in range(N):
        tmp_l = tmp_l | l_sets[i]
        tmp_r = tmp_r | r_sets[i]
        l_sets[i] = tmp_l.copy()
        r_sets[i] = tmp_r.copy()

    for _ in range(Q):
        p,q = map(int, input().split())
        tmp = r_sets[q-1] & l_sets_plain[p-1]
        print(len((r_sets[q-1] - l_sets[p-1]) | tmp))

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int, input().split())
l_sets_plain = [set() for i in range(N)]
r_sets_plain = [set() for i in range(N)]

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

l_sets = l_sets_plain.copy()
r_sets = r_sets_plain.copy()

tmp_l = set()
tmp_r = set()
for i in range(N):
    tmp_l = tmp_l | l_sets[i]
    tmp_r = tmp_r | r_sets[i]
    l_sets[i] = tmp_l.copy()
    r_sets[i] = tmp_r.copy()

for _ in range(Q):
    p,q = map(int, input().split())
    tmp = r_sets[q-1] & l_sets_plain[p-1]
    print(len((r_sets[q-1] - l_sets[p-1]) | tmp))

Submission status: Time Limit Exceeded

Solution code:
N, M , Q = map(int, input().split())
import numpy as np
Rui = [[0]*N]*N
Rui = np.array(Rui)

for i in range (0, M):
	A, B = map(int, input().split())
	for j in range (0,A):
		for k in range (B-1, N):
			Rui[j][k]+=1

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

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int,input().split())
lst = [list(map(int,input().split())) for _ in range(m)]
query = [list(map(int,input().split())) for _ in range(q)]
s = [[0]*(n+1) for _ in range(n+1)]

for i in range(m):
    l,r = lst[i]
    s[l][r] += 1

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

for i in range(q):
    l,r = query[i]
    ans = 0
    for j in range(l,r+1):
        ans += s[j][r] - s[j][l-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, M, Q = MAP()
LR = [LIST() for _ in range(M)]
pq = [LIST() for _ in range(Q)]

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

for L, R in LR:
	x[L][R] += 1

for l in range(N+1):
	x[l] = list(accumulate(x[l]))
		
for p, q in pq:
	ans = 0
	for i in range(p, q+1):
		ans += x[i][q] - x[i][p-1]
	print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M, Q = map(int, input().split())
mark = np.zeros((N+2, N+2), dtype=int)

for _ in range(M):
    a, b = map(int, input().split())
    mark[:a+1, b:] += 1

for _ in range(Q):
    qa, qb = map(int, input().split())
    print(mark[qa][qb])

Submission status: Time Limit Exceeded

Solution code:
import itertools
N, M, Q = map(int, input().split())
P = []
LR = [[0] * (N+1) for _ in range(N+1)] 
for m in range(M):
    l, r = map(int, input().split())
    LR[l][r] += 1

for q in range(Q):
    p = list(map(int, input().split()))
    P.append(p)

csum = []
for L in LR:
    a = list(itertools.accumulate(L))
    csum.append(a)

for p in P:
    ans = 0
    l, r = p
    for c in csum[l:r+1]:
        ans += (c[r] - c[l-1])
    print (ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,q_=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(m)]
pq=[list(map(int,input().split())) for _ in range(q_)]
from collections import defaultdict
dmap=defaultdict(int)
smap=defaultdict(int)
for l,r in lr:
  dmap[(l,r)]+=1
for i in range(1,n+1):
  tmp=0
  for j in range(i,n+1):
    tmp+=dmap[(i,j)]
    smap[(i,j)]=tmp
for p,q in pq:
  ans=0
  for i in range(p,q+1):
    ans+=smap[(i,q)]
  print(ans)

Submission status: Time Limit Exceeded

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

a=[]
#b=[]
for i in range(n):
    a.append([0]*(n))
    #b.append([0]*(n))

#import numpy as np
#b=np.array(b)
#print(a)
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    #a[(r-1):n,0:l]+=1
    for j in range(r-1,n):
        for k in range(l):
            a[j][k]+=1
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[r-1][l-1]+=1

for l in range(n):
    for r in range(l,n):
        temp=a[r][l]
        for i in range(r,n):
            for j in range(0,l+1):
                b[i][j]+=temp
        #b[r:n,0:l+1]+=temp
'''
#print(a)
#print(b)

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

Submission status: Time Limit Exceeded

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

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

#import numpy as np
#b=np.array(b)
#print(a)
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[r-1][l-1]+=1

for l in range(n):
    for r in range(l,n):
        temp=a[r][l]
        for i in range(r,n):
            for j in range(0,l+1):
                b[i][j]+=temp
        #b[r:n,0:l+1]+=temp

#print(a)
#print(b)

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

Submission status: Time Limit Exceeded

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

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

import numpy as np
b=np.array(b)
#print(a)
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[r-1][l-1]+=1

for l in range(n):
    for r in range(l,n):
        temp=a[r][l]
        b[r:n,0:l+1]+=temp

#print(a)
#print(b)

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

Submission status: Time Limit Exceeded

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

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

import numpy as np
a=np.array(a)
b=np.array(b)
#print(a)
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[r-1,l-1]+=1

for l in range(n):
    for r in range(l,n):
        temp=a[r,l]
        b[r:n,0:l+1]+=temp

#print(a)
#print(b)

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

Submission status: Time Limit Exceeded

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

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

import numpy as np
a=np.array(a)

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

#print(a)

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

Submission status: Time Limit Exceeded

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

n,m,que=MI()
lis=[[0]*n for i in range(n)]
for i in range(m):
    l,r=MI()
    lis[l-1][r-1]+=1
for i in range(n):
    lis[i]=list(accumulate(lis[i]))
#print(lis)
for i in range(que):
    p,q=MI()
    ans=0
    for i in range(p,q+1):
        if i==1:
            ans+=lis[i-1][q-1]
        else:
            ans+=lis[i-1][q-1]-lis[i-1][i-2]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - AtCoder Express 2

N, M, Q = map(int, input().split())
G = [[0] * (N+1) for _ in range(N+1)]

for _ in range(M):
    L, R = map(int, input().split())
    G[L][R] += 1

for i in range(N+1):
    for j in range(N):
        G[i][j+1] += G[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
start_sets = [set() for _ in range(n+2)]
end_sets = [set() for _ in range(n+2)]
for i in range(m):
    l, r = map(int, input().split())
    start_sets[l].add(i)
    end_sets[r].add(i)

for i in range(1, n+2):
    start_sets[i] |= start_sets[i-1]
    end_sets[i] |= end_sets[i-1]

ans = []
for _ in range(q):
    p, q = map(int, input().split())
    start = start_sets[q]-start_sets[p-1]
    end = end_sets[q] - end_sets[p-1]
    res = start & end
    ans.append(len(res))
print(*ans, sep="\n")

Submission status: Time Limit Exceeded

Solution code:
para = list(map(int,input().split(' ')))
train = []
for i in range(para[1]):
    train.append(list(map(int,input().split(' '))))
ques = []
for j in range(para[2]):
    ques.append(list(map(int,input().split(' '))))

for q in ques:
    cnt = 0
    for t in train:
        if(q[0]<=t[0]):
            if(q[1]>=t[1]):
                cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
para = list(map(int,input().split(' ')))
train = []
for i in range(para[1]):
    train.append(list(map(int,input().split(' '))))
ques = []
for j in range(para[2]):
    ques.append(list(map(int,input().split(' '))))

for q in ques:
    cnt = 0
    for t in train:
        if(q[0]<=t[0] and q[1]>=t[1]):
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n, m, Q = map(int, input().split())
A = [[0]*(n) for i in range(n)]
C = [[0]*(n+1) for i in range(n)]
for i in range(m):
    l, r = map(int, input().split())
    A[r-1][l-1] += 1

for i in range(n):
    a = A[i]
    c = C[i]
    for j in range(n):
        c[j+1] = c[j] + a[j]

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

Submission status: Time Limit Exceeded

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


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    coordinate = [[0 for j in range(N)] for i in range(N)] # coordinate[i][j]の数字がx印の数を表す
    for l, r in zip(L, R):
        coordinate[l][r] += 1

    cumsum = [[0 for j in range(N+1)] for i in range(N)] # coordinate[i][p] - coordinate[i][q] (p>q)は範囲q~p-1の和
    for i in range(N):
        for j in range(N):
            cumsum[i][j+1] = cumsum[i][j] + coordinate[i][j]

    for query_l, query_r in zip(p, q):
        result = sum([cumsum[i][query_r+1] - cumsum[i][query_l] for i in range(query_l, query_r+1)])
        print(result)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens)) - 1
        R[i] = int(next(tokens)) - 1
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens)) - 1
        q[i] = int(next(tokens)) - 1
    solve(N, M, Q, L, R, p, q)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    L = [_ - 1 for _ in L]
    R = [_ - 1 for _ in R]
    p = [_ - 1 for _ in p]
    q = [_ - 1 for _ in q]

    coordinate = [[0 for j in range(N)] for i in range(N)] # coordinate[i][j]の数字がx印の数を表す
    for l, r in zip(L, R):
        coordinate[l][r] += 1

    cumsum = [[0 for j in range(N+1)] for i in range(N)] # coordinate[i][p] - coordinate[i][q] (p>q)は範囲q~p-1の和
    for i in range(N):
        for j in range(N):
            cumsum[i][j+1] = cumsum[i][j] + coordinate[i][j]

    for query_l, query_r in zip(p, q):
        result = 0
        for i in range(query_l, query_r+1):
            tmp = cumsum[i][query_r+1] - cumsum[i][query_l]
            result += tmp
        print(result)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

trains = np.zeros([n+1,n+1],dtype = np.int32)

for i in range(m):
    x,y = [int(i) for i in input().split()]
    trains[x][y] += 1
    
ans_arr = np.cumsum(np.cumsum(trains,axis = 0),axis = 1)
    
for i in range(q):
    x,y = [int(i) for i in input().split()]
    ans = ans_arr[y][y] - ans_arr[x-1][y] - ans_arr[y][x-1] + ans_arr[x-1][x-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from itertools import accumulate
def main():
    #入力
    readline=stdin.readline
    n,m,q=map(int,readline().split())
    table=[[0]*n for _ in range(n)]
    for i in range(m):
        l,r=map(lambda x:int(x)-1,readline().split())
        table[l][r]+=1

    #累積和
    for i in range(n):
        table[i]=list(accumulate(table[i]))

    ans=[0]*q
    for i in range(q):
        l,r=map(lambda x:int(x)-1,readline().split())
        t=0
        for j in range(l,r+1):
            t+=table[j][r]
        ans[i]=t

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

if __name__=="__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
table = np.zeros((N, N), np.int64)
for _ in range(M):
    L, R = map(lambda n: int(n) - 1, input().split())
    table[L][R] += 1
table = np.rot90(np.rot90(table, k=-1).cumsum(axis=0).cumsum(axis=1), k=1)
for _ in range(Q):
    p, q = map(lambda n: int(n) - 1, input().split())
    print(table[p][q])

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, M, Q, *x = map(int, open(0).read().split())
    LR, pq = x[:2*M], x[2*M:]

    mat = [[0] * (N + 1) for _ in range(N + 1)]
    c = [[0] * (N + 1) for _ in range(N + 1)]
    # ここでマトリックス作ってる
    for l, r in zip(*[iter(LR)] * 2):
        mat[l][r] += 1
    # 累積和のためのマトリックス作成
    for l in range(N+1):
        for r in range(N+1):
            for k in range(r+1):
                c[l][r] += mat[l][k]
    # S計算
    for p, q in zip(*[iter(pq)] * 2):
        ans = 0
        for l in range(p,q+1):
            ans += c[l][q] - c[l][p-1]
        print(ans)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, M, Q = map(int, input().split())
    LR = [0] * M
    pq = [{}] * Q
    for i in range(M):
        LR[i] = set(map(int, input().split()))
    for i in range(Q):
        p, q = map(int, input().split())
        pq[i] = set(range(p, q + 1))

    for i in range(Q):
        c = 0
        for j in range(M):
            if LR[j].issubset(pq[i]):
                c += 1
        print(c)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, M, Q = map(int, input().split())
    LR = [0] * M
    for i in range(M):
        LR[i] = set(map(int, input().split()))
    for i in range(Q):
        c = 0
        p, q= map(int, input().split())
        pq = set(range(p, q+1))
        for j in range(M):
            if LR[j].issubset(pq):
                c += 1
        print(c)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, M, Q = map(int, input().split())
    L = [0] * M
    R = [0] * M
    p = [0] * Q
    q = [0] * Q
    for i in range(M):
        L[i], R[i] = map(int, input().split())
    for i in range(Q):
        p[i], q[i] = map(int, input().split())
    for i in range(Q):
        c = 0
        for j in range(M):
            if p[i] <= L[j] and R[j] <= q[i]:
                c += 1
        print(c)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

Solution code:
def solve():
    N, M, Q = map(int, input().split())
    L = [0] * M
    R = [0] * M
    for i in range(M):
        L[i], R[i] = map(int, input().split())
    for i in range(Q):
        c = 0
        p, q = map(int, input().split())
        for j in range(M):
            if p <= L[j] and R[j] <= q:
                c += 1
        print(c)


if __name__ == '__main__':
    solve()

Submission status: Time Limit Exceeded

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

ts = [[0] * (n+1) for _ in range(n+1)]
for _ in range(m):
    l, r = tuple(map(int, input().split()))
    ts[l][r] += 1

from itertools import accumulate
tsa = [list(accumulate(t)) for t in ts]

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

Submission status: Time Limit Exceeded

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

ts = [[0] * (n+1) for _ in range(n+1)]
for _ in range(m):
    l, r = tuple(map(int, input().split()))
    ts[l][r] += 1

from itertools import accumulate
tsa = [list(accumulate(t)) for t in ts]

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

for i in range(M):
  a, b = map(int, input().split())
  train[a][b] += 1
  
for i in range(1, N+1):
  for j in range(1, N+1):
    train[i][j] += train[i][j-1]


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

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int,input().split())
bord = [[0 for _j in range(n+2)] for _i in range(n+2)]

for _i in range(m):
    left, right = map(int, input().split())
    bord[left][right] += 1

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

result = []
for _i in range(q):
    p, q = map(int, input().split())
    c = 0
    for i in range(p, q+1):
        c += bord[i][q]-bord[i][p-1]
    result.append(c)
print(*result)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int,input().split())
bord = [[0 for _j in range(n+1)] for _i in range(n+1)]

for _i in range(m):
    left, right = map(int, input().split())
    bord[left][right] += 1
result = []
for _i in range(q):
    p, q = map(int, input().split())
    c = 0
    for i in range(p, q+1):
        for j in range(p, q+1):
            c += bord[i][j]
    result.append(c)
print(*result)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int,input().split())
ways = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    l,r = map(int,input().split())
    ways[l][r] += 1

sgways = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(i,n+1):
        for k in range(i,j+1):
            sgways[i][j] += ways[k][j]


ans = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j in range(i,n+1):
        for k in range(i,j+1):
            ans[i][j] += sgways[i][k]
for i in range(q):
    pi,qi = map(int,input().split())
    print(ans[pi][qi])

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
from collections import deque
import math
def input(): return sys.stdin.readline().strip()
def mp(): return map(int,input().split())
def lmp(): return list(map(int,input().split()))

n,m,Q=mp()
grid=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    l,r=mp()
    for j in range(1,l+1):
        for k in range(r,n+1):
            grid[j][k]+=1
for i in range(Q):
    p,q=mp()
    print(grid[p][q])

Submission status: Time Limit Exceeded

Solution code:
import collections
N,M,Q = map(int,(input().split()))
s = [[0]*(N+1) for _ in range(N+1)]
L = [0]*M
d = collections.defaultdict(int)
for i in range(M):
    L,R = map(int,(input().split()))
    d[(L,R)] += 1
for i in range(1,N+1):
    for j in range(1,N+1):
        s[i][j] = s[i][j-1] + d[(i,j)]
for i in range(Q):
    p,q = map(int,(input().split()))
    ans = 0
    for j in range(p,q+1):
        ans += s[j][q]-s[j][p-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate

n,m,q = map(int,input().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]
lin = []

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

for i in range(n+1):
    lin.append(list(accumulate(li[i])))

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,m,q = map(int,input().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]

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

li = np.array(li)
for i in range(n+1):
    li[i] = np.cumsum(li[i])
li = li.tolist()
for i in range(q):
    l,r = map(int,input().split())
    point = 0
    for j in range(l,r+1):
        point += li[j][r]-li[j][l-1]
    print(point//2)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,m,q = map(int,input().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]

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

li = np.array(li)
for i in range(n+1):
    li[i] = np.cumsum(li[i])

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

n,m,q = map(int,input().split())
li = [[0 for i in range(n+1)]for j in range(n+1)]

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

li = np.array(li)

for i in range(q):
    l,r = map(int,input().split())
    print(np.sum(li[l:r+1,l:r+1])//2)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
S=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    l,r=map(int,input().split())
    S[l][r]+=1

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

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

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
S=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    l,r=map(int,input().split())
    S[l][r]+=1

for i in range(q):
    a,b=map(int,input().split())
    ans=0
    for y in range(a,b+1):
        for x in range(a,b+1):
            ans+=S[x][y]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys

s = sys.stdin.readlines()

N, M, Q = map(int, s[0].split())

L = [0]*M
R = [0]*M

for i, e in enumerate(s[1:M+1]):
    L[i],R[i] = map(int, e.split())

pq = []
for j in s[M+1:]:
    pq.append(list(map(int, j.split())))

# pqが1~Q個ある。それぞれで p <= L <= R <= q となる本数をMから
for k in pq:
    counter = 0
    for a,b in zip(L,R):
        if k[0] <= a and b<=k[1]:
            counter +=1
    print(counter)

Submission status: Time Limit Exceeded

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

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

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

# pqが1~Q個ある。それぞれで p <= L <= R <= q となる本数をMから
for k in pq:
    counter = 0
    for a,b in zip(L,R):
        if k[0] <= a and a<= b and b<=k[1]:
            counter +=1
    print(counter)

Submission status: Time Limit Exceeded

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

for _ in range(m):
    L, R = map(lambda x: int(x)-1, input().split())
    edges[L][R] += 1


for _ in range(q):
    p, q = map(int, input().split())
    lines = edges[p-1:q]
    print(sum(sum(row[p-1:q]) for row in lines))