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:
# D - AtCoder Express 2
# https://atcoder.jp/contests/abc106/tasks/abc106_d

import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# N 個の都市
# M 本の列車
# Q 個の興味
def main_lte(N, M, Q, LRm, PQq):
    for p, q in PQq:
        ans = 0
        for l, r in LRm:
            if p <= l and r <= q:
                ans += 1
        print(ans)

def main_lte2(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            for j in range(i, q+1):
                ans += table[i][j]
        print(ans)

def main(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    # 累積輪
    table2 = [[0] * (N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, N+1):
            table2[i][j] = table2[i][j-1] + table[i][j]
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            ans += table2[i][q] - table2[i][p-1]
        print(ans)

N, M, Q = i2nn()
LRm = ii2nnn(M)
PQq = ii2nnn(Q)
main(N, M, Q, LRm, PQq)

Submission status: Time Limit Exceeded

Solution code:
# D - AtCoder Express 2
# https://atcoder.jp/contests/abc106/tasks/abc106_d

import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# N 個の都市
# M 本の列車
# Q 個の興味
def main_lte(N, M, Q, LRm, PQq):
    for p, q in PQq:
        ans = 0
        for l, r in LRm:
            if p <= l and r <= q:
                ans += 1
        print(ans)

def main(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            for j in range(i, q+1):
                ans += table[i][j]
        print(ans)

N, M, Q = i2nn()
LRm = ii2nnn(M)
PQq = ii2nnn(Q)
main(N, M, Q, LRm, PQq)

Submission status: Time Limit Exceeded

Solution code:
# D - AtCoder Express 2
# https://atcoder.jp/contests/abc106/tasks/abc106_d

import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# N 個の都市
# M 本の列車
# Q 個の興味
def main(N, M, Q, LRm, PQq):
    for p, q in PQq:
        ans = 0
        for l, r in LRm:
            if p <= l and r <= q:
                ans += 1
        print(ans)

N, M, Q = i2nn()
LRm = ii2nnn(M)
PQq = ii2nnn(Q)
main(N, M, Q, LRm, PQq)

Submission status: Time Limit Exceeded

Solution code:
N, M ,Q = map(int, input().split())
train = [list(map(int, input().split())) for i in range(M)]
qs = [list(map(int, input().split())) for i in range(Q)]
ns = []
for i in range(N+1):
    ns.append([0]*(N+1))
for l, r in train:
    for i in range(r, N+1):
        ns[l][i] += 1
for p, q in qs:
    ans = 0
    for i in range(p, q+1):
        ans += ns[i][q]
    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))


Lzip, Rzip = zip(*LR)

from functools import lru_cache

@lru_cache(maxsize=N)
def Lmet(Lz, l):
  return [l <= x for x in Lz]

@lru_cache(maxsize=N)
def Rmet(Rz, r):
  return [x <= r for x in Rz]

for p, q in PQ:
  lm = Lmet(Lzip, p)
  rm = Rmet(Rzip, q)
  print(sum(a*b for a, b in zip(lm, rm)))

Submission status: Time Limit Exceeded

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

from itertools import product, permutations, combinations

memo = {(i,i):0 for i in range(1, N+1)}
trains = {(i,i):0 for i in range(1, N+1)}
for x in combinations(range(1,N+1), 2):
  x = (min(x), max(x))
  memo[x] = 0
  trains[x] = 0

for l, r in LR:
  memo[(l,r)] +=1

for k, v in memo.items():
  for l, r in product(range(1,k[0]+1), range(k[1], N+1)):
    trains[(l,r)] += v

for p,q in PQ:
  print(trains[(p,q)])

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]"):
    mem = [[0] * N for i in range(N)]
    for i in range(M):
        mem[L[i] - 1][R[i] - 1] += 1
        #print(L[i], R[i], mem)
    for i in range(Q):
        pc = p[i]-1
        qc = q[i]-1
        sum = 0
        for w in range(pc, qc+1):
            for h in range(pc, qc+1):
                sum += mem[w][h]
        print(sum)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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:
def main():
	N, M, Q = map(int, input().split())
	LR = [[0 for _ in range(N+1)] for _ in range(N+1)]
	ans = [0]*Q
	for _ in range(M):
		l, r = map(int, input().split())
		LR[l][r] += 1
	for i in range(Q):
		p, q = map(int, input().split())
		for a in range(p, q+1):
			for b in range(a, q+1):
				ans[i] += LR[a][b]
	for a in ans:
		print(a)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from operator import itemgetter

N, M, Q = list(map(int, input().split()))
LR = sorted([list(map(int, input().split())) for i in range(M)], key=itemgetter(0))

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

for l in range(1, N+1):
    flag = [1 for i in range(len(LR))]
    for r in range(1, N+1):
        count = 0
        for idx, lr in enumerate(LR):
            if flag[idx] and l <= lr[0] and lr[1] <= r:
                count += 1
                flag[idx] = 0
        route[l][r] = route[l][r-1] + count
        
    while len(LR):
        if LR[0][0] == l:
            LR.pop(0)
        else:
            break
for i in range(Q):
    p, q = list(map(int, input().split()))
    print(route[p][q])

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


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

    for i in range(1, N+1):
        a[i] = list(itertools.accumulate(a[i]))

    for pp, qq in zip(p, q):
        print(int(sum([a[i][qq]-a[i][pp-1] for i in range(pp, qq+1)])))
    # print(a)

    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:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
# import numpy as np
INF = float("inf")


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

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

    for pp, qq in zip(p, q):
        print(int(sum([a[i][qq]-a[i][pp-1] for i in range(pp, qq+1)])))
    # print(a)

    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:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
import numpy as np
INF = float("inf")


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

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

    for pp, qq in zip(p, q):
        print(int(sum([a[i][qq]-a[i][pp-1] for i in range(pp, qq+1)])))
    # print(a)

    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:
#!/usr/bin/env python3
import sys
import itertools
import collections
import functools
import math
from queue import Queue
import numpy as np
INF = float("inf")


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    a = np.zeros((N+1, N+1))
    for l, r in zip(L, R):
        a[l][r] += 1

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

    for pp, qq in zip(p, q):
        print(int(sum([a[i][qq]-a[i][pp-1] for i in range(pp, qq+1)])))
    # print(a)

    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:
# 2019/04/05
# AtCoder Beginner Contest 106 - D

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

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

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

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

for i in range(q):
    ip, iq = map(int, input().split())
    ans = 0

    for j in range(ip, iq+1):
        ans += sted_acm[j][iq] - sted_acm[j][ip-1]
    
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import defaultdict
N,M,Q = map(int,input().split())
lr = [tuple(map(int,input().split())) for i in range(M)]
pq = [tuple(map(int,input().split())) for i in range(Q)]
lr.sort()
l = [lr[i][0] for i in range(M)]
r = [lr[i][1] for i in range(M)]

l_I = {}
for p in range(1,N+1):
    l_I[p] = bisect.bisect_left(l,p)

r_d = {}
for i in range(1,N+1):
    r_d[i] = sorted(r[l_I[i]:])
ans = defaultdict(lambda:{})
for p in range(1,N+1):
    for q in range(p,N+1):
        ans[p][q] = bisect.bisect(r_d[p],q)
for i in range(Q):
    p,q = pq[i]
    print(ans[p][q])

Submission status: Time Limit Exceeded

Solution code:
import bisect
from collections import defaultdict
N,M,Q = map(int,input().split())
lr = [0]*M
for i in range(M):
    l,r = map(int,input().split())
    lr[i] = [l,r]
lr = sorted(lr,key=lambda x:x[0])
lr_t = list(map(list, zip(*lr)))
index_dict={}
r_dict={}
ans = defaultdict(lambda:{})
for i in range(N):
    index_dict[i+1]=bisect.bisect_left(lr_t[0],i+1)
    r_dict[i+1]=sorted(lr_t[1][index_dict[i+1]:])
for p in range(1,N+1):
    for q in range(p,N+1):
        I = index_dict[p]
        r = r_dict[p]
        I = bisect.bisect(r,q)
        ans[p][q]=I
for i in range(Q):
    p,q = map(int,input().split())
    print(ans[p][q])

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
total = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    l, r = map(int, input().split())
    total[l][r] += 1
cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    tmp = 0
    for j in range(1, N+1):
        tmp += total[i][j]
        cum[i][j] += tmp
for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for i in range(p, q+1):
        ans += cum[i][q] - cum[i][i-1]
    print(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)]
