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:
cond=input().split(" ")
n=int(cond[0])
m=int(cond[1])
q=int(cond[2])
train=[[0 for i in range(2)] for j in range(m)]
sect=[[0 for i in range(2)] for j in range(q)]
#print(train)

def judge(arr_m,arr_q):
    a=0
    #print(arr_m)
    #print(arr_q)
    #print("*")
    if arr_q[0]<=arr_m[0] and arr_m[1]<=arr_q[1]:
        a=1
    return a

for i in range(m):
    train[i]=input().split(" ")
    train[i]=list(map(int,train[i]))
    #print(train)
for i in range(q):
    sect[i]=input().split(" ")
    sect[i]=list(map(int,sect[i]))
    #print(sect)
for i in range(q):
    ans=0
    for j in range(m):
        ans+=judge(train[j],sect[i])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
train = [tuple(map(int, input().split())) for _ in range(m)]
quest = [tuple(map(int, input().split())) for _ in range(q)]
dp = [[0 for _ in range(n)] for _ in range(n)]
d = {}
for l in range(n):
    for r in range(l,n):
        d[(l,r)] = 0
for p, q in train:
    d[(p-1,q-1)] += 1
for l in range(n):
    dp[l][l] = d[(l,l)]
for w in range(1,n):
    for l in range(n-w):
        add = 0
        for addl in range(l,l+w+1):
            add += d[(addl, l+w)]
        dp[l][l+w] = dp[l][l+w-1] + add
for l, r in quest:
    print(dp[l-1][r-1])

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M, Q = map(int, input().split())
    LR = [[0 for _ in range(N + 1)] for _ in range((N + 1))]
    for _ in range(M):
        L, R = map(int, input().split())
        LR[L][R] += 1
    ans = []
    for _ in range(Q):
        p, q = map(int, input().split())
        c = 0
        for R in LR[p:]:
            c += sum(R[:q + 1])
        ans.append(c)
    for a in ans:
        print(a)


main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    N, M, Q = map(int, input().split())
    LR = []
    for _ in range(M):
        L, R = map(int, input().split())
        LR.append((L, R))
    ans = []
    for _ in range(Q):
        p, q = map(int, input().split())
        c = 0
        for L, R in LR:
            if p > L or R > q:
                continue
            c += 1
        ans.append(c)
    for a in ans:
        print(a)


main()

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
trains = []
question = []
for i in range(M):
    trains.append(list(map(int,input().split())))
for j in range(Q):
    question.append(list(map(int,input().split())))
for que in question:
    ans = 0
    for train in trains:
        if train[0]>=que[0] and train[1]<=que[1]:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
int_n, int_m, int_q = map(int, input().split())
li_m = list()
li_q = list()

for m in range(int_m):
    li_m.append(tuple(map(int, input().split())))

for q in range(int_q):
    li_q.append(tuple(map(int, input().split())))

li_answer = [0] * int_q

for idx, (q_start, q_end) in enumerate(li_q):
    for m_start, m_end in li_m:
        if q_start <= m_start and m_end <= q_end:
            li_answer[idx] += 1

for a in li_answer:
    print(a)

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
  input = sys.stdin.readline
  N, M, Q  = map(int, input().split())
  
  DP = [[0 for _ in range(N+1)] for _ in range(N+1)] 
  for _ in range(M):
    l, r = map(int, input().split())
    for i in range(l+1):
      for j in range(r, N+1):
        DP[i][j] += 1

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


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
  input = sys.stdin.readline
  N, M, Q  = map(int, input().split())
  
  DP = [[0 for _ in range(501)] for _ in range(N+1)] 
  for _ in range(M):
    l, r = map(int, input().split())
    DP[l][r] += 1

  A = [[0 for _ in range(N+1)] for _ 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):
        A[i][j] += sum(DP[k][:j+1])


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


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
  input = sys.stdin.readline
  N, M, Q  = map(int, input().split())
  
  DP = [[0 for _ in range(501)] for _ in range(501)] 
  for _ in range(M):
    l, r = map(int, input().split())
    for i in range(1, l+1):
      for j in range(r, 501):
        DP[i][j] += 1

  for _ in range(Q):
    p, q = map(int, input().split())
    ans = 0
    print(DP[p][q])


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys

