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:
n, m, q = map(int,input().split())
t = [list(map(int,input().split())) for i in range(m)]
cond = [list(map(int,input().split())) for j in range(q)]
for i in range(q):
    cond1 = [(t[j][0]-cond[i][0],t[j][1]-cond[i][1]) for j in range(m)]
    cond2 = [1 if cond1[i][0] >= 0 and cond1[i][1] <= 0 else 0 for i in range(m)]
    print(sum(cond2))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
n,m,q=map(int,input().split())
a=np.zeros((n,n))
for i in range(m):
    L,R=map(int,input().split())
    a[:L,R-1:]+=1
for i in range(q):
    L,R=map(int,input().split())
    print(int(a[L-1][R-1]))

Submission status: Time Limit Exceeded

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

import numpy as np
matrix = np.array([[0 for _ in range(N+1)] for _ in range(N+1)], dtype=np.int16)

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

for i in range(1, N+1):
    for j in range(i, N+1):
        w = pairs[i][j]
        if w > 0:
            matrix[:i+1,j:] += w

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

Submission status: Time Limit Exceeded

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

import numpy as np
matrix = np.array([[0 for _ in range(N+1)] for _ in range(N+1)], dtype=np.int16)

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

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

Submission status: Time Limit Exceeded

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

import numpy as np
matrix = np.array([[0 for _ in range(N+1)] for _ in range(N+1)])

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

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = list(map(int,input().split()))
LR = [[] for i in range(N)]
for i in range(M):
    l,r = list(map(int,input().split()))
    LR[l-1].append(["L",i])
    LR[r-1].append(["R",i])

Map = [[0 for j in range(N)] for i in range(N)]

for i in range(N):
    count = 0
    flag = [False for i in range(M)]
    for j in range(i,N):
        for a in LR[j]:
            b,c = a
            if b=="L":
                flag[c]=True
            else:
                if flag[c]:
                    flag[c]=False
                    count+=1
        Map[i][j]=count

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
def main():
	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)]

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

	for l, r in LR:
		lines[l][r] += 1

	for p, q in PQ:
		lines_sum = 0
		for y in range(p, q + 1):
			for x in range(p, q + 1):
				lines_sum += lines[y][x]
		print(lines_sum)
main()

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

lines = [[0] * N for _ in range(N)]

for l, r in LR:
	l, r = l - 1, r - 1
	lines[l][r] += 1

for p, q in PQ:
	p, q = p - 1, q - 1
	lines_sum = 0
	for y in range(p, q + 1):
		for x in range(p, q + 1):
			lines_sum += lines[y][x]
	print(lines_sum)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]


def solve1():
    table = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        table[l][r] += 1
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = table[i][j - 1] + table[i][j]
    for p, q in pq_array:
        res = 0
        for i in range(p, q + 1):
            # print(i)
            res += table[i][q]
        print(res)

    return 0


# 横軸：スタート
# 縦軸：ゴール
# 2次元累積和で解く
def solve2():
    cumulative_lr = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        for i in range(1, l + 1):
            for j in range(r, n + 1):
                cumulative_lr[i][j] += 1

    for p, q in pq_array:
        print(cumulative_lr[p][q])


if __name__ == '__main__':
    solve1()

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]


def solve1():
    table = [[0 for x in range(n+1)] for y in range(n+1)]
    for l, r in lr_array:
        table[l][r] += 1

    return 0


# 横軸：スタート
# 縦軸：ゴール
# 2次元累積和で解く
def solve2():
    cumulative_lr = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        for i in range(1, l + 1):
            for j in range(r, n + 1):
                cumulative_lr[i][j] += 1

    for p, q in pq_array:
        print(cumulative_lr[p][q])


if __name__ == '__main__':
    solve2()

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]

# 横軸：スタート
# 縦軸：ゴール
cumulative_lr = [[0 for x in range(n + 1)] for y in range(n + 1)]
for l, r in lr_array:
    for i in range(1, l+1):
        for j in range(r, n + 1):
            cumulative_lr[i][j] += 1

for p, q in pq_array:
    print(cumulative_lr[p][q])

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_cities = [[] for _ in range(N)]
for l, r in LR:
	l, r = l - 1, r - 1
	from_cities[l] += [r - l]

#print(from_cities)

for p, q in PQ:
	c, p, q = 0, p - 1, q - 1
	for i in range(p, q + 1):
		for line in from_cities[i]:
			if line <= q - i:
				c += 1
	print(c)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
