Problem:


Score: 400 points

Problem Statement

In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east.
A company called AtCoder Express possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i).
Takahashi the king is interested in the following Q matters:

The number of the trains that runs strictly within the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.

Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Constraints

N is an integer between 1 and 500 (inclusive).

M is an integer between 1 and 200 \ 000 (inclusive).

Q is an integer between 1 and 100 \ 000 (inclusive).

1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)

1 \leq p_i \leq q_i \leq N (1 \leq i \leq Q)

Input

Input is given from Standard Input in the following format:

N M Q
L_1 R_1
L_2 R_2
:
L_M R_M
p_1 q_1
p_2 q_2
:
p_Q q_Q

Output

Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City p_i to City q_i.

Sample Input 1

2 3 1
1 1
1 2
2 2
1 2

Sample Output 1

3

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.

Sample Input 2

10 3 2
1 5
2 8
7 10
1 7
3 10

Sample Output 2

1
1

The first query is on the section from City 1 to 7. There is only one train that runs strictly within that section: Train 1.
The second query is on the section from City 3 to 10. There is only one train that runs strictly within that section: Train 3.

Sample Input 3

10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10

Sample Output 3

7
9
10
6
8
9
6
7
8
10



Sample input:
2 3 1
1 1
1 2
2 2
1 2


Sample output:
3

Submission status: Time Limit Exceeded

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

N, M, Q = map(int, input().split())
L, R = [], []
X = [[0]*N for _ in range(N)]
for i in range(M):
    l, r = map(int, input().split())
    L.append(l-1)
    R.append(r-1)
    X[l-1][r-1] += 1
C =[[0]*(N+1) for _ in range(N)]
for i in range(N):
    for j in range(N):
        C[i][j+1] = C[i][j] + X[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
L, R = [], []
X = [[0]*N for _ in range(N)]
for i in range(M):
    l, r = map(int, input().split())
    L.append(l-1)
    R.append(r-1)
    X[l-1][r-1] += 1
C =[[0]*(N+1) for _ in range(N)]
for i in range(N):
    for j in range(N):
        C[i][j+1] = C[i][j] + X[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = sys.stdin.readline
N, M, Q = [int(_) for _ in input().split()]

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
N, M, Q = [int(_) for _ in input().split()]

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
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)]
data=[[] for i in range(N+1)]
for l,r in LR:
    data[l].append(r)
for i in range(1,N):
    data[i].sort()
for p,q in PQ:
    count=0
    for i in range(p,q+1):
        count+=bisect_right(data[i],q)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
from bisect import *
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)]
data=[[] for i in range(N+1)]
for l,r in LR:
    data[l].append(r)
data=[sorted(data[i]) for i in range(N+1)]
for p,q in PQ:
    count=0
    for i in range(p,q+1):
        count+=bisect_right(data[i],q)
    print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
line=[[0]*(n+1) for _ in range(n+1)]
for i in range(m):
  l,r=map(int,input().split())
  for j in range(0,l):
    for k in range(r-1,n):
      line[j][k]+=1
for _ in range(q):
  x,y=map(int,input().split())
  print(line[x-1][y-1])

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
def main():
  n,m,q=map(int,input().split())
  x=[[0]*(n+1) for i in range(n+1)]
  c=[[0]*(n+1) for i 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())
    s=0
    for j in range(p,q+1):
      s+=c[j][q]-c[j][p-1]
    print(s)
if __name__=='__main__':
  main()

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
Arr = []
for i in range(n+1):
  Arr.append([0] * (n+1))
for i in range(m):
  l, r = map(int, input().split())
  Arr[l][r] += 1
#print(Arr)

for i in range(q):
  left, right = map(int, input().split())
  train_num = 0
  for j in range(left, right+1):
    for k in range(left, right+1):
      train_num += Arr[j][k]
  print(train_num)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