pq = [list(map(int, input().split())) for _ in range(Q)]
total = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l, r in lr:
    total[l][r] += 1
cum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1, N+1):
    tmp = 0
    for j in range(1, N+1):
        tmp += total[i][j]
        cum[i][j] += tmp
for p, q in pq:
    ans = 0
    for i in range(p, q+1):
        ans += cum[i][q] - cum[i][i-1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)]
dlr = {}
for i in range(len(lr)):
    if not lr[i] in dlr:
        dlr[lr[i]] = 0
    dlr[lr[i]] += 1
for p, q in pq:
    ans = 0
    for (l, r), v in dlr.items():
        if p-1 <= l-1 <= r-1 <= q-1:
            ans += v
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
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)]
dlr = {}
for i in range(len(lr)):
    if not lr[i] in dlr:
        dlr[lr[i]] = 0
    dlr[lr[i]] += 1
ans = [[0 for _ in range(N)] for _ in range(N)]
for i in range(N):
    for j in range(i, N):
        for (l, r), v in dlr.items():
            if i <= l-1 <= r-1 <= j:
                ans[i][j] += v
for p, q in pq:
    print(ans[p-1][q-1])

Submission status: Time Limit Exceeded

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

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


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

Submission status: Time Limit Exceeded

Solution code:
n, m, q = map(int, input().split())
train = []
question = []
for i in range(m):
    temp = [int(i) for i in input().split()]
    train.append(temp)