lr = [0] * M
for i in range(M):
    lr[i] = list(map(int,input().split()))
# 長さが短い順にソート
lr.sort(key=lambda x:x[0]-x[1], reverse=True)
pq = [0] * Q
for i in range(Q):
    pq[i] = list(map(int,input().split()))

for p,q in pq:
    x = q-p
    count = 0
    for l,r in lr:
        if r-l > x:
            break
        if p <= l and r <= q:
            count += 1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
#D問題
N,M,Q = map(int,input().split())
LR = [list(map(int,input().split())) for i in range(M)]
PQ = [list(map(int,input().split())) for i in range(Q)]
DN = [[0 for j in range(N)] for i in range(N)]

for i in range(M):
    l = LR[i][0]
    r = LR[i][1]
    DN[l-1][r-1]+=1

for i in range(Q):
    ans = 0
    p = PQ[i][0]
    q = PQ[i][1]
    for j in range(q-p+1):
        P = DN[p+j-1]
        ans+=sum(P[p-1:q])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M, Q = map(int, input().split(" "))
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for _ in range(M):
		l, r = map(int, input().split(" "))
		l -= 1
		r -= 1
		N_list[l][r] += 1
		
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		
		ans = 0
		for i in range(p, q+1):
			for j in range(p, q+1):
				ans += N_list[i][j]
		print(ans)
		
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M, Q = map(int, input().split(" "))
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for _ in range(M):
		l, r = map(int, input().split(" "))
		l -= 1
		r -= 1
		for a in range(l, N):
			for b in range(r, N):
				N_list[a][b] += 1
		
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		
		a = 0
		b = 0
		c = 0
		if p != 0:
			a = N_list[q][p-1]
			b = N_list[p-1][q]
			c = N_list[p-1][p-1]
		ans = N_list[q][q] - a - b + c
		print(ans)
		
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np

def main():
	N, M, Q = map(int, input().split(" "))
	
	LR = []
	for _ in range(M):
		l, r = map(int, input().split(" "))
		LR.append((l, r))
		
	PQ = []
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		PQ.append((p, q))
	
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for i, val in enumerate(LR):
		l, r = val
		l -= 1
		r -= 1
		for a in range(l, N):
			for b in range(r, N):
				N_list[a][b] += 1
	
	for i, val in enumerate(PQ):
		p, q = val
		p -= 1
		q -= 1
		
		a = 0
		b = 0
		c = 0
		if p != 0:
			a = N_list[q][p-1]
			b = N_list[p-1][q]
			c = N_list[p-1][p-1]
		ans = N_list[q][q] - a - b + c
		print(ans)
		
	#print("{} {}".format(p-1, q))
	#print(N_list)
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

N,M,Q = [int(x) for x in input().split()]
lr = [[int(x) for x in input().split()]for _ in range(M)]
pq = [[int(x) for x in input().split()]for _ in range(Q)]

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

for i in lr:
    for j in range(i[0]+1):
        dp[j][i[1]]+=1

for i in range(N,0,-1):
    for j in range(i,N+1):
        if(j!=i):
            dp[i][j] += dp[i][j-1]

for i in pq:
    print(dp[i[0]][i[1]])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)

N,M,Q = [int(x) for x in input().split()]
lr = [[int(x) for x in input().split()]for _ in range(M)]
pq = [[int(x) for x in input().split()]for _ in range(Q)]

li = [[]for _ in range(N+1)]
for i in lr:
    li[i[0]].append(i[1])
for i in pq:
    cnt = 0
    for j in li[i[0]:i[1]+1]:
        for x in j:
            if(x<=i[1]):
                cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
	
def main():
	N, M, Q = map(int, input().split(" "))
	
	LR = []
	for _ in range(M):
		l, r = map(int, input().split(" "))
		LR.append((l, r))
		
	LRs = []
	for i in LR:
		l, r = i
		l -= 1
		tmp = [0 for i in range(N)]
		for i in range(l, r):
			tmp[i] = 1
		for i in range(r, N):
			tmp[i] = 2
		LRs.append(tmp)
		
	ans = []
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		tmp = 0
		for val in LRs:
			if val[p] < 1 and val[q] > 1:
				tmp += 1
			elif (p == 0 or val[p-1] == 0) and (q == N-1 or val[q+1] == 2):
				tmp += 1	
		ans.append(tmp)
			
	for i in ans:
		print(i)
	#print(LRs)
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
	
