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())
g=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    g[a][b]+=1
r=[[0 for i in range(n+1)] for j in range(n)]
for i in range(n):
    for j in range(1,n+1):
        r[i][j]=r[i][j-1]+g[i][j-1]
for i in range(q):
    a,b=map(int,input().split())
    a-=1
    b-=1
    ans=0
    for i in range(a,b+1):
        ans+=r[i][b+1]-r[i][a]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
from sys import stdin

N, M, Q = map(int, input().split())
data = [[0] * (N+1) for _ in range(N+1)]
for i in range(M):
    L, R = map(int, input().split())
    data[L][R] += 1
for i in range(N+1):
    for j in range(N):
        data[i][j+1] += data[i][j]
for i in range(Q):
    p, q = map(int, input().split())
    answer = 0
    for j in range(p, q+1):
        answer += data[j][q] - data[j][p-1]
    print(answer)

Submission status: Time Limit Exceeded

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

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

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


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

Submission status: Time Limit Exceeded

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

lrl = []
for _ in range(m):
    l,r = map(int,input().split())
    lrl.append((l,r))
    
lrl = sorted(lrl)

import bisect

for _ in range(Q):
    ans = 0
    p,q = map(int,input().split())
    lidx = bisect.bisect_left(lrl, (p,p))
    ridx = bisect.bisect_right(lrl, (q,q))
    new_lrl = lrl[lidx:ridx]
    print(len([i[1] for i in new_lrl if i[1] <= q]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

LR = np.zeros(shape=(N + 1, N + 1), dtype=np.int32)
for _ in range(M):
    L, R = map(int, input().split())
    LR[L, R] += 1

np.cumsum(LR, axis=0, out=LR)
np.cumsum(LR, axis=1, out=LR)

P, Q = np.array([list(map(int, input().split())) for _ in range(K)], dtype=np.int32).T

P -= 1
ans = LR[Q, Q] - LR[P, Q] - LR[Q, P] + LR[P, P]
print(*ans, sep='\n')

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
m, n, q = map(int, input().split())
train_lis = []
city_lis = []
for i in range(n):
    train_lis.append(list(map(int, input().split())))
for i in range(q):
    city_lis.append(list(map(int, input().split())))
train_arr = np.array(train_lis)
city_arr = np.array(city_lis)
for i in range(q):
    print(sum(np.logical_and(train_arr[:, 0]>= city_lis[i][0], train_arr[:, 1]<= city_lis[i][1])))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M, Q = map(int,input().split())
l=np.zeros(M)
r=np.zeros(M)
p=np.zeros(Q)
q=np.zeros(Q)
ans = np.zeros(Q)

for j in range(M):
    l[j], r[j] = map(int,input().split())
for i in range(Q):
    p[i], q[i] = map(int,input().split()) 
    ans[i]=((p[i]<=l)*(r<=q[i])).sum()
for i in range(Q):
    print(int(ans[i]))

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
tracks = [[] for i in range(N)]
for i in range(M):
    L, R = map(int, input().split())
    tracks[L-1].append(R-1)
    
for track in tracks: track.sort()

ans = [[None for j in range(N)] for i in range(N)]
for L in range(N):
    cur = 0
    tot = 0
    for R in range(L, N):
        while cur < len(tracks[L]) and tracks[L][cur] <= R:
            cur += 1
            tot += 1
        ans[L][R] = tot

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import bisect
from operator import itemgetter
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)]
LR.sort(key=itemgetter(0))
LR = np.array(LR)
#print(LR)
#print(PQ)
for i in range(Q):
  ans = 0
  key = bisect.bisect_left(LR[:,0],PQ[i][0])
  ans += np.sum(LR[key:] <= PQ[i][1], axis = 0)[1]
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
# D - AtCoder Express 2

import numpy as np

N, M, Q = map(int, input().split())
L, R, = [], []
p, q = np.array([],np.int64), np.array([],np.int64)
for _ in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p = np.append(p, [tmp_p])
    q = np.append(q, [tmp_q])
    
