Problem:


Score: 400 points

Problem Statement

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

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

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

Constraints

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

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

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

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

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

Input

Input is given from Standard Input in the following format:

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

Output

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

Sample Input 1

2 3 1
1 1
1 2
2 2
1 2

Sample Output 1

3

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

Sample Input 2

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

Sample Output 2

1
1

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

Sample Input 3

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

Sample Output 3

7
9
10
6
8
9
6
7
8
10



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


Sample output:
3

Submission status: Time Limit Exceeded

Solution code:
import bisect
n, m, q = map(int, input().split())
edges = []
for i in range(m):
    L, R = map(int, input().split())
    edges.append((L, R, i))

L_sorted = sorted(edges)
L_sorted_bi = [L for L, R, i in L_sorted]
L_cum_set = [set()for _ in range(m+1)]
for i in reversed(range(m)):
    L_cum_set[i] = L_cum_set[i+1] | {L_sorted[i][2]}


R_sorted = sorted(edges, key=lambda x: x[1])
R_sorted_bi = [R for L, R, i in R_sorted]
R_cum_set = [set()for _ in range(m+1)]
for i in range(m):
    R_cum_set[i+1] = R_cum_set[i] | {R_sorted[i][2]}


for _ in range(q):
    p, q = map(int, input().split())
    idx = bisect.bisect_left(L_sorted_bi, p)
    s = L_cum_set[idx]

    idx = bisect.bisect_left(R_sorted_bi, q+1)
    t = R_cum_set[idx]
    print(len(s & t))

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from itertools import permutations, accumulate, combinations, combinations_with_replacement
from math import sqrt, ceil, floor, factorial
from bisect import bisect_left, bisect_right, insort_left, insort_right
from copy import deepcopy
from operator import itemgetter
from functools import reduce
from fractions import gcd
import sys
def input(): return sys.stdin.readline().rstrip()
def I(): return int(input())
def Is(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def TI(): return tuple(map(int, input().split()))
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def TIR(n): return [TI() for _ in range(n)]
def S(): return input()
def Ss(): return input().split()
def LS(): return list(input())
def SR(n): return [S() for _ in range(n)]
def SsR(n): return [Ss() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
sys.setrecursionlimit(10**6)
MOD = 10**9+7
INF = 10**18
# ----------------------------------------------------------- #

n, m, q = Is()
LR = TIR(m)
PQ = TIR(q)
LR.sort(key=itemgetter(0, 1))
for p, q in PQ:
    A = LR[bisect_left([l for l, r in LR], p):]
    A.sort(key=itemgetter(1))
    B = A[:bisect_right([r for l, r in A], q)]
    print(len(B))

Submission status: Time Limit Exceeded

Solution code:
def main():
    from sys import stdin
    readline = stdin.readline

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

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

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

    result = []
    for _ in range(Q):
        p, q = map(int, readline().split())
        result.append(sum(t[i][q] - t[i][i - 1] for i in range(p, q + 1)))
    print('\n'.join(str(v) for v in result))


main()

Submission status: Time Limit Exceeded

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

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

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

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

result = []
for _ in range(Q):
    p, q = map(int, readline().split())
    result.append(sum(t[i][q] - t[i][i - 1] for i in range(p, q + 1)))
print('\n'.join(str(v) for v in result))

Submission status: Time Limit Exceeded

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

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

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

result = []
for _ in range(Q):
    p, q = map(int, input().split())
    result.append(sum(t[i][q] - t[i][i - 1] for i in range(p, q + 1)))
print('\n'.join(str(v) for v in result))

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(m)]
B = [list(map(int, input().split())) for _ in range(q)]
l = [[0]*n for _ in range(n)]
for i in range(m):
    l[A[i][0]-1][A[i][1]-1] += 1
#print(l)

a = [[0]*n for _ in range(n)] #差に対して
for i in range(n):
    for j in range(n-i):
        if (j==0):
            a[i][j] = l[0][i]
        else:
            a[i][j] = a[i][j-1] + l[j][j+i]
#print(a)
        
ans = [[0]*n for _ in range(n)]
for i in range(n):
    for j in range(i,n):
        x = 0
        for k in range(j-i+1):
            #print(k)
            if (i!=0):
                x += a[k][j-k]-a[k][i-1]
            else:
                x += a[k][j-k]
        ans[i][j] = x
        #print(i,j,x)
#print(ans)
            

for i in range(q):
    print(ans[B[i][0]-1][B[i][1]-1])

Submission status: Time Limit Exceeded

Solution code:
n,m,qu = map(int,input().split())
l = [0 for _ in range(m)]
r = [0 for _ in range(m)]
p = [0 for _ in range(qu)]
q = [0 for _ in range(qu)]

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

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

for i in range(qu):
  honsu=0
  for j in range(m):
    if l[j]>=p[i] and r[j]<=q[i]:
      honsu+=1
  print(honsu)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np


def main():
    N, M, Q = list(map(int, input().split(' ')))
    x = np.zeros((N + 1, N + 1), dtype=int)
    for _ in range(M):
        left, right = list(map(int, input().split(' ')))
        x[left, right] += 1
    x = np.apply_along_axis(np.cumsum, axis=1, arr=x)
    queries = [list(map(int, input().split(' '))) for _ in range(Q)]
    for q in queries:
        print(x[q[0]:(q[1] + 1), q[1]].sum())


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import sys

input=sys.stdin.readline

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

lrs = [list(map(int, input().split())) for _ in range(m)]
pqs = [list(map(int, input().split())) for _ in range(q)]

train_array = np.zeros((n+1,n+1),dtype=int)

for lr in lrs:
    train_array[lr[0]][lr[1]] +=1


#print(train_array)

train_array_ruisekiwa = np.zeros((n+1,n+1), dtype = int)

for index, train_vector in enumerate(train_array):
    train_array_ruisekiwa[index][0] = train_vector[0]

    for i in range(1, n+1):
        train_array_ruisekiwa[index][i] = train_array_ruisekiwa[index][i-1] + train_vector[i]

#print(train_array_ruisekiwa)

for pq in pqs:
    ans = 0
    for i in range(pq[0],pq[1]+1):
        ans += train_array_ruisekiwa[i][pq[1]] - train_array_ruisekiwa[i][pq[0] - 1]

    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

lrs = [list(map(int, input().split())) for _ in range(m)]
pqs = [list(map(int, input().split())) for _ in range(q)]

train_array = np.zeros((n+1,n+1),dtype=int)

for lr in lrs:
    train_array[lr[0]][lr[1]] +=1


#print(train_array)

train_array_ruisekiwa = np.zeros((n+1,n+1), dtype = int)

for index, train_vector in enumerate(train_array):
    train_array_ruisekiwa[index][0] = train_vector[0]

    for i in range(1, n+1):
        train_array_ruisekiwa[index][i] = train_array_ruisekiwa[index][i-1] + train_vector[i]

#print(train_array_ruisekiwa)

for pq in pqs:
    ans = 0
    for i in range(pq[0],pq[1]+1):
        ans += train_array_ruisekiwa[i][pq[1]] - train_array_ruisekiwa[i][pq[0] - 1]

    print(ans)

Submission status: Time Limit Exceeded

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

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)]
data = [[0] * n for _ in range(n)]
for l, r in lr:
    data[l - 1][r - 1] += 1