def main():
	N, M, Q = map(int, input().split(" "))
	
	LR = []
	for _ in range(M):
		l, r = map(int, input().split(" "))
		LR.append((l, r))
		
	PQ = []
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		PQ.append((p, q))
	
	ans = []
	for i in PQ:
		p, q = i
		tmp = 0
		for j in LR:
			l, r = j
			if p <= l and r <= q:
				tmp += 1
		ans.append(tmp)
	
	for i in ans:
		print(i)
	
	
if __name__ == "__main__":
	main()

Submission status: Time Limit Exceeded

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


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

Submission status: Time Limit Exceeded

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

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

c = [[0 for i in range(N)] for j in range(N)]
for i in range(N):
    cnt = 0
    for j in range(N):
        cnt += train[i][j]
        c[i][j] = cnt

for x in range(Q):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    cnt2 = 0
    for i in range(p,q+1):
        if p == 0:
            cnt2 += c[i][q]
        else:
            cnt2 += c[i][q] - c[i][p-1]
    print(cnt2)

Submission status: Time Limit Exceeded

Solution code:
# ABC106D
import numpy as np
N,M,Q = map(int,input().split())

s = np.zeros([M,N])
f = np.zeros([M,N])
for m in range(M):
    L,R = map(int,input().split())
    s[m,:L] = 1
    f[m,R-1:] = -1