train = np.zeros((N+1, N+1))
np.add.at(train, (L,R), 1)

np.cumsum(train, axis = 0, out = train)
np.cumsum(train, axis = 1, out = train)

p -= 1
ans = train[q,q] - train[p,q] - train[q,p] + train[p,p]
for i in range(Q):
    print(int(ans[i]))

Submission status: Time Limit Exceeded

Solution code:
# D - AtCoder Express 2

import numpy as np

N, M, Q = map(int, input().split())
L, R, = [], []
p, q = np.array([],np.int64), np.array([],np.int64)
for _ in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p = np.append(p, [tmp_p])
    q = np.append(q, [tmp_q])
    
train = np.zeros((N+1, N+1))
np.add.at(train, (L,R), 1)

np.cumsum(train, axis = 0, out = train)
np.cumsum(train, axis = 1, out = train)
    
ans = train[q,q] - train[p-1,q] - train[q,p-1] + train[p-1,p-1]
for i in range(Q):
    print(int(ans[i]))

Submission status: Time Limit Exceeded

Solution code:
# D - AtCoder Express 2

import numpy as np

N, M, Q = map(int, input().split())
LR = np.zeros((N+1, N+1))

for _ in range(M):
    l, r = map(int, input().split())
    np.add.at(LR, (l,r), 1)

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

Submission status: Time Limit Exceeded

Solution code:
# D - AtCoder Express 2

import bisect, copy

N, M, Q = map(int, input().split())
LRidx = [list(map(int, input().split())) + [i] for i in range(M)]
p, q = [], []
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p.append(tmp_p)
    q.append(tmp_q)

# l,rはそれぞれ高々500通りなので、l,rの値に対して探索結果をメモしておく
LRidx = sorted(LRidx, key = lambda x: x[0])
tmp_L = [LRidx[idx][0] for idx in range(M)]
l_memo = [[-1] for _ in range(N+1)]
l_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if l_memo[p[i]] and l_memo[p[i]][0] == -1:
        b_idx = bisect.bisect_left(tmp_L, p[i])
        tmp = [LRidx[j][2] for j in range(b_idx, M)]
        l_ok_idx[i] = tmp.copy()
        l_memo[p[i]] = tmp.copy()
    else:
        l_ok_idx[i] = l_memo[p[i]].copy()
    
LRidx = sorted(LRidx, key = lambda x: x[1])
tmp_R = [LRidx[idx][1] for idx in range(M)]
r_memo = [[-1] for _ in range(N+1)]
r_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if l_ok_idx[i] and r_memo[q[i]] and r_memo[q[i]][0] == -1:
        b_idx = bisect.bisect_right(tmp_R, q[i])
        tmp = [LRidx[j][2] for j in range(b_idx)]
        r_ok_idx[i] = tmp.copy()
        r_memo[q[i]] = tmp.copy()
    else:
        r_ok_idx[i] = r_memo[q[i]].copy()
    
for i in range(Q):
    print(len(set(l_ok_idx[i]) & set(r_ok_idx[i])))

Submission status: Time Limit Exceeded

Solution code:
# D - AtCoder Express 2

import bisect, copy

N, M, Q = map(int, input().split())
LRidx = [list(map(int, input().split())) + [i] for i in range(M)]
p, q = [], []
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p.append(tmp_p)
    q.append(tmp_q)

# l,rはそれぞれ高々500通りなので、l,rの値に対して探索結果をメモしておく
LRidx = sorted(LRidx, key = lambda x: x[0])
tmp_L = [LRidx[idx][0] for idx in range(M)]
l_memo = [[-1] for _ in range(N+1)]
l_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if l_memo[p[i]] and l_memo[p[i]][0] == -1:
        b_idx = bisect.bisect_left(tmp_L, p[i])
        tmp = [LRidx[j][2] for j in range(b_idx, M)]
        l_ok_idx[i] = copy.deepcopy(tmp)
        l_memo[p[i]] = copy.deepcopy(tmp)
    else:
        l_ok_idx[i] = copy.deepcopy(l_memo[p[i]])
    