ans = []
for j in range(q):
    temp = [int(i) for i in input().split()]
    count = 0
    for t in train:
        if (t[0] >= temp[0]) & (t[1] <= temp[1]):
            count += 1
    ans.append(count)
for i in ans:
    print(i)

Submission status: Time Limit Exceeded

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

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

Submission status: Time Limit Exceeded

Solution code:
N, M, Q = map(int, input().split())
coordinate = [[0 for _ in range(N)] for i in range(N)]
for m in range(M):
    l, r = map(int, input().split())
    coordinate[l-1][r-1] += 1
PQ = [list(map(int, input().split())) for i in range(Q)]

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

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
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007

#A
def A():
    return

#B
def B():
    return

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

#D
def D():
    n,m,q = LI()
    v = [[] for i in range(n)]
    for i in range(m):
        l,r = LI()
        v[l-1].append(r-1)
        v[l-1].sort()
    f = [[bisect.bisect_right(v[i],j) for j in range(n)] for i in range(n)]
    for i in range(q):
        p,q = LI()
        p -= 1
        q -= 1
        ans = 0
        for j in range(p,q+1):
            ans += f[j][q]
        print(ans)
#E
def E():
    return

#F
def F():
    return

#G
def G():
    return

#H
def H():
    return

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

Submission status: Time Limit Exceeded

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

A = [[0] * (N + 1) for i in range(N + 1)]
for i in range(M):
    l, r = map(int, input().split())
    A[l][r] += 1
    
for i in range(Q):
    p, q = map(int, input().split())
    cnt = 0
    for i in range(p, q + 1):
        cnt += sum(A[i][p : q + 1])
    print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import defaultdict