import numpy as np
Arr = np.zeros((n+1)**2, dtype=np.int).reshape((n+1, n+1))
for i in range(m):
  l, r = map(int, input().split())
  Arr[l][r] += 1
#print(Arr)

for i in range(q):
  left, right = map(int, input().split())
  train_num = np.sum(Arr[left:right+1, left:right+1], axis=None, dtype=np.int)
  print(train_num)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
import numpy as np
Arr = np.zeros((n+1)**2, dtype=np.int).reshape((n+1, n+1))
for i in range(m):
  l, r = map(int, input().split())
  Arr[l][r] += 1
#print(Arr)

A = np.array(Arr)
for i in range(q):
  left, right = map(int, input().split())
  train_num = np.sum(A[left:right+1, left:right+1], axis=None, dtype=np.int)
  print(train_num)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import defaultdict as dd
n, m, q = map(int, input().split())
Tr = []
L2Rs = dd(lambda: [])
for i in range(m):
  l, r = map(int, input().split())
  Tr.append([l, r])
  L2Rs[l] += [r]
Tr.sort(key=lambda x: x[0])
for i in L2Rs.keys():
  L2Rs[i] = sorted(L2Rs[i])
L = sorted(L2Rs.keys())

Sc = []
for i in range(q):
  Sc.append(list(map(int, input().split())))
#Sc.sort(key=lambda x: x[0])
#print(Sc)

for i in range(q):
  left, right = Sc[i]
  l_ok_index = bisect.bisect_left(L, left)
  counter = 0
  for j in range(l_ok_index, len(L)):
    #print(j, L2Rs[j], left, right)
    r_ok = bisect.bisect_right(L2Rs[L[j]], right)
    #print(r_ok)
    counter += r_ok
  print(counter)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import defaultdict as dd
n, m, q = map(int, input().split())
Tr = []
L2Rs = dd(lambda: [])
for i in range(m):
  l, r = map(int, input().split())
  Tr.append([l, r])
  L2Rs[l] += [r]
Tr.sort(key=lambda x: x[0])
for i in L2Rs.keys():
  L2Rs[i] = sorted(L2Rs[i])
L = L2Rs.keys()
  
Sc = []
for i in range(q):
  Sc.append(list(map(int, input().split())))
#Sc.sort(key=lambda x: x[0])
#print(Sc)

for i in range(q):
  left, right = Sc[i]
  counter = 0
  for j in range(left, 500):
    #print(j, L2Rs[j], left, right)
    r_ok = bisect.bisect_right(L2Rs[j], right)
    #print(r_ok)
    counter += r_ok
  print(counter)

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m, q = map(int, input().split())
Tr = []
for i in range(m):
  Tr.append(list(map(int, input().split())))
Tr.sort(key=lambda x: x[0])
Sc = []
L = [x[0] for x in Tr]
R = [x[1] for x in Tr]
for i in range(q):
  Sc.append(list(map(int, input().split())))
#Sc.sort(key=lambda x: x[0])
#print(Sc)

for i in range(q):
  left, right = Sc[i]
  train_l_ok_id = bisect.bisect_left(L, left)
  counter = 0
  for j in range(train_l_ok_id, m):
    if R[j] <= right:
      counter += 1
  print(counter)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = (int(x) for x in input().split())
Ls=[0]*M
Rs=[0]*M
for m in range(M):
    Ls[m],Rs[m] = (int(x) for x in input().split())
ans=[0]*Q
for q in range(Q):
    Ps,Qs = (int(x) for x in input().split())
    for m in range(M):
        if (Ps <= Ls[m]) and (Rs[m] <= Qs):
            ans[q] += 1

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = (int(x) for x in input().split())
Ls=[0]*M
Rs=[0]*M
for m in range(M):
    Ls[m],Rs[m] = (int(x) for x in input().split())
Ps=[0]*Q
Qs=[0]*Q
for q in range(Q):
    Ps[q],Qs[q] = (int(x) for x in input().split())