for x in range(Q):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    ans = s[:,p]-f[:,q]
    print(len(ans[ans==2]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M,Q = map(int,input().split())

s = []
f = []
for m in range(M):
    L,R = map(int,input().split())
    s.append([1 for i in range(L)]+[0 for i in range(N-L)])
    f.append([0 for i in range(R-1)]+[-1 for i in range(N-R+1)])


for x in range(Q):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    ans = np.array(s)[:,p]-np.array(f)[:,q]
    print(len(ans[ans==2]))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

trains = np.zeros((N, N))
for i in range(M):
    l, r = list(map(int, input().split()))
    trains[l-1, r-1] += 1

for j in range(Q):
    p, q = list(map(int, input().split()))
    t = trains[p-1:q, p-1:q]
    print(int(np.sum(t)))

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]

for p, q in pq_array:
    cnt = 0
    for l, r in lr_array:
        if p <= l and r <= q:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

trains = np.zeros((M, N))
for i in range(M):
    l, r = list(map(int, input().split()))
    trains[i, l-1] = 1
    trains[i, r-1] = trains[i, r-1]+1


for j in range(Q):
    p, q = list(map(int, input().split()))
    column_sum = np.sum(trains[:, p-1:q], axis=1)
    a = column_sum[np.where(column_sum == 2)]
    print(np.size(a))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

trains = np.zeros((M, N))
# 電車の都市区間が1始まりなことに注意
for i in range(M):
    l, r = list(map(int, input().split()))
    trains[i, l-1] = 1
    trains[i, r-1] = trains[i, r-1]+1


for j in range(Q):
    p, q = list(map(int, input().split()))
    t = trains[:, p-1:q]
    column_sum = np.sum(t, axis=1)
    a = column_sum[np.where(column_sum == 2)]
    print(np.size(a))

Submission status: Time Limit Exceeded

Solution code:
"""
累積和っぽい

始点と終点の"2"つを指定しなければいけない
⇨二次元累積和ってやつ。

参考
https://qiita.com/drken/items/56a6b68edef8fc605821
"""

import numpy as np
N,M,Q = map(int,input().split())
A = np.zeros((N+1,N+1))
Acum = np.zeros((N+1,N+1))

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

#2次元累積和
for i in range(N):
    for j in range(N):
        Acum[i+1][j+1] = Acum[i][j+1] + Acum[i+1][j] - Acum[i][j] + A[i][j]

# print(Acum)
for _ in range(Q):
    p,q= map(int,input().split())
    A = Acum[q,q]-Acum[p-1,q]-Acum[q,p-1]+Acum[p-1,p-1]
    print(int(A))

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = [ int(it) for it in input().split()]

grid = [ [0]*N for i in range(N) ]
gridsml = [ [0]*N for i in range(N) ]

for i in range(M):
  s,g = [ int(it)-1 for it in input().split()]
  grid[s][g]+=1

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


for i in range(Q):
  s,g = [ int(it)-1 for it in input().split()]
  m = 0
  for i in range(s,N):
    m += gridsml[i][g]
  print (m)

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
n, m, q = map(int, input().split())
x = [[0 for i in range(n + 1)] for j in range(n + 1)]
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
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x[i][j] = x[i][j - 1] + c[i][j]
for k in range(q):
    ans = 0
    p, q2 = map(int, input().split())
    for i in range(p, q2 + 1):
        ans += x[i][q2] - x[i][p - 1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
x = [[0 for i in range(n + 1)] for j in range(n + 1)]
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
for i in range(1, n + 1):
    for j in range(1, n + 1):
        x[i][j] = x[i][j - 1] + c[i][j]
for k in range(q):
    ans = 0
    p, q2 = map(int, input().split())
    for i in range(p, q2 + 1):
        ans += x[i][q2] - x[i][p - 1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import numpy as np
import random

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

count = np.zeros((N+1, N+1)).astype(int)
memo = np.zeros((N+1, N+1)).astype(int)

for _ in range(M):
    p, q = map(int, input().rstrip().split(' '))
    count[p, q] += 1

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

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

Submission status: Time Limit Exceeded

Solution code:
# coding: utf-8
# Your code here!
import numpy as np

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

memo = np.zeros((N, N)).astype(int)

for _ in range(M):
    p, q = map(int, input().rstrip().split(' '))
    memo[:p, q-1:] += 1

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

Submission status: Time Limit Exceeded

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

n, m, q = map(int, input().split())
qa = []
ma = [[0 for i in range(n + 2)] for _ in range(m + 1)]
for i in range(m):
    x, y = map(int, input().split())
    ma[i][x] += 1
    ma[i][y + 1] -= 1
for i in range(m + 1):
    for j in range(1, n + 2):
        ma[i][j] = 1 if ma[i][j] + ma[i][j-1] > 0 else 0
for i in range(q):
    x, y = map(int ,input().split())
    sm = 0
    for j in ma:
        if j[x - 1] == 0 and j[y + 1] == 0:
            for k in range(x, y + 1):
                if j[k] == 1:
                    sm += 1
                    break
    print(sm)

Submission status: Time Limit Exceeded

Solution code:
import bisect

N, M, Q = map(int, input().split())
tmp = [list(map(int, input().split())) for _ in range(M)]
tmp.sort(key=lambda x: x[0])
L, R = [], []
for i in range(M):
    L.append(tmp[i][0])
    R.append(tmp[i][1])

for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    INDEX_1 = bisect.bisect_left(L, p)
    INDEX_2 = bisect.bisect_right(L, q)
    for i in range(INDEX_1, INDEX_2):
        if R[i] <= q:
            ans += 1
    print(ans)

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 _ in range(m):
    l, r = map(lambda x: int(x) - 1, input().split())
    lr[l][r] += 1

c = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        if j == 0:
            c[i][j] = lr[i][j]
        else:
            c[i][j] = c[i][j-1] + lr[i][j]

for _ in range(q):
    p, q = map(lambda x: int(x) - 1, input().split())
    count = 0
    for i in range(p, q+1):
        if p == 0:
            count += c[i][q]
        else:
            count += (c[i][q] - c[i][p-1])

    print(count)

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 _ in range(m):
    l, r = map(lambda x: int(x) - 1, input().split())
    lr[l][r] += 1

dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
    for j in range(n):
        added = 0
        for k in range(i, j+1):
            added += lr[k][j]
        dp[i][j] = dp[i][j-1] + added

for _ in range(q):
    p, q = map(lambda x: int(x) - 1, input().split())
    print(dp[p][q])

Submission status: Time Limit Exceeded

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

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

for l in range(1, N+1):
    for r in range(1, N+1):
        cum_sum[l][r] += cum_sum[l][r-1]

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def f(nc, nt, nq):
    t = [list(map(int, input().split())) for _ in range(nt)]
    q = [list(map(int, input().split())) for _ in range(nq)]
    dp = np.zeros((nc + 1, nc + 1), dtype="i8")
    for l, r in t:
        dp[l][r] += 1
    for l, r in q:
        print(np.sum(dp[l:r+1,l:r+1]))


nc, nt, nq = map(int, input().split())
f(nc, nt, nq)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def f(nc, nt, nq):
    t = [list(map(int, input().split())) for _ in range(nt)]
    q = [list(map(int, input().split())) for _ in range(nq)]
    dp = np.zeros((nc + 1, nc + 1), dtype="i8")
    for l, r in t:
        dp[:l + 1, r:] += 1
    for l, r in q:
        print(dp[l][r])


nc, nt, nq = map(int, input().split())
f(nc, nt, nq)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

nc, nt, nq = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(nt)]
q = [list(map(int, input().split())) for _ in range(nq)]
dp = np.zeros((nc + 1, nc + 1), dtype="i8")
for l, r in t:
    dp[:l + 1, r:] += 1
for l, r in q:
    print(dp[l][r])

Submission status: Time Limit Exceeded

Solution code:
def f():
    nc, nt, nq = map(int, input().split())
    t = [list(map(int, input().split())) for _ in range(nt)]
    q = [list(map(int, input().split())) for _ in range(nq)]
    dp = [[0] * (nc + 1) for _ in range(nc + 1)]
    for l, r in t:
        for i in range(1, l + 1):
            dpi = dp[i]
            for j in range(r, nc + 1):
                dpi[j] += 1
    for l, r in q:
        print(dp[l][r])

f()

Submission status: Time Limit Exceeded

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

import numpy as np
a=np.zeros((n+1,n+1),dtype=int)
for i in range(m):
    a[lr[i][0]:,lr[i][1]:]+=1
for i in range(q):
    print(a[pq[i][1],pq[i][1]]-a[pq[i][0]-1,pq[i][1]])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import math

def main():
    N, M, Q = map(int, input().split())
    matrix = np.zeros((N + 1, N + 1))
    cmatrix = np.zeros((N + 1, N + 1))
    for i in range(M):
        left, right = map(int, input().split())
        matrix[left][right] += 1
    # print(matrix)

    for i in range(1, N+1):
        for j in range(1, N+1):
            # cmatrix[i][j] = matrix[i][j]
            cmatrix[i][j] = cmatrix[i][j - 1] + matrix[i][j]
    # print(cmatrix)
    
    for i in range(Q):
        left, right = map(int, input().split())
        num = 0
        for j in range(left, right + 1):
            num += cmatrix[j][right] - cmatrix[j][left - 1]
        print(int(num))

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline

n,m,q = map(int,input().split())
c=[[0 for i in range(n+1)] for j in range(n+1)]
x=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    l,r = map(int,input().split())
    x[l][r] += 1
for i in range(1,n+1):
    for j in range(1,n+1):
        c[i][j] = c[i][j-1] + x[i][j]
for i in range(q):
    p,q = map(int,input().split())
    sum = 0
    for j in range(p,q+1):
         sum+= c[j][q] - c[j][p-1]
    print(sum)

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)]
x=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    l,r = map(int,input().split())
    x[l][r] += 1