def main():
  input = sys.stdin.readline
  N, M, Q  = map(int, input().split())
  
  DP = [[0 for _ in range(501)] for _ in range(501)] 
  for _ in range(M):
    l, r = map(int, input().split())
    DP[l][r] += 1

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


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter
import bisect

n, m, Q = map(int, input().split())
train = [list(map(int, input().split())) + [i] for i in range(m)]
train_L = []
train_R = []
L_n = []
R_n = []
for i in sorted(train, key=itemgetter(0)):
    train_L.append(i[0])
    L_n.append(i[2])
for i in sorted(train, key=itemgetter(1)):
    train_R.append(i[1])
    R_n.append(i[2])
for i in range(Q):
    p, q = map(int, input().split())
    p_set = set(L_n[bisect.bisect_left(train_L, p):])
    q_set = set(R_n[:bisect.bisect_right(train_R, q)])
    print(len(p_set & q_set))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

array = np.zeros([n,n])
for _ in range(m):
    p, q = map(int, input().split())
    array[p-1][q-1] += 1
    
array2 = np.zeros([n,n])
for p in range(n):
    for q in range(n):
        array2[p][q] = sum(sum(array[p:, :q+1]))

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

array = np.zeros([n,n])
for _ in range(m):
    p, q = map(int, input().split())
    array[p-1][q-1] += 1

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

Submission status: Time Limit Exceeded

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

arr = [[0 for j in range(n)] for i in range(n)]
arr_sum = [[0 for j in range(n)] for i in range(n)]
arr_sum2 = [[0 for j in range(n)] for i in range(n)]

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

for i in range(n):
    for j in range(n):
        if i <= j:
            arr_sum[i][j] = sum(arr[i][:j+1])

for i in range(n):
    for j in range(n):
        if i <= j:
            for k in range(i,j+1):
                arr_sum2[i][j] += arr_sum[k][j]


ans_arr = []
for k in range(q):
    p, q = map(int, input().split())
    ans = arr_sum2[p-1][q-1]
    ans_arr.append(ans)

for i in ans_arr:
    print(i)

Submission status: Time Limit Exceeded

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

arr = [[0 for j in range(n)] for i in range(n)]
arr_sum = [[0 for j in range(n)] for i in range(n)]

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

for i in range(n):
    for j in range(n):
        if i <= j:
            arr_sum[i][j] = sum(arr[i][:j+1])


ans_arr = []
for k in range(q):
    ans = 0
    p, q = map(int, input().split())
    for i in range(p-1, q):
        ans += arr_sum[i][q-1]
    ans_arr.append(ans)

for i in ans_arr:
    print(i)

Submission status: Time Limit Exceeded