LRidx = sorted(LRidx, key = lambda x: x[1])
tmp_R = [LRidx[idx][1] for idx in range(M)]
r_memo = [[-1] for _ in range(N+1)]
r_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if l_ok_idx[i] and r_memo[q[i]] and r_memo[q[i]][0] == -1:
        b_idx = bisect.bisect_right(tmp_R, q[i])
        tmp = [LRidx[j][2] for j in range(b_idx)]
        r_ok_idx[i] = copy.deepcopy(tmp)
        r_memo[q[i]] = copy.deepcopy(tmp)
    else:
        r_ok_idx[i] = copy.deepcopy(r_memo[q[i]])
    
for i in range(Q):
    print(len(set(l_ok_idx[i]) & set(r_ok_idx[i])))

Submission status: Time Limit Exceeded

Solution code:
# D - AtCoder Express 2

import bisect, copy

N, M, Q = map(int, input().split())
LRidx = [list(map(int, input().split())) + [i] for i in range(M)]
p, q = [], []
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p.append(tmp_p)
    q.append(tmp_q)

# l,rはそれぞれ高々500通りなので、l,rの値に対して探索結果をメモしておく
LRidx = sorted(LRidx, key = lambda x: x[0])
tmp_L = [LRidx[idx][0] for idx in range(M)]
l_memo = [[-1] for _ in range(N+1)]
l_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if l_memo[p[i]] and l_memo[p[i]][0] == -1:
        b_idx = bisect.bisect_left(tmp_L, p[i])
        try:
            tmp = [LRidx[j][2] for j in range(b_idx, M)]
            l_ok_idx[i] = copy.deepcopy(tmp)
            l_memo[p[i]] = copy.deepcopy(tmp)
        except:
            pass
    else:
        l_ok_idx[i] = copy.deepcopy(l_memo[p[i]])
    
LRidx = sorted(LRidx, key = lambda x: x[1])
tmp_R = [LRidx[idx][1] for idx in range(M)]
r_memo = [[-1] for _ in range(N+1)]
r_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if r_memo[q[i]] and r_memo[q[i]][0] == -1:
        b_idx = bisect.bisect_right(tmp_R, q[i])
        tmp = [LRidx[j][2] for j in range(b_idx)]
        r_ok_idx[i] = copy.deepcopy(tmp)
        r_memo[q[i]] = copy.deepcopy(tmp)
    else:
        r_ok_idx[i] = copy.deepcopy(r_memo[q[i]])
    
for i in range(Q):
    print(len(set(l_ok_idx[i]) & set(r_ok_idx[i])))

Submission status: Time Limit Exceeded

Solution code:
# D - AtCoder Express 2

import bisect

N, M, Q = map(int, input().split())
LRidx = [list(map(int, input().split())) + [i] for i in range(M)]
p, q = [], []
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p.append(tmp_p)
    q.append(tmp_q)
    
LRidx = sorted(LRidx, key = lambda x: x[0])
tmp_L = [LRidx[idx][0] for idx in range(M)]
l_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    try:
        for j in range(bisect.bisect_left(tmp_L, p[i]), M):
            l_ok_idx[i].append(LRidx[j][2])
    except:
        pass
    
LRidx = sorted(LRidx, key = lambda x: x[1])
tmp_R = [LRidx[idx][1] for idx in range(M)]
r_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if bisect.bisect_right(tmp_L, p[i]) > 0:
        for j in range(bisect.bisect_right(tmp_R, q[i])):
            r_ok_idx[i].append(LRidx[j][2])
    
for i in range(Q):
    print(len(set(l_ok_idx[i]) & set(r_ok_idx[i])))

Submission status: Time Limit Exceeded