for i in range(1,n+1):
    for j in range(1,n+1):
        c[i][j] = c[i][j-1] + x[i][j]
for i in range(q):
    p,q = map(int,input().split())
    sum = 0
    for j in range(p,q+1):
         sum+= c[j][q] - c[j][p-1]
    print(sum)

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    n, m, q, *lrpq = map(int, string.split())
    lr, pq = lrpq[:2 * m], lrpq[2 * m:]
    t = [[0] * (n + 1) for _ in range(n + 1)]
    for l, r in zip(lr[::2], lr[1::2]):
        t[l][r] += 1
    for i in range(n + 1):
        for j in range(n + 1):
            if j > 0:
                t[i][j] += t[i][j - 1]

    ans = [
        str(sum([t[i][q] - t[i][p - 1]
                 for i in range(p, q + 1)]))
        for p, q in zip(pq[::2], pq[1::2])
    ]
    return "\n".join(ans)


if __name__ == '__main__':
    n, m, q = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, q) + '\n'.join([input() for _ in range(m + q)])))

Submission status: Time Limit Exceeded

Solution code:
def solve(string):
    n, m, q, *lrpq = map(int, string.split())
    lr, pq = lrpq[:2 * m], lrpq[2 * m:]
    ans = []
    for p, q in zip(pq[::2], pq[1::2]):
        ans.append(str(sum([1 if p <= l and r <= q else 0 for l, r in zip(lr[::2], lr[1::2])])))
    return "\n".join(ans)


if __name__ == '__main__':
    n, m, q = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, q) + '\n'.join([input() for _ in range(m + q)])))

Submission status: Time Limit Exceeded

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

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

for i in range(n):
  for j in range(i, n):
    for k in range(i, j + 1):
      for l in range(k, j + 1):
        List2[i][j] += List1[k][l]


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

Submission status: Time Limit Exceeded

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

for i in range(m):
  l,r = map(int, input().split())
  for j in range(l):
    for k in range(r - 1, n):
      List[j][k] += 1
for i in range(q):
  a, b = map(int, input().split())
  print(List[a - 1][b - 1])