Solution code:
n,m,q= map(int,input().split())
lrList=[list(map(int,input().split()))for i in range(m)]
pqList=[list(map(int,input().split()))for i in range(q)]
for pq in pqList:
    ans = 0
    for lr in lrList:
        ans +=(pq[0] <= lr[0] and pq[1] >= lr[1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,q= map(int,input().split())
lrList=[list(map(int,input().split()))for i in range(m)]
pqList=[list(map(int,input().split()))for i in range(q)]
for pq in pqList:
    ans = 0
    for lr in lrList:
        if pq[0] <= lr[0] and pq[1] >= lr[1]:
            ans +=1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,q= map(int,input().split())
lrList=[list(map(int,input().split()))for i in range(m)]
pqList=[list(map(int,input().split()))for i in range(q)]
for pq in pqList:
    ans = list(filter(lambda x: pq[0]<=x[0] and pq[1]>=x[1],lrList))
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
n,m,q= map(int,input().split())
lrList=[list(map(int,input().split()))for i in range(m)]
pqList=[list(map(int,input().split()))for i in range(q)]
for pq in pqList:
    ans = list(filter(lambda x: pq[0]<=x[0],lrList))
    ans = list(filter(lambda x: pq[1]>=x[1],ans))
    print(len(ans))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M,Q = IL()
cnt = np.zeros((N+1,N+1))

l = [IL() for i in range(M)]
for i in range(M):
    cnt[:l[i][0]+1,l[i][1]:] += 1

ans = [IL() for i in range(Q)]
for i in range(Q):
    print(int(cnt[ans[i][0]][ans[i][1]]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M,Q = IL()
cnt = np.zeros((N+1,N+1))

for i in range(M):
    a,b = IL()
    cnt[:a+1,b:] += 1

for i in range(Q):
    c,d = IL()
    print(int(cnt[c][d]))

Submission status: Time Limit Exceeded

Solution code:
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def nibutan(n,list):
    left = 0
    right = len(list)
    while left+1 != right:
        middle = (left+right)//2
        if list[middle] <= n:
            left = middle
        else:
            right = middle
    return left+1

N,M,Q = IL()

l = [[] for i in range(N+1)]

for i in range(M):
    a,b = IL()
    l[a].append(b)

for i in l:
    i.sort()

for i in range(Q):
    cnt = 0
    start, end = IL()
    for j in range(start,end+1):
        if len(l[j]) == 0 or l[j][0] > end:
            continue
        elif l[j][-1] <= end:
            cnt += len(l[j])
        else:
            cnt += nibutan(end,l[j])
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def nibutan(n,list):
    left = 0
    right = len(list)
    while left+1 != right:
        middle = (left+right)//2
        if list[middle] <= n:
            left = middle
        else:
            right = middle
    return left+1

N,M,Q = IL()

l = [[] for i in range(N+1)]

for i in range(M):
    a,b = IL()
    l[a].append(b)

for i in l:
    i.sort()

for i in range(Q):
    cnt = 0
    start, end = IL()
    for j in range(start,end+1):
        if len(l[j]) == 0 or l[j][0] > end:
            continue
        elif l[j][-1] <= end:
            cnt += len(l[j])
        else:
            cnt += nibutan(end,l[j])
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

def nibutan(n,list):
    left = 0
    right = len(list)
    while left+1 != right:
        middle = (left+right)//2
        if list[middle] <= n:
            left = middle
        else:
            right = middle
    return left+1

N,M,Q = IL()

l = [[] for i in range(N+1)]

for i in range(M):
    a,b = IL()
    l[a].append(b)

for i in l:
    i.sort()

Ql = [IL() for i in range(Q)]

for i in range(Q):
    cnt = 0
    start, end = Ql[i]
    for j in range(start,end+1):
        if len(l[j]) == 0:
            continue
        if l[j][0] > end:
            continue
        elif l[j][-1] <= end:
            cnt += len(l[j])
        else:
            cnt += nibutan(end,l[j])
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

N,M,Q = IL()

l = [[] for i in range(N+1)]

for i in range(M):
    a,b = IL()
    l[a].append(b)

for i in l:
    i.sort()

Ql = [IL() for i in range(Q)]

for i in range(Q):
    cnt = 0
    start, end = Ql[i]
    for j in range(start,end+1):
        for k in range(len(l[j])):
            if l[j][k] <= end:
                cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:

N, M, Q = map(int, input().split())
A = [[0] * N for _ in range(N)]
for _ in range(M):
    l, m = map(int, input().split())
    A[l - 1][m - 1] += 1

questions = []
for _ in range(Q):
    p, q = map(int, input().split())
    questions.append((p - 1, q - 1))


D = []
for l in range(N):
    s = 0
    d = []
    for r in range(N):
        s += A[l][r]
        d.append(s)
    D.append(d)

for question in questions:
    print(sum([D[i][question[1]]
               for i in range(question[0], question[1] + 1)]))

Submission status: Time Limit Exceeded

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

questions = []
for _ in range(Q):
    p, q = map(int, input().split())
    questions.append((p - 1, q - 1))


D = []
for l in range(N):
    s = 0
    d = []
    for r in range(N):
        s += A[l][r]
        d.append(s)
    D.append(d)

for question in questions:
    print(sum([D[i][question[1]] for i in range(question[0], N)]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

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

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


def solve():

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

    ans = []

    for _ in range(Q):
        ql, qr = map(int, input().split())
        tmp = 0
        for i in range(ql, qr+1):
            tmp += mat[i][qr] - mat[i][ql-1]
        ans.append(tmp)

    for a in ans:
        print(a)


def solve2():

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

    ans = [0]*Q
    for i in range(Q):
        ql, qr = map(int, input().split())
        t = mat[qr][qr] - mat[ql-1][qr] - mat[qr][ql-1] + mat[ql-1][ql-1]
        ans[i] = t

    for a in ans:
        print(a)


solve()

Submission status: Time Limit Exceeded

Solution code:
import itertools

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

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

totals = [[0] * (n + 1) for _ in range(n + 1)]
for i, j in itertools.product(range(1, n + 1), repeat=2):
    totals[i][j] += totals[i][j - 1] + matrix[i][j]

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

Submission status: Time Limit Exceeded

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

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

count = [[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l, r = map(int, input().split())
    count[l][r] += 1

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
train = []
ques=[]
for i in range(M):
  x = input().split()
  x = [int(a) for a in x]
  train.append(x)
  
for j in range(Q):
  p, q = map(int, input().split())
  count = 0
  for k in range(M):
    if p <= train[k][0] and q>= train[k][1]:
      count +=1
  print(count)

Submission status: Time Limit Exceeded

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

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#横にn個入力
n, m, q = map(int, input().split())
#行列
s = []
for i in range(m):#h:高さ
    s.append([int(m) for m in input().split()] + [i])
# 行列
t = []
for i in range(q):  # h:高さ
    t.append([int(m) for m in input().split()])

LR = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
for v in range(m):
     LR[s[v][0]][s[v][1]] += 1
for j in range(1, n + 1):
    for i in range(1, n + 1):#Lについての累積和
        LR[i][j] += LR[i - 1][j]

for k in range(q):
    tmp = 0
    for j in range(t[k][0], t[k][1] + 1):#Rについてみていく
        tmp += LR[t[k][1]][j] - LR[t[k][0] - 1][j]

    print(tmp)

Submission status: Time Limit Exceeded

Solution code:
num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * (num_city + 1) for i in range(0, num_city + 1)]
for i in range(0, num_train):
    start, arrive = [int(j) for j in input().split()]
    trains[start][arrive] += 1

#累積和表を作る
trains_cumulative_sum = [[0] * (num_city + 1) for i in range(0, num_city  + 1)]
for start in range(0, num_city + 1):
    for arrive in range(0, num_city + 1):
        trains_cumulative_sum[start][arrive] = trains_cumulative_sum[start][arrive - 1] + trains[start][arrive]

for i in range(0, num_question):
    start, arrive = [int(j) for j in input().split()]
    result = 0
    for j in range(start, arrive + 1):
        result += trains_cumulative_sum[j][arrive]
    print(result)

Submission status: Time Limit Exceeded

Solution code:
num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = [[0] * num_city for i in range(0, num_city)]
for i in range(0, num_train):
    start, arrive = [int(j) - 1 for j in input().split()]
    trains[start][arrive] += 1

#累積和表を作る
trains_cumulative_sum = [[0] * num_city for i in range(0, num_city)]
for start in range(0, num_city):
    for arrive in range(0, num_city):
        if arrive != 0:
            trains_cumulative_sum[start][arrive] += trains_cumulative_sum[start][arrive - 1]
        trains_cumulative_sum[start][arrive] += trains[start][arrive]

answers = []
for i in range(0, num_question):
    start, arrive = [int(j) - 1 for j in input().split()]
    result = 0
    for j in range(start, arrive + 1):
        result += trains_cumulative_sum[j][arrive]
    answers.append(result)

for answer in answers:
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
num_city, num_train, num_question = [int(i) for i in input().split()]

#電車の数
trains = {}
for i in range(0, num_train):
    start, arrive = [int(j) - 1 for j in input().split()]
    if (start, arrive ) in trains:
        trains[(start, arrive)] += 1
    else:
        trains[(start, arrive)] = 1

#累積和表を作る
trains_cumulative_sum = {}
for start in range(0, num_city):
    for arrive in range(0, num_city):
        if arrive == 0:
            trains_cumulative_sum[(start, arrive)] = 0
        else:
            trains_cumulative_sum[(start, arrive)] = trains_cumulative_sum[(start, arrive - 1)]

        if (start, arrive) in trains:
            trains_cumulative_sum[(start, arrive)] += trains[(start, arrive)]

answers = []
for i in range(0, num_question):
    start, arrive = [int(j) - 1 for j in input().split()]
    result = 0
    for j in range(start, arrive + 1):
        result += trains_cumulative_sum[(j, arrive)]
    answers.append(result)

for answer in answers:
    print(answer)

Submission status: Time Limit Exceeded

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

table = [[0]*n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    table[a-1][b-1] += 1

s = [[0] for i in range(n)]

for i in range(n):
    for j in range(n):
        s[i].append(s[i][-1]+table[i][j])

for _ in range(q):
    i, j = map(int, input().split())
    tmp = 0
    if i == 1:
        for k in range(i-1, j):
            tmp += s[k][j]
    else:
        for k in range(i-1, j):
            tmp += s[k][j] - s[k][i-1]
    print(tmp)

Submission status: Time Limit Exceeded

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

table = [[0]*n for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    table[a-1][b-1] += 1

s = [[table[i][0]] for i in range(n)]

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

for _ in range(q):
    i, j = map(int, input().split())
    tmp = 0
    if i == 1:
        for k in range(i-1, j):
            tmp += s[k][j-1]
    else:
        for k in range(i-1, j):
            tmp += s[k][j-1] - s[k][i-2]
    print(tmp)



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

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

for i, j in y:
    print(table[i-1][j-1])
'''

Submission status: Time Limit Exceeded

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

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

for i, j in x:
    table[i-1][j-1] += 1

s = [[table[i][0]] for i in range(n)]

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

for i, j in y:
    tmp = 0
    if i == 1:
        for k in range(i-1, j):
            tmp += s[k][j-1]
    else:
        for k in range(i-1, j):
            tmp += s[k][j-1] - s[k][i-2]
    print(tmp)



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

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

for i, j in y:
    print(table[i-1][j-1])
'''

Submission status: Time Limit Exceeded

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

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

for i, j in x:
    table[i-1][j-1] += 1

for i, j in y:
    ans = 0
    for s in range(i-1, j):
        for t in range(i-1, j):
            ans += table[s][t]
    print(ans)

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

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

for i, j in y:
    print(table[i-1][j-1])
'''

Submission status: Time Limit Exceeded

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

N = int(N)
M = int(M)
Q = int(Q)

import numpy as np

L_R = np.array([list(map(int, input().split())) for i in range(M)]).reshape(-1,2)

p_q = np.array([list(map(int, input().split())) for i in range(Q)]).reshape(-1,2)

for i in p_q:
    
    p_dis =  L_R[:,:1] - i[0]
    q_dis = (-1)*L_R[:,1:2] + i[1]

    pq_dis_true = np.c_[p_dis, q_dis]

    print(list(np.all(pq_dis_true >= 0, axis = 1)).count(True))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
#横にn個入力
n, m, q = map(int, input().split())
#行列
s = []
for i in range(m):#h:高さ
    s.append([int(m) for m in input().split()] + [i])
# 行列
t = []
for i in range(q):  # h:高さ
    t.append([int(m) for m in input().split()])

lin = []
li0 = []
for i in range(n):
    lin.append(set())
    li0.append(set())
for i in range(m):
    lin[s[i][0] - 1].add(s[i][2])
    li0[s[i][1] - 1].add(s[i][2])
for i in range(n - 1):
    li0[i + 1] = li0[i + 1] | li0[i]
for i in range(n - 1, 0, -1):
    lin[i - 1] = lin[i] | lin[i - 1]
for i in range(q):
    ans = len(lin[t[i][0] - 1] & li0[t[i][1] - 1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
num_city, num_train, num_question = [int(i) for i in input().split()]

trains = []
for i in range(0, num_train):
    trains.append([int(j) for j in input().split()])

answers = []
for i in range(0, num_question):
    question = [int(j) for j in input().split()]

    count = 0
    for train in trains:
        if question[0] <= train[0] and question[1] >= train[1]:
            count += 1
    answers.append(count)

for answer in answers:
    print(answer)

Submission status: Time Limit Exceeded

Solution code:
n,m,Q = map(int,input().split())
LR = []
pon = []
for _ in range(m):
    LR.append(list(map(int,input().split())))
for _ in range(Q):
    p,q = map(int,input().split())
    ans = 0
    for i in range(m):
        if p<=LR[i][0] and LR[i][1] <= q:
            ans += 1
    pon.append(ans)
for i in range(Q):
    print(pon[i])

Submission status: Time Limit Exceeded

Solution code:
n,m,Q = map(int, input().split())
train = []
for i in range(n):
  a = []
  for j in range(n):
    a.append(0)
  train.append(a)
  
for i in range(m):
  l,r = map(int, input().split())
  train[l-1][r-1] += 1

for i in range(n):
  lst = [0,train[i][0]]
  for j in range(1,n):
    lst.append(lst[j]+train[i][j])
  train[i] = lst 
pq = []
for i in range(Q):
  p,q = map(int, input().split())
  ans = 0
  for i in range(p-1,q):
      ans += train[i][q]

  print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m,Q = map(int, input().split())
train = []
for i in range(n):
  a = []
  for j in range(n):
    a.append(0)
  train.append(a)
  
for i in range(m):
  l,r = map(int, input().split())
  train[l-1][r-1] += 1

for i in range(n):
  lst = [train[i][0]]
  for j in range(1,n):
    lst.append(lst[j-1]+train[i][j])
  train[i] = lst 
pq = []
for i in range(Q):
  p,q = map(int, input().split())
  ans = 0
  for i in range(p-1,q):
    if p == 1:
      ans += train[i][q-1]
    else:
      ans += train[i][q-1] - train[i][p-2]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
Town=[[int(i) for i in input().split()] for i in range(M)]
Town.sort(key=lambda x:x[0])

def BS_left(x,L,s):
  L_copy=L[:]
  left=0
  if L[s-1]<x:
    return s-1
  else:
    while s>2:
      if L_copy[s//2]<x:
        L_copy=L_copy[s//2:s]
        left+=s//2
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        s=s//2+1
    if L[left]>=x:
      return left-1
    else:
      return left

def BS_right(x,L,s):
  L_copy=L[:]
  right=s-1
  if L[0]>x:
    return 0
  else:
    while s>2:
      if L_copy[s//2]<=x:
        L_copy=L_copy[s//2:s]
        s=s-s//2
      else:
        L_copy=L_copy[0:s//2+1]
        right+=-s//2+1
        s=s//2+1
    if L[right]<=x:
      return right+1
    else:
      return right

ans=[0]*Q
for i in range(Q):
  p,q=map(int,input().split())
  for i in zip(*Town):
    TownL=i
    break
  a=BS_left(p,TownL,M)+1
  newTown=Town[a:]
  if M-a==0:
    print(0)
  else:
    newTown.sort(key=lambda x:x[1])
    e=0
    for i in zip(*newTown):
      if e==0:
        e+=1
      else:
        TownR=i
        break
    b=BS_right(q,TownR,M-a)
    if b==1 and TownR[0]>q:
      print(0)
    else:
      print(b)

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

C = [[0] * (N+1) for i in range(N+1)]
for i in range(M):
  for j in range(1, LR[i][0]+1):
    for k in range(LR[i][1], N+1):
      C[j][k] += 1
      
for i in range(Q):
  print(C[pq[i][0]][pq[i][1]])