Solution code:

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

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

    LR = [list(map(int, input().split())) for _ in range(M)]
    query = [tuple(map(int, input().split())) for _ in range(Q)]

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

    """
    C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
    C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
    """
    C =  [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = C[i][j-1] + X[i][j]


    """
    print("---------------")
    for a in C:
        print(a)
    """

    for p,q in query:
        cnt = 0
        for r in range(p-1,q):
            cnt += C[r][q-1]
        print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

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

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

    query = [tuple(map(int, input().split())) for _ in range(Q)]

    """
    C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
    C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
    """
    C =  [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            C[i][j] = C[i][j-1] + X[i][j]


    """
    print("---------------")
    for a in C:
        print(a)
    """

    for p,q in query:
        cnt = 0
        for r in range(p-1,q):
            cnt += C[r][q-1]
        print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:

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

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

    query = [tuple(map(int, input().split())) for _ in range(Q)]

    """
    C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
    C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
    """
    C =  [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        for j in range(N):
            if X[i][j] != 0:
                #if j == i
                C[i][j] = C[i][j-1] + X[i][j]
            else:
                C[i][j] = C[i][j-1]

    """
    print("---------------")
    for a in C:
        print(a)
    """

    for p,q in query:
        cnt = 0
        for r in range(p-1,q):
            cnt += C[r][q-1]
        print(cnt)


if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

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

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

query = [tuple(map(int, input().split())) for _ in range(Q)]

"""
C[i][j]：iから出発してjまで（ｊを含む）のどこかに行くもの
C[i][j] = X[i][i] + X[i][i+1] + ... + X[i][j-1] + X[i][j]
"""
C =  [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(N):
        if X[i][j] != 0:
            #if j == i
            C[i][j] = C[i][j-1] + X[i][j]
        else:
            C[i][j] = C[i][j-1]
            
"""
print("---------------")
for a in C:
    print(a)
"""

for p,q in query:
    cnt = 0
    for r in range(p-1,q):
        cnt += C[r][q-1]
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
L=[]
P=[]
for i in range(m):
    l,r=map(int,input().split())
    L.append([l,r])

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

for i in P:
    a=0
    for j in L:
        if i[0] <= j[0] and i[1] >= j[1]:
            a+=1
    print(a)

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

a=list()

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

for i in range(q):
  l,r=map(int,input().split())
  t = 0
  for j in range(l,r+1):
    t += s[j][r]-s[j][l-1]
  a.append(t)

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

Submission status: Time Limit Exceeded

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

a=list()

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

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

for i in range(q):
  l,r=map(int,input().split())
  a.append(s[l][r])

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

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)]
a=list()

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

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

for i in range(q):
  l,r=map(int,input().split())
  t = 0
  for j in range(l,r+1):
    t += s[j][r]-s[j][l-1]
  a.append(t)

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

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

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

for i in range(n+1):
  s[i].sort()

for i in range(q):
  t=0
  l,r=map(int,input().split())
  for i in range(l,r+1):
    t += bisect.bisect_right(s[i],r)
  a.append(t)

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

Submission status: Time Limit Exceeded

Solution code:
#106d
N,M,Q = map(int, input().split()) # N:500

#500C2 = 124750 通り

#同じ範囲を計算することになる→メモる!

L_list=[]
R_list=[]
L_list_append = L_list.append
R_list_append = R_list.append

for i in range(M):
    L,R = map(int, input().split())
    L_list_append(L)
    R_list_append(R)


for _ in range(Q): #10**5
    p,q = map(int, input().split())
    ans = 0
    for j in range(M): #2*10**5
        if p<= L_list[j] and R_list[j] <= q:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

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

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

LR = [[] for _ in range(N)]
for _ in range(M) :
    L, R = map(int, input().split())
    LR[L-1].append(R-1)
for i in range(N) :
    LR[i].sort()

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M,Q = map(int,input().split())
vote = np.array([[0 for _ in range(N)] for _ in range(N)])
for i in range(M):
    l,r = map(int,input().split())
    vote[:l,r-1:] += 1
for i in range(Q):
    p,q = map(int,input().split())
    print(vote[p-1][q-1])

Submission status: Time Limit Exceeded

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

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

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

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

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, radians
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7


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

	x = [[0]*N for _ in range(N)]
	for L, R in LR:
		x[L-1][R-1] += 1

	pq = [LIST() for _ in range(Q)]

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

	for i in range(N):
		tmp = 0
		C[i] = list(accumulate(x[i]))

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

if __name__ == "__main__":
	main()

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, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect

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()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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

x = [[0]*N for _ in range(N)]
for L, R in LR:
	x[L-1][R-1] += 1

pq = [LIST() for _ in range(Q)]

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

for i in range(N):
	tmp = 0
	for j in range(N):
		tmp += x[i][j]
		C[i][j] = tmp

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

Submission status: Time Limit Exceeded

Solution code:
import itertools
import sys

input = sys.stdin.readline

n, m, q = map(int, input().split())
ls = [[0] * n for _ in range(n)]
for _ in range(m):
    l, r = map(int, input().split())
    ls[l - 1][r - l] += 1
for i in range(n):
    ls[i] = list(itertools.accumulate(ls[i]))
for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    res = 0
    for i in range(min(r - l + 1, n - l)):
        res += ls[l + i][r - l - i]
    print(res)

Submission status: Time Limit Exceeded

Solution code:
import bisect
import sys

input = sys.stdin.readline

n, m, q = map(int, input().split())
ls = [[] for _ in range(n)]
for _ in range(m):
    l, r = map(int, input().split())
    ls[l - 1].append(r - l)
for i in range(n):
    ls[i].sort()
for _ in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    res = 0
    for i in range(min(r - l + 1, n - l)):
        res += bisect.bisect(ls[l + i], r - l - i)
    print(res)

Submission status: Time Limit Exceeded

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

for i in range(q):
    question = list(map(int, input().split()))
    count = 0
    for k in train:
        if question[0] <= k[0] and question[1] >= k[1]:
            count += 1

    print(count)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    print((a-1)*(b-1))
    return

#B
def B():
    def est(n):
        res = 0
        for i in range(1, int(n ** 0.5) + 1):
            if not n % i:
                res += 2
        res -= float.is_integer(n ** 0.5)
        return res == 8
    n = II()
    ans = 0
    for i in range(1, n + 1, 2):
        ans += est(i)
    print(ans)
    return

#C
def C():
    s = S()
    k = II()
    for i in range(k):
        if s[i] != "1":
            print(s[i])
            return
    print(s[k-1])
    return

# D
# 解説AC
# 始点と終点を2次元座標に落とし込むことで解ける
# 難しい
def D():
    n, m, q = LI()
    c = [[0] * n for i in range(n)]
    for _ in range(m):
        l, r = LI_()
        c[l][r] += 1
    for _ in range(q):
        p, q = LI_()
        ans = 0
        for pi in range(p, q + 1):
            cpi = c[pi]
            for qi in range(p, q + 1):
                ans += cpi[qi]
        print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
import itertools
sys.setrecursionlimit(10**5)
stdin = sys.stdin
bisect_left = bisect.bisect_left
bisect_right = bisect.bisect_right
def LI(): return list(map(int, stdin.readline().split()))
def LF(): return list(map(float, stdin.readline().split()))
def LI_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def II(): return int(stdin.readline())
def IF(): return float(stdin.readline())
def LS(): return list(map(list, stdin.readline().split()))
def S(): return list(stdin.readline().rstrip())
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#A
def A():
    a, b = LI()
    print((a-1)*(b-1))
    return

#B
def B():
    def est(n):
        res = 0
        for i in range(1, int(n ** 0.5) + 1):
            if not n % i:
                res += 2
        res -= float.is_integer(n ** 0.5)
        return res == 8
    n = II()
    ans = 0
    for i in range(1, n + 1, 2):
        ans += est(i)
    print(ans)
    return

#C
def C():
    s = S()
    k = II()
    for i in range(k):
        if s[i] != "1":
            print(s[i])
            return
    print(s[k-1])
    return

# D
# 解説AC
# 始点と終点を2次元座標に落とし込むことで解ける
# 難しい
def D():
    n, m, q = LI()
    c = [[0] * n for i in range(n)]
    for _ in range(m):
        l, r = LI_()
        c[l][r] += 1
    for _ in range(q):
        p, q = LI_()
        ans = 0
        for pi in range(p, q + 1):
            for qi in range(p, q + 1):
                ans += c[pi][qi]
        print(ans)
    return

#Solve
if __name__ == '__main__':
    D()

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
slst = []
elst = []
for i in range(M):
    a, b = map(int, input().split())
    slst.append(a)
    elst.append(b)

question = []
for k in range(Q):
    cnt = 0
    c, d = map(int, input().split())
    cnt = 0    
    for i, j in zip(slst, elst):
        if i >= c and j<= d:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
slst = []
elst = []
for i in range(M):
    a, b = map(int, input().split())
    slst.append(a)
    elst.append(b)

question = []
for j in range(Q):
    c, d = map(int, input().split())
    question.append([c, d])

for x in question:
    cnt = 0    
    for i, j in zip(slst, elst):
        if i >= x[0] and j<= x[1]:
            cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M,Q = map(int,input().split())
I = {}
for _ in range(M):
    L,R = map(int,input().split())
    if L not in I:
        I[L] = []
    bisect.insort_right(I[L],R)
for x in I:
  I[x] = sorted(I[x])
A = sorted(list(I.keys()))
for _ in range(Q):
    p,q = map(int,input().split())
    indL = bisect.bisect_left(A,p)
    indR = bisect.bisect_right(A,q)
    cnt = 0
    for i in range(indL,indR):
        a = A[i]
        ind = bisect.bisect_right(I[a],q)
        cnt += ind
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M,Q = map(int,input().split())
I = {}
for _ in range(M):
    L,R = map(int,input().split())
    if L not in I:
        I[L] = []
    I[L].append(R)
for x in I:
  I[x] = sorted(I[x])
A = sorted(list(I.keys()))
for _ in range(Q):
    p,q = map(int,input().split())
    indL = bisect.bisect_left(A,p)
    indR = bisect.bisect_right(A,q)
    cnt = 0
    for i in range(indL,indR):
        a = A[i]
        ind = bisect.bisect_right(I[a],q)
        cnt += ind
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M,Q = map(int,input().split())
I = {}
for _ in range(M):
    L,R = map(int,input().split())
    if L not in I:
        I[L] = []
    I[L].append(R)
A = sorted(list(I.keys()))
for _ in range(Q):
    p,q = map(int,input().split())
    indL = bisect.bisect_left(A,p)
    indR = bisect.bisect_right(A,q)
    cnt = 0
    for i in range(indL,indR):
        for y in I[A[i]]:
            if y<=q:
                cnt += 1
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int, input().split())
ml = []
ql = []
for i in range(m):
  tmp = input().split()
  ml.append([int(j) for j in tmp])
for i in range(q):
  tmp = input().split()
  ql.append([int(j) for j in tmp])
  
for i in range(q):
  out = 0
  for j in range(m):
    if ql[i][0] <= ml[j][0] and ml[j][1] <= ql[i][1]:
      out += 1
  print(out)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
line=sorted([list(map(int,input().split())) for i in range(m)])
question=[tuple(map(int,input().split())) for j in range(q)]
dis={}
for i in range(1,n+1):
    for j in range(1,n+1):
        dis[(i,j)]=0
        for x,y in line[i-1:]:
            if i<=x and y<=j:
                dis[(i,j)] +=1

for i in question:
    print(dis[i])

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
line=sorted([list(map(int,input().split())) for i in range(m)])
question=[tuple(map(int,input().split())) for j in range(q)]
dis={}
for i in range(1,n+1):
    for j in range(1,n+1):
        dis[(i,j)]=0
        for x,y in line:
            if i<=x and y<=j:
                dis[(i,j)] +=1

for i in question:
    print(dis[i])