N,M,Q=map(int,input().split())
d=defaultdict(int)
for i in range(M):
  a,b=map(int,input().split())
  d[(a,b)]+=1
c={}
for x in range(0,N+1):
  for y in range(0,x):
    c[(x,y)]=0
  c[(x,x)]=d[(x,x)]
  for y in range(x+1,N+1):
    c[(x,y)]=c[(x,y-1)]+d[(x,y)]
for i in range(Q):
  x,y=map(int,input().split())
  print(sum(c[(j,y)]-c[(j,x-1)] for j in range(x,y+1)))

Submission status: Time Limit Exceeded

Solution code:
import itertools
from collections import defaultdict
N,M,Q=map(int,input().split())
d=defaultdict(int)
for i in range(M):
  a,b=map(int,input().split())
  d[(a,b)]+=1
c={}
for x,y in itertools.product(range(0,N+1),repeat=2):
  c[(x,y)]=sum(d[(x,j)] for j in range(1,y+1))
for i in range(Q):
  x,y=map(int,input().split())
  print(sum(c[(j,y)]-c[j,x-1] for j in range(x,y+1)))

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M,Q = map(int, input().split())
table = np.zeros((N,N),dtype=int)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N,M,Q = map(int, input().split())
table = np.zeros((N,N),dtype=int)

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

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

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

Submission status: Time Limit Exceeded

Solution code:
import bisect
N,M,Q=map(int,input().split())
L=[]
for i in range(M):
  a,b=map(int,input().split())
  L.append([a,b])
L.sort(key=lambda x:x[0])
for i in range(Q):
  x,y=map(int,input().split())
  j=bisect.bisect(L,[x,0])
  ans=0
  for k in range(j,M):
    if L[k][1]<=y:
      ans+=1
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

N, M, Q = map(int, input().split())
N_Map = np.zeros((N + 1, N + 1))
for _ in range(M):
    a = list(map(int, input().split()))
    N_Map[:a[0] + 1, a[1]:] += 1

result = []
for _ in range(Q):
    a = list(map(int, input().split()))
    result.append(N_Map[a[0], a[1]])
for r in result:
    print(int(r))

Submission status: Time Limit Exceeded

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

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

Li = []
for _ in range(M):
    a = list(map(int, input().split()))
    Li.append(a)
    N_Map[a[0]][a[1]] += 1

Pi = []
for _ in range(Q):
    a = list(map(int, input().split()))
    Pi.append(a)

for p in Pi:
    ans = 0
    for i in range(p[0], p[1] + 1):
        for j in range(p[0], p[1] + 1):
            ans += N_Map[i][j]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m, q = (int(i) for i in input().split())  
M = [[int(i)-1 for i in input().split()] for i in range(m)]
Q = [[int(i)-1 for i in input().split()] for i in range(q)]

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

for m_ in M:
    x[m_[0]][m_[1]] += 1

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

for q_ in Q:
    sum_num = 0
    for i in range(q_[0], q_[1]+1):
        sum_num += c[i][q_[1]] - (c[i][q_[0]-1] if q_[0] > 0 else 0)
    print(sum_num)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
RcntL = np.zeros((N+1, N+1), int)
for _ in range(M):
    l, r = map(int, input().split())
    RcntL[r:, l] += 1
pq = []
for _ in range(Q):
    pq.append(list(map(int, input().split())))

RcntL = np.cumsum(RcntL, axis=1)

for p, q in pq:
    ans = RcntL[q, q] - RcntL[q, p - 1]
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
RcntL = np.zeros((N+1, N+1), int)
for _ in range(M):
    l, r = map(int, input().split())
    RcntL[r:, l] += 1
pq = []
for _ in range(Q):
    pq.append(list(map(int, input().split())))

for p, q in pq:
    ans = np.sum(RcntL[q, p:q+1])
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def inpl(): return list(map(int,input().split()))

N, M , Q = inpl()
#trains = np.zeros((N+1,N+1),dtype=np.int)
cumsum = np.zeros((N+1,N+1),dtype=np.int)
ans = np.zeros((N+1,N+1),dtype=np.int)