for q in range(Q):
    ans = 0
    for m in range(M):
        if (Ps[q] <= Ls[m]) and (Rs[m] <= Qs[q]):
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

NN = 18
KK = (1 << (1 << NN)) - 1
I0 = KK // 3
I1 = KK // 5
I2 = KK // 17
I3 = KK // 257
I4 = KK // 65537
def popcount(x):
    x -= (x >> 1) & I0
    x = (x & I1) + ((x >> 2) & I1)
    x = (x + (x >> 4)) & I2
    x = (x + (x >> 8)) & I3
    x = (x + (x >> 16)) & I4
    for k in range(5, 18):
        x += x >> 2**k
    return x & 0x3ffff

N, M, Q = MAP()

# 出発前の列車の集合
S1 = [(1<<M)-1] * (N+1)
# 終着後の列車の集合
S2 = [0] * (N+1)
for i in range(M):
    l, r = MAP()
    l -= 1; r -= 1
    S1[l+1] ^= 1<<i
    S2[r] |= 1<<i
for i in range(1, N+1):
    S1[i] &= S1[i-1]
    S2[i] |= S2[i-1]

for i in range(Q):
    p, q = MAP()
    p -= 1; q -= 1
    pq = S1[p] & S2[q]
    print(popcount(pq))

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

for i in range(M):
    L, R = map(int, input().split())
    LR_plane[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 += LR_plane[j][k]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
LR = []
num = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    l,r = list(map(int,input().split()))
    l -= 1
    r -= 1
    num[l][r] += 1
    LR.append([l,r])
LR.sort()
pq = []
for i in range(Q):
    p,q=list(map(int,input().split()))
    p -= 1
    q -= 1
    ans = 0
    for i in range(N-1,p-1,-1):
        ans += sum(num[i][:q+1])
    print(ans)

Submission status: Time Limit Exceeded

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

from bisect import bisect_right
n,m,q = map(int,input().split())
d = {}
for i in range(m):
    l,r = map(int, input().split())
    if l not in d:
        d[l] = []
    d[l].append(r)

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

for _ in range(q):
    p,q = map(int, input().split())
    c = 0
    for i in range(p,q+1):
        if i not in d:
            continue
        j = bisect_right(d[i], q)
        c += j
        # print(j, '-', d[i])
    print(c)

Submission status: Time Limit Exceeded

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

trains = []

for _ in range(M):
    trains.append(list(map(int,input().split())))

for i in range(Q):
    ans = 0
    L,R = map(int,input().split())
    for li in trains:
        if li[0] >= L and li[1] <=R:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import accumulate
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for _ in range(M)]
PQ = [tuple(map(int, input().split())) for _ in range(Q)]
T = [[0] * (N+1) for _ in range(N)]
for l, r in LR:
    T[l-1][r] += 1
U = [list(accumulate(t)) for t in T]
for p, q in PQ:
    print(sum(u[q]-u[p-1] for u in U[p-1:q]))

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
C = {i:{} for i in range(1,N+1)}
for _ in range(M):
    L,R = map(int,input().split())
    if L not in C[R]:
        C[R][L] = 0
    C[R][L] += 1
for _ in range(Q):
    p,q = map(int,input().split())
    A = {i:0 for i in range(1,N+1)}
    for i in range(1,q+1):
        for a in C[i]:
            A[a] += C[i][a]
    cnt = 0
    for a in range(p,N+1):
        cnt += A[a]
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left
N,M,Q = map(int,input().split())
C = {i:[] for i in range(1,N+1)}
for _ in range(M):
    L,R = map(int,input().split())
    C[R].append(L)
for _ in range(Q):
    p,q = map(int,input().split())
    A = []
    for i in range(1,q+1):
        A += C[i]
    A = sorted(A)
    ind = bisect_left(A,p)
    print(len(A[ind:]))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys
input = sys.stdin.readline
N,M,Q = map(int,input().split())
LR = []
matrix = np.zeros((N,N)).astype('int')
for i in range(M):
    l,r = map(int,input().split())
    matrix[l-1][r-1] += 1
cumsums = []
for i in range(N):
    c = [0]
    for e in matrix[i]:
        c.append(c[-1]+e)
    cumsums.append(c)
for i in range(Q):
    p,q = map(int,input().split())
    p,q = p-1,q-1
    ans = 0
    for j in range(p,q+1):
        ans += cumsums[j][q+1]-cumsums[j][p]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M,Q = map(int,input().split())
LR = []
matrix = np.zeros((N,N)).astype('int')
for i in range(M):
    l,r = map(int,input().split())
    matrix[l-1][r-1] += 1
cumsums = []
for i in range(N):
    c = [0]
    for e in matrix[i]:
        c.append(c[-1]+e)
    cumsums.append(c)
for i in range(Q):
    p,q = map(int,input().split())
    p,q = p-1,q-1
    ans = 0
    for j in range(p,q+1):
        ans += cumsums[j][q+1]-cumsums[j][p]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M,Q = map(int,input().split())
LR = []
matrix = np.zeros((N,N)).astype('int')
for i in range(M):
    l,r = map(int,input().split())
    matrix[l-1][r-1] += 1
for i in range(Q):
    p,q = map(int,input().split())
    print(np.sum(matrix[p-1:q,p-1:q]))

Submission status: Time Limit Exceeded

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

def main():
    N,M,Q = map(int,input().split())
    go = [[0 for _ in range(N)] for i in range(N)]
    for _ in range(M):
        L,R = map(int,input().split())
        go[L-1][R-1] += 1
        
    qu = []
    for _ in range(Q):
        p,q = map(int,input().split())
        qu.append((p-1,q-1))
        
    num = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        num[i][0] = go[i][0]
    for i in range(N):
        for j in range(N-1):
            num[i][j+1] = num[i][j] + go[i][j+1]
            
    for i in range(Q):
        ans = 0
        p,q = qu[i]
        for j in range(p,q+1):
            ans += num[j][q]
        print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

for i in range(Q):
    p, q = map(int, input().split())
    count = 0
    for L_R in L_R_list:
        if p<=L_R[0] and L_R[1]<= q:
            count+=1
    print(count)

Submission status: Time Limit Exceeded

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

for p_q in p_q_list:
    count = 0
    for L_R in L_R_list:
        if p_q[0]<=L_R[0] and L_R[1]<= p_q[1]:
            count+=1
    print(count)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
import numpy as np
trains=np.zeros((N+1,N+1),dtype=int)
for i in range(M):
  l,r=map(int,input().split())
  trains[l][r]+=1
  
np.cumsum(trains,axis=1,out=trains)
np.cumsum(trains,axis=0,out=trains)

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
import numpy as np
trains=np.zeros((N+1,N+1),dtype=int)
for i in range(M):
  l,r=map(int,input().split())
  trains[l][r]+=1
  
np.cumsum(trains,axis=0,out=trains)
np.cumsum(trains,axis=1,out=trains)

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
import numpy as np
trains=np.zeros((N+1,N+1),dtype=int)
for i in range(M):
  l,r=map(int,input().split())
  trains[l][r]+=1
  
trains=np.cumsum(trains,axis=0)
trains=np.cumsum(trains,axis=1)

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q=map(int,input().split())
import numpy as np
trains=np.zeros((N+1,N+1),dtype=int)
for i in range(M):
  l,r=map(int,input().split())
  trains[l][r]+=1
  
trains=np.cumsum(trains,axis=0)
trains=np.cumsum(trains,axis=1)

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

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

def bit_count(i):

    return bin(i).count('1')

N, M, Q = MAP()