for p, q in pq:
    ans = 0
    for i in range(p-1, q):
        ans += sum(data[i][p - 1:q])
    print(ans)

Submission status: Time Limit Exceeded

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


def main():
    n, m, q = map(int, input().split())
    lr = [list(map(int, input().split())) for _ in range(m)]
    pq = [list(map(int, input().split())) for _ in range(q)]
    data = [[0] * n for _ in range(n)]
    for l, r in lr:
        data[l - 1][r - 1] += 1
    #for j in range(n):
    #    print(data[j])
    for p, q in pq:
        ans = 0
        for i in range(p-1, q):
            ans += sum(data[i][p - 1:q])
        print(ans)


main()

Submission status: Time Limit Exceeded

Solution code:
n, m, q = [int(x) for x in input().split()]

t_list = [[0] * (n + 1) for i in range(n + 1)]
c_list = [[0] * (n + 1) for i in range(n + 1)]

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

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

for _ in range(q):
    l, r = [int(x) for x in input().split()]
    ans = 0
    for j in range(l, r + 1):
        ans += c_list[j][r] - c_list[j][l - 1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = [int(x) for x in input().split()]

t_list = []
c_list = []
for _ in range(n + 1):
    t_list.append([0] * (n + 1))
    c_list.append([0] * (n + 1))

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

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

for _ in range(q):
    l, r = [int(x) for x in input().split()]
    ans = 0
    for j in range(l, r + 1):
        ans += c_list[j][r] - c_list[j][l - 1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
from bisect import bisect_left, bisect_right

n, m, q = [int(x) for x in input().split()]

temp_list = []
for i in range(m):
    l, r = [int(x) for x in input().split()]
    temp_list.append((l, i, 0))
    temp_list.append((r, i, 1))
temp_list.sort()

for _ in range(q):
    l, r = [int(x) for x in input().split()]

    li = bisect_left(temp_list, (l, 0, 0))
    ri = bisect_right(temp_list, (r, m, 1))

    flag = [False] * m
    ans = 0
    for j in range(li, ri):
        _, i, f = temp_list[j]
        if f == 0:
            flag[i] = True
        elif f == 1 and flag[i]:
            ans += 1
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

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

x=np.zeros((N+1,N+1),dtype=np.int32)
for _ in range(M):
    l,r=map(int,input().split())
    x[l,r]+=1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

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

x=np.zeros((N+1,N+1),dtype=np.int32)
for _ in range(M):
    l,r=map(int,input().split())
    x[l][r]+=1

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

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

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

x=np.zeros((N+1,N+1),dtype=np.int32)
for _ in range(M):
    l,r=map(int,input().split())
    x[l][r]+=1

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

Submission status: Time Limit Exceeded

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

c=[[0]*N for _ in range(N)]
for i in range(N):
    for j in range(i,N):
        if j==0:
            c[i][0]=x[i][0]
        else:
            c[i][j]=c[i][j-1]+x[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
import sys

input = lambda :sys.stdin.readline().rstrip()

def main():
    n, m, Q = map(int, input().split())
    Train= [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(m):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        Train[l][r] += 1
    
    P_Train = [[0 for _ in range(n + 1)] for _ in range(n)]
    for i in range(n):
        tmp = 0
        for j in range (n):
            tmp += Train[i][j]
            P_Train[i][j + 1] = tmp

    for i in range(Q):
        p, q = map(int, input().split())
        p, q = p - 1, q - 1
        ans = solve(P_Train, n, p, q)
        print(ans)

def solve(P_Train, n, p, q):
    ans = 0
    for i in range(p, q + 1):
        ans += P_Train[i][q + 1] - P_Train[i][p]
    return ans


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def main():
    n, m, Q = map(int, input().split())
    Train= [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(m):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        Train[l][r] += 1
    
    P_Train = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        tmp = 0
        for j in range(n):
            tmp += Train[i][j]
            P_Train[i][j] = tmp

    for i in range(Q):
        p, q = map(int, input().split())
        p, q = p - 1, q - 1
        ans = solve(P_Train, n, p, q)
        print(ans)

def solve(P_Train, n, p, q):
    ans = 0
    for i in range(p, q + 1):
        if  p - 1 < 0:
            ans += P_Train[i][q]
        else:
            ans += P_Train[i][q] - P_Train[i][p - 1]
    return ans


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, M, queries = LI()
    L = []
    R = []
    for _ in range(M):
        l, r = LI()
        L.append(l)
        R.append(r)
    P = []
    Q = []
    for _ in range(queries):
        p, q = LI()
        P.append(p)
        Q.append(q)

    regions = [[] for _ in range(N+1)]
    for l, r in zip(L, R):
        regions[l].append(r-l)
    for i in range(len(regions)):
        regions[i] = sorted(regions[i])

    from bisect import bisect_right
    
    for p, q in zip(P, Q):
        counter = 0
        length = q-p
        for station in range(p, q+1):
            counter += bisect_right(regions[station], length)
            length -= 1
        print(counter)
        
main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
def LILI(n): return [LI() for _ in range(n)]
INF = 10 ** 18
MOD = 10 ** 9 + 7

def main(): 
    N, M, queries = LI()
    L = []
    R = []
    for _ in range(M):
        l, r = LI()
        L.append(l)
        R.append(r)
    P = []
    Q = []
    for _ in range(queries):
        p, q = LI()
        P.append(p)
        Q.append(q)

    regions = [[] for _ in range(N+1)]
    for l, r in zip(L, R):
        regions[l].append(r-l)
    
    for p, q in zip(P, Q):
        counter = 0
        length = q-p
        for station in range(p, q+1):
            for region in regions[station]:
                if region <= length:
                    counter += 1
            length -= 1
        print(counter)


main()

Submission status: Time Limit Exceeded

Solution code:

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

left=[]
right=[]
for i in range(M):
    l,r=map(int, input().split())
    left.append(l)
    right.append(r)
#left=np.array(left)
#right=np.array(right)
for i in range(Q):
    p,q=map(int, input().split())
    #l=left>=p
    #r=right<=q
    #ans=(l*r).sum()
    ans=0
    for j in range(M):
        l=left[j]
        r=right[j]
        if p<=l and r<=q:
            ans+=1
    print(ans)

Submission status: Time Limit Exceeded

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

left=[]
right=[]
for i in range(M):
    l,r=map(int, input().split())
    left.append(l)
    right.append(r)
left=np.array(left)
right=np.array(right)
for i in range(Q):
    p,q=map(int, input().split())
    l=left>=p
    r=right<=q
    ans=(l*r).sum()
    print(ans)

Submission status: Time Limit Exceeded

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

dia = [[0]*(n+1) for i in range(n+1)]
for i in range(m):
  l, r = map(int, input().split())
  dia[l][r] += 1
  
lst = [[0]*(n+1) for i in range(n+1)]
for i in range(1, n+1):
  for j in range(i, n+1):
    lst[i][j] = lst[i][j-1] + dia[i][j]
    
for i in range(q):
  l, r = map(int, input().split())
  count = 0
  for j in range(l, r+1):
    count += lst[j][r]
  print(count)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n,m,q = inpl()
g = [[0]*n for _ in range(n)]
for _ in range(m):
    l,r = inpl()
    l,r = l-1, r-1
    g[l][r] += 1
for _ in range(q):
    a,b = inpl()
    a,b = a-1,b-1
    cnt = 0
    for i in range(a,b+1):
        for j in range(i,b+1):
            cnt += g[i][j] 
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline

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

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

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

    for l in range(N + 1):
        for r in range(N):
            lst[l][r + 1] += lst[l][r]

    # for tmp in lst:
    #     print (tmp)

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

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

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

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

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

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

for l in range(N + 1):
    for r in range(N):
        lst[l][r + 1] += lst[l][r]

# for tmp in lst:
#     print (tmp)

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

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from bisect import bisect_left, bisect_right, insort

nii=lambda:map(int,stdin.readline().split())

N,M,Q=nii()
tree=[[] for i in range(N)]
for i in range(M):
  l,r=nii()
  l-=1
  r-=1
  insort(tree[l],r)

for i in range(Q):
  p,q=nii()
  p-=1
  q-=1

  ans=0
  for j in range(p,N):
    t_list=tree[j]
    num=bisect_right(t_list,q)
    ans+=num

  print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from bisect import bisect_left, bisect_right

nii=lambda:map(int,stdin.readline().split())

N,M,Q=nii()
tree=[[] for i in range(N)]
for i in range(M):
  l,r=nii()
  l-=1
  r-=1
  tree[l].append(r)

for i in range(N):
  tree[i]=sorted(tree[i])



for i in range(Q):
  p,q=nii()
  p-=1
  q-=1

  ans=0
  for j in range(p,N):
    t_list=tree[j]
    num=bisect_right(t_list,q)
    ans+=num

  print(ans)

Submission status: Time Limit Exceeded

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

n,m,q = map(int,input().split())
d = [{} for _ in range(n)]
for i in range(m):
    l,r = map(int,input().split())
    l -= 1
    r -= 1
    if r not in d[l].keys():
        d[l][r] = 0
    d[l][r] += 1
for i in range(n-1)[::-1]:
    for k,v in d[i+1].items():
        if k not in d[i]:d[i][k] = 0
        d[i][k] += v
ans = [0]*q
for i in range(q):
    P,Q = map(int,input().split())
    P -= 1
    Q -= 1
    for k,v in d[P].items():
        if k <= Q:
            ans[i] += v
print('\n'.join(str(i) for i in ans))

Submission status: Time Limit Exceeded

Solution code:
n,m,q=map(int,input().split())
lr=[list(map(int,input().split())) for _ in range(m)]
lr=sorted(lr)
lrL=[x[0] for x in lr]

anL=[]
import bisect
for _ in range(q):
    p,q=map(int,input().split())
    ind=bisect.bisect_left(lrL,p)
    lr1=lr[ind:]
    
    lr2=sorted(lr1,key=lambda x:x[1])
    lrR=[x[1] for x in lr2]
    
    ans=bisect.bisect_right(lrR,q)
    anL.append(ans)

for i in range(len(anL)):
    print(anL[i])

Submission status: Time Limit Exceeded

Solution code:
import sys
input = sys.stdin.readline
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)]

#X[l][r]はlからrをちょうど走る電車の数
X = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l, r in LR:
    X[l][r] += 1
cum = [[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):
        cum[i][j] = cum[i][j-1] + X[i][j]

outputs = []
for p, q in PQ:
    ans = 0
    for i in range(p, q+1):
        ans += cum[i][q] - cum[i][p-1]
    outputs.append(ans)

print('\n'.join(map(str, outputs)))

Submission status: Time Limit Exceeded

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

#X[l][r]はlからrをちょうど走る電車の数
X = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l, r in LR:
    X[l][r] += 1
cum = [[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):
        cum[i][j] = cum[i][j-1] + X[i][j]

for p, q in PQ:
    ans = 0
    for i in range(p, q+1):
        ans += cum[i][q] - cum[i][p-1]
    print(ans)

Submission status: Time Limit Exceeded

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

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

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

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

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

Solution code:
def main():
    import bisect
    import sys
    input = sys.stdin.readline
    n,m,q=map(int,input().split())
    train=[[] for i in range(n)]
    for i in range(m):
        l,r=map(int,input().split())
        train[l-1].append(r-1)
    for i in range(n):
        train[i].sort()
    for i in range(q):
        p,q_=map(int,input().split())
        ans=0
        for i in range(p-1,q_):
            ans+=bisect.bisect_right(train[i],q_-1)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import bisect
n,m,q=map(int,input().split())
train=[[] for i in range(n)]
for i in range(m):
    l,r=map(int,input().split())
    train[l-1].append(r-1)
for i in range(n):
    train[i].sort()
for i in range(q):
    p,q=map(int,input().split())
    ans=0
    for i in range(p-1,q):
        ans+=bisect.bisect_right(train[i],q-1)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:

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

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

        print(ans)

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:

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

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

if __name__ == "__main__":
    resolve()

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    n,m,q = map(int,input().split())
    l = [[0]*(n) for i in range(n)]
    for i in range(m):
        a,b = map(int,input().split())
        l[a-1][b-1] += 1

    for i in range(q):
        a,b = map(int,input().split())
        count = 0
        for i in range(a-1,b):
            for j in range(a-1,b):
                count += l[i][j]
        print(count)
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m,q = map(int,input().split())
l = [[0]*(n) for i in range(n)]
for i in range(m):
    a,b = map(int,input().split())
    l[a-1][b-1] += 1

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

Submission status: Time Limit Exceeded

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

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


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

#pq = [[int(i) for i in input().split()]for j in range(q)]

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

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

ans_dp = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(i,n+1):
        tmp = 0
        for k in range(j-i+1):
            tmp += dp[i+k][j]
        ans_dp[i][j] = tmp

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

Submission status: Time Limit Exceeded

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

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


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

pq = [[int(i) for i in input().split()]for j in range(q)]

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

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

ans_dp = [[0 for i in range(n+1)] for j in range(n+1)]

for i in range(1,n+1):
    for j in range(i,n+1):
        tmp = 0
        for k in range(j-i+1):
            tmp += dp[i+k][j]
        ans_dp[i][j] = tmp

for i in range(q):
    print(ans_dp[pq[i][0]][pq[i][1]])

Submission status: Time Limit Exceeded

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

lr = [[0 for i in range(n+1)] for j in range(n+1)]
#lr = [[int(i) for i in input().split()]for j in range(m)]

st = [0] * (n+1)
ed = [0] * (n+1)

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

pq = [[int(i) for i in input().split()]for j in range(q)]

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

#print(lr)

for i in range(1,n+1):
    #print(i)
    for j in range(i,n+1):
        #print(i,j)
        dp[i][j] = dp[i][j-1]+lr[i][j]

for i in range(q):
    st = pq[i][0]
    ed = pq[i][1]
    tmp = 0
    for j in range(ed-st+1):
        tmp += dp[st+j][ed]
    print(tmp)
#print(dp)

Submission status: Time Limit Exceeded

Solution code:
import sys
readline = sys.stdin.readline
N, M, Q = map(int, readline().split())
X = [[0] * N for _ in range(N)]
for _ in range(M):
    l, r = map(int, readline().split())
    X[l-1][r-1] += 1

S = [[0] * (N + 1) for _ in range(N + 1)]
for i in range(N):
    for j in range(N):
        S[i+1][j+1] = S[i+1][j] + X[i][j]

for _ in range(Q):
    p, q = map(int, readline().split())
    p -= 1
    q -= 1
    ans = sum(S[i][q+1] - S[i][p] for i in range(p + 1, q + 2))
    print(ans)

Submission status: Time Limit Exceeded

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

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