for i in range(M):
    L, R = inpl()
    cumsum[L,R] += 1

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

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

for i in range(Q):
    p, q = inpl()
    print(ans[p,q])

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
def inpl(): return list(map(int,input().split()))

N, M , Q = inpl()
trains = np.zeros((N,N),dtype=np.int)
ans = np.zeros((N,N),dtype=np.int)

for i in range(M):
    L, R = inpl()
    trains[L-1,R-1] += 1

for l in range(N):
    for r in range(l,N):
        ans[l,r] = trains[l:r+1,l:r+1].sum()

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

Submission status: Time Limit Exceeded

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

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

for begin in range(1,n+1):
    s = 0
    for ending in range(begin,n+1):
        for k in range(begin,ending+1):
            s += table[ending][k]
        res[ending][begin] = s
for _ in range(q):
    start,end = map(int,input().split())
    print(res[end][start])

Submission status: Time Limit Exceeded

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

table = []

for i in range(n+1):
    table.append([0]*(i+1))

for i in range(m):
    a,b = map(int,input().split())
    table[b][a] += 1

for _ in range(q):
    start,end = map(int,input().split())
    res = 0
    for i in range(start,end+1):
        res += sum(table[i][start:])
    print(res)

Submission status: Time Limit Exceeded

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

for i in range(n+1):
  for j in range(n+1):
    cnum[i][j] = cnum[i][j-1] + trnum[i][j]

for _ in range(q):
  qp, qq = map(int, input().split())
  s = 0
  for j in range(qp, qq+1):
    s += cnum[j][qq] - cnum[j][qp-1]
  print(s)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
toshi = []
for i in range(M):
  toshi.append(tuple(map(int,input().split())))
query = []
for i in range(Q):
  query.append(tuple(map(int,input().split())))
grid = []
for i in range(N+1):
  grid.append([0]*(N+1))
for i in range(M):
  grid[toshi[i][1]][toshi[i][0]] += 1
for i in range(1,N+1):
  for j in range(1,N+1):
    grid[i][j] += grid[i][j-1]
for i in range(Q):
  ans = 0
  for j in range(query[i][1]-query[i][0]+1):
    ans += (grid[query[i][0]+j][query[i][1]]-grid[query[i][0]+j][query[i][0]-1])
  print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M,Q = map(int,input().split())
toshi = []
for i in range(M):
  toshi.append(list(map(int,input().split())))
query = []
for i in range(Q):
  query.append(list(map(int,input().split())))
grid = []
for i in range(N+1):
  grid.append([0]*(N+1))
for i in range(M):
  grid[toshi[i][1]][toshi[i][0]] += 1
for i in range(1,N+1):
  for j in range(1,N+1):
    grid[i][j] += grid[i][j-1]
for i in range(Q):
  ans = 0
  for j in range(query[i][1]-query[i][0]+1):
    ans += (grid[query[i][0]+j][query[i][1]]-grid[query[i][0]+j][query[i][0]-1])
  print(ans)

Submission status: Time Limit Exceeded

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

LRsum = [[0 for x in range(N+1)] for y in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        LRsum[i][j] = LRsum[i][j-1] + LR[i][j]

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

Submission status: Time Limit Exceeded

Solution code:
import bisect

N,M,Q = map(int,input().split())
LR = []
for i in range(M):
    L,R = map(int,input().split())
    LR.append((L,R))
LR = sorted(LR)
L = [t[0] for t in LR]
R = [t[1] for t in LR]
#print(LR)
pq = []
for i in range(Q):
    pq.append(list(map(int,input().split())))
for i in range(Q):
    p,q = pq[i]
    left = bisect.bisect_left(L,p)
    #print(left,M)
    #print(R[left:M])
    ans = len(list(filter(lambda t:t <= q, R[left:M])))
    print(ans)