# 出発前の列車の集合
S1 = [(1<<M)-1] * (N+1)
# 終着後の列車の集合
S2 = [0] * (N+1)
for i in range(M):
    l, r = MAP()
    l -= 1; r -= 1
    S1[l+1] ^= 1<<i
    S2[r] |= 1<<i
for i in range(1, N+1):
    S1[i] &= S1[i-1]
    S2[i] ^= S2[i-1]

for i in range(Q):
    p, q = MAP()
    p -= 1; q -= 1
    pq = S1[p] & S2[q]
    print(bit_count(pq))

Submission status: Time Limit Exceeded

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

def search(l,r):
    ans = 0
    for i in range(l,r+1):
        for j in range(l,r+1):
            ans += query[i][j]
    return ans

for h in range(q):
    k,l = map(int,input().split())
    print(search(k,l))

Submission status: Time Limit Exceeded

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

query = np.zeros((501,501),dtype=int)

for k,l in list_lr:
    query[k][l] += 1

def search(l,r):
    ans = 0
    for i in range(l,r+1):
        for j in range(l,r+1):
            ans += query[i][j]
    return ans

for k,m in list_pq:
    print(search(k,m))

Submission status: Time Limit Exceeded

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


n, m, q = map(int, input().split())
start_ok = [set() for _ in range(n)]
end_ok = [set() for _ in range(n)]

for i in range(m):
    start, end = map(int, input().split())
    for x in range(start):
        start_ok[x].add(i)
    for y in range(end-1, n):
        end_ok[y].add(i)

for _ in range(q):
    left, right = map(int, input().split())
    possible = start_ok[left-1] & end_ok[right-1]
    print(len(possible))

Submission status: Time Limit Exceeded

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


n, m, q = map(int, input().split())
train = defaultdict(list)
for _ in range(m):
    start, end = map(int, input().split())
    train[start].append(end)

for num in range(n):
    train[num].sort()

for _ in range(q):
    left, right = map(int, input().split())
    count = 0
    for num in range(left, right+1):
        candidate = train[num]
        possible = bisect.bisect_right(candidate, right)
        count += possible
    print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def solve(N, M, Q, L, R, p, q):
    A = np.zeros((N+2, N+2), dtype=int)
    S = np.zeros((N+2, N+2), dtype=int)
    for i in range(M):
        A[L[i], R[i]] += 1
    S[0,0] = A[0,0]
    for i in range(1, N+1):
        S[i,:] = S[i-1,:] + A[i,:]
    res = []
    D = {}
    for i in range(Q):
        x1, x2 = p[i], q[i]
        if not (x1, x2) in D:
            a = sum(S[p[i]-1,p[i]:q[i]+1])
            b = sum(S[q[i],  p[i]:q[i]+1])
            D[x1, x2] = b - a
        res.append(D[x1, x2])
    return "\n".join(map(str, res))

N, M, Q = map(int, input().split())
L, R = [0]*M, [0]*M
for i in range(M):
    L[i], R[i] = map(int, input().split())
p, q = [0]*Q, [0]*Q
for i in range(Q):
    p[i], q[i] = map(int, input().split())
print(solve(N, M, Q, L, R, p, q))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def solve(N, M, Q, L, R, p, q):
    A = np.zeros((N+2, N+2), dtype=int)
    S = np.zeros((N+2, N+2), dtype=int)
    for i in range(M):
        A[L[i], R[i]] += 1
    S[0,0] = A[0,0]
    for i in range(1, N+1):
        for j in range(1, N+1):
            S[i,:] = S[i-1,:] + A[i,:]
    res = []
    D = {}
    for i in range(Q):
        x1, x2 = p[i], q[i]
        if not (x1, x2) in D:
            a = sum(S[p[i]-1,p[i]:q[i]+1])
            b = sum(S[q[i],p[i]:q[i]+1])
            D[x1, x2] = b - a
        res.append(D[x1, x2])
    return "\n".join(map(str, res))

N, M, Q = map(int, input().split())
L, R = [0]*M, [0]*M
for i in range(M):
    L[i], R[i] = map(int, input().split())
p, q = [0]*Q, [0]*Q
for i in range(Q):
    p[i], q[i] = map(int, input().split())
print(solve(N, M, Q, L, R, p, q))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def solve(N, M, Q, L, R, p, q):
    A = np.zeros((N+2, N+2), dtype=int)
    S = np.zeros((N+2, N+2), dtype=int)
    for i in range(M):
        A[L[i], R[i]] += 1
    S[0,0] = A[0,0]
    for i in range(1, N+1):
        for j in range(1, N+1):
            S[i,:] = S[i-1,:] + A[i,:]
    res = []
    for i in range(Q):
        a = sum(S[p[i]-1,p[i]:q[i]+1])
        b = sum(S[q[i],p[i]:q[i]+1])
        c = b - a
        res.append(c)
    return "\n".join(map(str, res))

N, M, Q = map(int, input().split())
L, R = [0]*M, [0]*M
for i in range(M):
    L[i], R[i] = map(int, input().split())
p, q = [0]*Q, [0]*Q
for i in range(Q):
    p[i], q[i] = map(int, input().split())
print(solve(N, M, Q, L, R, p, q))

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
D=[]
for i in range(M):
  l,r = map(int,input().split())
  D += [[l,r]]
for i in range(Q):
  ql,qr = map(int,input().split())
  count=0
  for j in range(M):
    if ql<=D[j][0] and D[j][1]<=qr:
      count +=1
  print(count)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N,M,Q = map(int,input().split())
lis = np.zeros((N,N))
for i in range(M):
    L,R = map(int,input().split())
    lis[0:L,R-1:] += 1
for i in range(Q):
    p,q = map(int,input().split())
    print(int(lis[p-1,q-1]))

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = [int(i) for i in input().split()]
LR = [[int(i) for i in input().split()] for _ in range(M)]
QList = [[int(i) for i in input().split()] for _ in range(Q)]
count = {i:0 for i in range(1,Q+1)}
qnum = 0

for ql,qr in QList:
    qnum += 1
    for l,r in LR:
        if ql <= l and r <= qr:
            count[qnum] += 1
for i in count.values():
    print(i)

Submission status: Time Limit Exceeded

Solution code:
import collections
import bisect
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]
LR.sort(key=lambda x: x[1])

table = collections.defaultdict(list)
for L, R in LR:
    table[L].append(R)

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

Submission status: Time Limit Exceeded

Solution code:
import collections
import bisect
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]


table = collections.defaultdict(list)
for L, R in LR:
    table[L].append(R)

for x in table:
    table[x].sort()

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

Submission status: Time Limit Exceeded

Solution code:
import collections
import bisect
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]


table = collections.defaultdict(list)
for L, R in LR:
    table[L].append(R)

for x in table:
    table[x].sort()

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

Submission status: Time Limit Exceeded

Solution code:
import collections
import bisect
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]


table = collections.defaultdict(list)
for L, R in LR:
    table[L].append(R)

for x in table:
    table[x].sort()

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
dp = np.zeros((N,N), dtype=np.int32)
for i in range(M):
  l, r = map(int, input().split())
  dp[r-1][l-1] += 1
for i in range(N):
  dp[i] = np.flipud(np.cumsum(np.flipud(dp[i])))
for i in range(N-1):
  dp[i+1] += dp[i]
for i in range(Q):
  p, q = map(int, input().split())
  print(dp[q-1][p-1])

Submission status: Time Limit Exceeded

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


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    matrix = [[0]*(N+1) for _ in range(N+1)]

    for i in range(M):
        matrix[L[i]][R[i]] += 1

    for j in range(Q):
        answer = 0
        for k in range(p[j],q[j]+1): 
            for l in range(p[j],q[j]+1):
                answer += matrix[k][l]
        print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
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)