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: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
train = []
loop = 0
for i in range(m):
    l,r = map(int,input().split())
    if l == r:
        loop += 1
    train.append([l,r])

train.sort(key = lambda x: x[1])
cum = [0 for i in range(n+1)] #自己ループを除く 終点用
cumb = [0 for i in range(n+1)] #ジコループを除く　始点用
anothercum = [0 for i in range(n+1)] #自己ループ用

for i in range(m):
    if train[i][0] != train[i][1]:
        cum[train[i][1]] += 1
    else:
        anothercum[train[i][1]] += 1

train.sort(key = lambda x: x[0])
for i in range(m):
    if train[i][1] - train[i][0] > 2:
        cumb[train[i][0]+1] += 1

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



for i in range(1,n+1):
    if cum[i] == 0:
        cum[i] = cum[i-1]
    else:
        cum[i] = cum[i-1] + cum[i]
for i in range(1,n+1):
    if anothercum[i] == 0:
        anothercum[i] = anothercum[i-1]
    else:
        anothercum[i] = anothercum[i-1] + anothercum[i]


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

Submission status: Wrong Answer

Solution code:
import numpy as np

setting = list(map(int, input().split()))

train = []
quest = []
for i in range(setting[1]):
    num = list(map(int, input().split()))
    train.append(num)
train = np.array(train)

for i in range(setting[2]):
    q = list(map(int, input().split()))
    quest.append(q)

train = train * np.array([1,-1])
ansList = []
for qs in quest:
    a = train
    sch = np.array(qs)
    sch = sch * np.array([-1,1])
    b = a + sch
    ans = np.delete(b, np.where(b<0), axis=0)

    ansList.append(ans.shape[0])
    
for an in ansList:
    print(an)

Submission status: Wrong Answer

Solution code:
def binarySearch(D, target):
    left = 0
    right = len(D)
    mid = 0
    while left < right:
        mid = (left + right) // 2
        if D[mid] == target:
            return mid
        elif target < D[mid]:
            right = mid
        else:
            left = mid + 1
    return mid

N, M, Q = list(map(int, input().split()))
LR = {k:[] for k in range(1, N+1)}
for i in range(M):
    l, r = list(map(int, input().split()))
    LR[l].append(r)

# sortしておく
for i in range(1, N+1):
    LR[i].sort()

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

for i in range(Q):
    re = 0
    p, q = PQ[i][0] , PQ[i][1]
#    print(i, p, q)
    for j in range(p,q + 1):
        re += binarySearch(LR[j], q) + 1
    print(re)

Submission status: Wrong Answer

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

table = [[0 for _i in range(N+1)] for _j in range(N+1)]
accum = [[0 for _i in range(N+1)] for _j in range(N+1)]
accum2 = [[0 for _i in range(N+1)] for _j in range(N+1)]

for line in LR:
    table[line[0]][line[1]] += 1
# よこ
for i in range(1, N+1):
    for j in range(i, N+1):
        accum[i][j] = accum[i][j-1] + table[i][j]
# 縦
for i in range(1, N+1):
    for j in range(i, N+1):
        accum2[i][j] = accum2[i-1][j] + accum[i][j]

# for i in range(1, N+1):
#     for j in range(i, N+1):
#         ans[i][j] = sum([accum[k][j] - accum[k][i-1] for k in range(i, j+1)])

for question in pq:
    p = question[0]
    q = question[1]
    print(accum2[q][q] - accum2[p-1][q] - accum2[q][p-1] + accum2[p-1][p-1])

Submission status: Wrong Answer

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

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

p=[]
q=[]    
for i in range(Q):
    c,d=map(int,input().split())
    p.append(c)
    q.append(d)
    
for i in range(Q):
    answer=0
    for j in range(m):
        if p[i]-l[j]+r[j]-q[i]<=0:
            answer+=1
    print(answer)

Submission status: Wrong Answer

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

table = [[0 for _i in range(N+1)] for _j in range(N+1)]
accum = [[0 for _i in range(N+1)] for _j in range(N+1)]
ans = [[0 for _i in range(N+1)] for _j in range(N+1)]

for line in LR:
    table[line[0]][line[1]] += 1
# よこ
for i in range(1, N+1):
    for j in range(i, N+1):
        accum[i][j] = accum[i][j-1] + table[i][j]
# 縦
for i in range(1, N+1):
    for j in range(i, N+1):
        accum[i][j] = accum[i-1][j] + accum[i][j]

# for i in range(1, N+1):
#     for j in range(i, N+1):
#         ans[i][j] = sum([accum[k][j] - accum[k][i-1] for k in range(i, j+1)])

for question in pq:
    p = question[0]
    q = question[1]
    print(accum[q][q] - accum[p-1][q] - accum[q][p-1] + accum[p-1][p-1])

Submission status: Wrong Answer

Solution code:
def binarySearch(D, target):
    left = 0
    right = len(D)
    while left < right:
        mid = (left + right) // 2
        if D[mid] == target:
            return mid
        elif target < D[mid]:
            right = mid
        else:
            left = mid + 1
    return left - 1

N, M, Q = list(map(int, input().split()))
LR = {k:[] for k in range(1, N+1)}
for i in range(M):
    l, r = list(map(int, input().split()))
    LR[l].append(r)

# sortしておく
for i in range(1, N+1):
    LR[i].sort()

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

for i in range(Q):
    re = 0
    p, q = PQ[i][0] , PQ[i][1]
#    print(i, p, q)
    for j in range(p,q + 1):
        re += binarySearch(LR[j], q) + 1
    print(re)

Submission status: Wrong Answer

Solution code:
n,m,q = input().split()
list = []
for i in range(int(m)):
    l,r = input().split()
    list.append([int(l),int(r)])
for i in range(int(q)):
    p,q = input().split()
    count = 0
    for j in range(len(list)):
        print("check")
        if int(p) <= list[j][0] and int(q) >= list[j][1]:
            print("A")
            count += 1
    print(count)

Submission status: Wrong Answer

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

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


D = [["0" for i in range(N+1)] for j in range(N+1)]

for j in range(Q):
	p,q = map(int,input().split())
	if D[p][q] != "0":
		print(D[p][q])
	s = 0
	for i in range(p,q+1):
		for j in range(i,q+1):
			s += C[i][j]
	D[p][q] = s
	print(s)

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
alist=[]
for i in range(m):
    l,r=map(int,input().split())
    alist.append([l,r])
for t in range(q):
    count=m
    p,q=map(int,input().split())
    for i in alist:
        if p>i[0] or p<i[1]:
            count-=1
    print(count)

Submission status: Wrong Answer

Solution code:
from operator import itemgetter

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

trains = []
for i in range(m):
  a, b = map(int, input().split())
  trains.append((a,b))

trains.sort(key=itemgetter(0))
index = [-1 for _ in range(n+1)]
index[trains[0][0]] = 0
tmp = trains[0][0]

for i in range(len(trains)):
  if tmp != trains[i][0]:
    tmp = trains[i][0]
    index[tmp] = i
    
for i in range(len(index)-2, 0, -1):
    if index[i] == -1:
      index[i] = index[i+1]

questions = []
for i in range(q):
  a, b = map(int, input().split())
  questions.append((a,b))

for question in questions:
  cnt = 0
  for train in trains[index[question[0]]:]:
    if train[1] > question[1]:
      continue
    cnt += 1
    
  print(cnt)

Submission status: Wrong Answer

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

ns = [[0 for _ in range(n + 1)]for _ in range(n + 1)]

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

print(ns)

for i in range(q):
    count = 0
    (ql, qr) = map(int, input().split(" "))
    for j in range(ql, qr + 1):
        for k in range(j, qr + 1):
            count += ns[j][k]
    print(count)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int,input().split())
L_list = [0 for _ in range (M)]
R_list = [0 for _ in range (M)]
p_list = [0 for _ in range (Q)]
q_list = [0 for _ in range (Q)]

for m in range (M):
    L_list[m], R_list[m] = map(int,input().split())
    
new_L_list = list(zip(L_list,range(M)))
new_R_list = list(zip(R_list,range(M)))
new_L_list.sort(key=lambda x:x[0])
new_R_list.sort(key=lambda x:x[0])

for q in range (Q):
    p_list[q], q_list[q] = map(int,input().split())

for q in range (Q):
    ans = 0
    for m in range(M):
        if p_list[q] <= new_L_list[m][0]:
            if new_R_list[new_L_list[m][1]][0] <= q_list[q]:
                ans +=1
        else:
            break    
    print(ans)

Submission status: Wrong Answer

Solution code:
N,M,Q = list(map(int,input().split()))
L_R = [list(map(int,input().split())) for i in range(M)]
p_q = [list(map(int,input().split())) for i in range(Q)]
count = 0
for t in range(Q):
    for i in range(M):
        count+=1 if p_q[t][0] <= L_R[i][0] and p_q[t][1] >= L_R[i][1] else 0
print(count)

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
alist=[]
for i in range(m):
    l,r=map(int,input().split())
    alist.append([l,r])
alist.sort()
for t in range(q):
    count=0
    blist=[]
    p,q=map(int,input().split())
    print(alist)
    for j in range (len(alist)):
        if p<=alist[0][0]:
            alist.sort(key=lambda x:x[1])
            break
        blist.append(alist[0])
        alist.remove(alist[0])
    for j in range (len(alist)):
        if q>=alist[j][1]:
            count+=1
        else:
            break
    for k in blist:
        alist.append(k)
    print(count)
    alist.sort(key=lambda x:x[0])

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input().split())
ll = [[0, 0] for i in range(m)]
p = [[0, 0] for i in range(m)]
for i in range(m):
    ll[i][0], ll[i][1] = map(int, input().split())
for i in range(q):
    p[i][0], p[i][1] = map(int, input().split())
ll = sorted(ll, key=lambda x: x[0])
for i in range(q):
    ans = 0
    if max(ll[:][0]) < p[i][0]:
        print(ans)
        continue
    else:
        if p[i][1] < min(ll[:][1]):
            print(ans)
            continue
        else:
            for j in range(m):
                if p[i][0] > ll[j][0]:
                    continue
                if ll[j][1] > p[i][1]:
                    continue
                ans += 1
    print(ans)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
trains = [list(map(int,input().split())) for _ in range(M)]
querys = [list(map(int,input().split())) for _ in range(Q)]
s = [0]*N
e = [0]*N

for t in trains:
  s[t[0]-1] += 1
  e[t[1]-1] += 1

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

for q in querys:
  tmp = M
  if 1 < q[0]:
    tmp -= s[q[0]-2]
  if q[1] < N:
    tmp -= e[q[1]]
  print(tmp)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M, Q = map(int, input().split())
L = []
R = []
for i in range(M):
    tmp = list(map(int, input().split()))
    L.append(tmp[0])
    R.append(tmp[1])
p = []
q = []
for i in range(Q):
    tmp = list(map(int, input().split()))
    p.append(tmp[0])
    q.append(tmp[1])

L = np.array(L)
R = np.array(R)

ans = []
for i in range(len(p)):
    cnt = sum((L <= p[i]) * (R >= q[i]))
    ans.append(cnt)

for i in range(len(p)):
    print(ans[i])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import numpy as np
n,m,q=map(int,input().split())
s=[]
t=[]
ss=[]
for i in range(m):
    x,y=map(int,input().split())
    ss.append((x,y))
ss.sort()
for x,y in ss:
    t+=[y]
for i in range(q):
    x,y=map(int,input().split())
    bi=bisect_left(s,(x,y))
    u=np.array(t[bi:])
    print(len(u[u<=y]))

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input().split())
ll = [[0, 0] for i in range(m)]
p = [[0, 0] for i in range(m)]
for i in range(m):
    ll[i][0], ll[i][1] = map(int, input().split())
for i in range(q):
    p[i][0], p[i][1] = map(int, input().split())
ll = sorted(ll, key=lambda x: x[0])
for i in range(q):
    ans = 0
    if max(ll[:][0]) < p[i][0]:
        continue
    else:
        if p[i][1] < min(ll[:][1]):
            continue
        else:
            for j in range(m):
                if p[i][0] > ll[j][0]:
                    continue
                if ll[j][1] > p[i][1]:
                    continue
                ans += 1
            print(ans)

Submission status: Wrong Answer

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

N_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() )
  N_LR[l][r] += 1

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

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

for i in range(1,N+1):
  if i == 1:
    DP[i][i] = N_LR[1][1]
  else:
    DP[i][i] = DP[i-1][i] - N_LR[i-1][i-1]
  for j in range(i+1, N+1):
    DP[i][j] = DP[i][j-1] + S_LR[j][j] - S_LR[i-1][j]

for i in range(Q):
  x,y = map(int, input().split() )
  print(DP[x][y])

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
lr = []
for i in range(m):
    lr.append(list(map(int,input().split())))
pq = []
for i in range(q):
    pq.append(list(map(int,input().split())))
lr.sort(key=lambda x:x[0])
lr.reverse()
pq.sort(key=lambda x:x[0])
pq.reverse()
for j in pq:
    count = 0
    for i in lr:
        if j[0] <= i[0] and i[1] <= j[1]:
            count += 1
        if j[0] > i [0]:
            break
    print(count)

Submission status: Wrong Answer

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

for i in range(m):
    a,b = map(int,input().split())
    l[i] = a-1
    r[i] = b-1
for i in range(Q):
    a,b = map(int,input().split())
    p[i] = a-1
    q[i] = b-1

a = np.zeros((n,n))
deps = np.zeros(n)
dests = np.zeros(n)
for i in range(n):
    deps[i] = np.sum(l == i)
    dests[i] = np.sum(r == i)
    a[0,i] = np.sum(dests)

for i in range(1,n):
    a[i,:] = a[i-1,:] - deps[i-1]

for i in range(Q):
    x = int(a[int(p[i]),int(q[i])])
    if(x <= 0):
        print(0)
    else:
        print(x)

Submission status: Wrong Answer

Solution code:
def main():
    N, M, Q = map(int, input().split())
    L = [0]*M
    R = [0]*M
    p = [0]*Q
    q = [0]*Q
    LL = [0] * N
    RR = [0] * N
    for i in range(M):
        L[i], R[i] = map(int, input().split())
        LL[L[i]-1] += 1
        RR[R[i]-1] += 1
    for i in range(Q):
        p[i], q[i] = map(int, input().split())

    Lsum = [0] * N
    Rsum = [0] * N
    for i in range(N):
        if i!=0:
            Lsum[i] = Lsum[i-1] - LL[i-1]
            Rsum[i] = Rsum[i-1] + RR[i]
        else:
            Lsum[i] = M
            Rsum[i] = RR[i]

    for i in range(Q):
        print(min(Lsum[p[i]-1], Rsum[q[i]-1]) - min(M-Lsum[p[i]-1], M-Rsum[q[i]-1]))

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
lr=[list(map(int,input().split())) for i in range(0,m)]
pq=[list(map(int,input().split())) for i in range(0,q)]

print(lr)
print(pq)

for x in pq:
    print(sum([1 for i in lr if(x[0]<=i[0] and x[1]>=i[1])]))

Submission status: Wrong Answer

Solution code:
import numpy as np

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

L = [None] * M
R = [None] * M
p = [None] * Q
q = [None] * Q

for i in range(M):
    print(i)
    L[i], R[i] = map(int, input().split())

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

A = np.zeros((N, N))

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

for i in range(Q):
    print(int(A[p[i]-1, q[i]-1]))

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input().split())
city = [[0]*(n+2) for _ in range(n+2)]
same = [0]*(n+1)
for _ in range(m):
    l, r = map(int, input().split())
    city[r][1] += 1
    city[r][l+1] -= 1

    city[1][r] += 1
    city[l+1][r] -= 1
    if l==r:
        same[l] += 1

"""
print()
for c in city[1:n+1]:
    print(c[1:n+1])
"""

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

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


print()
for c in city[1:n+1]:
    print(c[1:n+1])


for _ in range(q):
    x, y = map(int, input().split())
    if x==y:
        print(same[x])
    else:
        print(city[x][y])

Submission status: Wrong Answer

Solution code:
# TLE

import numpy as np

line = input().split()
N = int(line[0])
M = int(line[1])
Q = int(line[2])

L = []
R = []
for i in range(M):
    line = input().split()
    L.append(int(line[0]))
    R.append(int(line[1]))

p = []
q = []
for i in range(Q):
    line = input().split()
    p.append(int(line[0]))
    q.append(int(line[1]))

count = 0

for pp, qq in zip(p, q):
    for LL, RR in zip(L, R):
        if pp <= LL and RR <= qq:
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
import bisect

N, M, Q = map(int, input().split())
trains = [list(map(int, input().split())) for i in range(M)]
queries = [list(map(int, input().split())) for i in range(Q)]
trains.sort(key = lambda x: x[1])
L = [train[0] for train in trains]
R = [train[1] for train in trains]

dp = [[0] * N for i in range(N)]
for i in range(N):
    for j in range(i, N):
        print(i, j)
        right = bisect.bisect_right(R, j + 1)
        A = sorted(L[:right])
        left = bisect.bisect_left(A, i + 1)
        dp[i][j] = right - left
for q in range(Q):
    pi, qi = queries[q]
    print(dp[pi - 1][qi - 1])

Submission status: Wrong Answer

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

N_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() )
  N_LR[l][r] += 1

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

for i in range(1,N+1):
  if i == 1:
    DP[i][i] = N_LR[1][1]
  else:
    DP[i][i] = DP[i-1][i] - N_LR[i-1][i-1]
  for j in range(i+1, N+1):
    DP[i][j] = DP[i][j-1]
    for k in range(i,j+1):
      DP[i][j] += N_LR[k][j]

for i in range(Q):
  x,y = map(int, input().split() )
  print(DP[x][y])

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m, q = map(int, input().split())
m_list = []
for i in range(m):
    m_list.append(list(map(int, input().split())))
m_list = sorted(m_list)
q_list = []
for i in range(q):
    q_list.append(list(map(int, input().split())))
train_map = np.zeros((n, n))
for m_ in m_list:
    start, end = m_[0], m_[1]
    train_map[:start, end-1:] += 1
for q_ in q_list:
    q_s, q_e = q_[0]-1, q_[1]-1
    print(train_map[q_s, q_e])

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect
import bisect

# Set max recursion limit
sys.setrecursionlimit(10000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None


def main():
    N, M, Q = li_input()
    L, R = [], []
    LL = []

    LR = [li_input() for _ in range(M)]
    LR.sort(key=lambda x: x[1])

    LL_ = [0] * (N + 1)
    for l, r in LR:
        L.append(l)
        R.append(r)
        LL_[l] += 1
        LL.append(LL_[:])

    Query = [li_input() for _ in range(Q)]

    for p, q in Query:
        r_idx = bisect.bisect_right(R, q)
        targetLL = LL[r_idx - 1]
        print(sum(targetLL[p:q + 1]))


main()

Submission status: Wrong Answer

Solution code:
import numpy
N, M, Q = map(int, input().split())
l = [0]*(N+1)
r = [0]*(N+1)
for _ in range(M):
    a, b = map(int, input().split())
    l[a] -= 1
    r[b-1] += 1
l = numpy.cumsum(l)
r = numpy.cumsum(r)

for _ in range(Q):
    a, b = map(int, input().split())
    print(r[b-1] + l[a-1])

Submission status: Wrong Answer

Solution code:
n, m, q = map(int, input().split())
city = [[0]*(n+2) for _ in range(n+2)]
same = [0]*(n+1)
for _ in range(m):
    l, r = map(int, input().split())
    city[r][1] += 1
    city[r][l+1] -= 1

    city[1][r] += 1
    city[l+1][r] -= 1
    if l==r:
        same[l] += 1

same_sum = sum(same)
"""
print()
for c in city[1:n+1]:
    print(c[1:n+1])
"""

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

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

for i in range(n+1):
    city[i][i] -= same_sum - same[i]

"""
print()
for c in city[1:n+1]:
    print(c[1:n+1])
"""

for _ in range(q):
    x, y = map(int, input().split())
    print(city[x][y])

Submission status: Wrong Answer

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

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

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

for j in range(1, n):
    for k in range(n-j):
        x[k][j+k] += x[k][j+k-1] + x[k+1][j+k]

y = []
for i in range(q):
    a, b = map(int, input().split())
    y.append(x[a-1][b-1])
    
for i in range(q):
    print(y[i])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left
import numpy as np
n,m,q=map(int,input().split())
s=[]
t=[]
for i in range(m):
    x,y=map(int,input().split())
    s+=[x]
    t+=[y]
for i in range(q):
    x,y=map(int,input().split())
    bi=bisect_left(s,x)
    u=np.array(t[bi:])
    print(len(u[u<=y]))

Submission status: Wrong Answer

Solution code:
import sys

def main(N, LP, PQ):
    # N < 500
    # M < 200,000
    # Q < 100,000
    print("N", N)

    LP = sorted(LP)
    print("LP", LP, file=sys.stderr)

    index = [0] * (N+1)
    l = 0
    p = 0
    for i, pq in enumerate(LP):
        p, q = pq
        if p != l:
            for j in range(l, p):
                index[j] = i
            l = p
    for j in range(p, N+1):
        index[j] = p

    print(index[1:],file=sys.stderr)
    print("PQ", PQ, file=sys.stderr)

    for pq in PQ:
        p, q = pq
        count = 0
        for lr in LR:
            l, r = lr
            if p <= l and r <= q:
                count+=1

        print(count)

N, M, Q = [int(x) for x in input().split(" ")]

LR = []
PQ = []
for i in range(M):
    LR.append(tuple(int(x) for x in input().split(" ")))
for i in range(Q):
    PQ.append(tuple(int(x) for x in input().split(" ")))

main(N, LR, PQ)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(int(1e9))

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

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

H, W = (501, 501)
for i in range(H):
    for j in range(1, W):
        cnt[i][j] = cnt[i][j] + cnt[i][j-1]

for j in range(W):
    for i in range(1, H):
        cnt[i][j] = cnt[i][j] + cnt[i-1][j]

def Sum(l, r):
    return cnt[r][r] - cnt[l][r] - cnt[r][l] - cnt[l][l]

for i in range(Q):
    l, r = list(map(int, input().split()))
    ans = Sum(l-1, r)
    print(ans)

Submission status: Wrong Answer

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

l = []

p = []

for i in range(M):
    l.append(list(map(int,input().split())))
for i in range(Q):
    p.append(list(map(int,input().split())))
l.sort()

for i in p:
    count = 0
    for j in l:
        if (i[0]<= j[0]) and (j[1] <= i[1]):
            count += 1
        elif j[1] < i[0]:
            break
    print(count)

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect
import bisect

# Set max recursion limit
sys.setrecursionlimit(10000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None
Query = []
L, R = [], []
l_lims, r_lims = {}, {}
anss = {}


def f(R, q):
    R.sort()
    return bisect.bisect_right(R, q)


def main():
    N, M, Q = li_input()

    for i in range(M):
        l, r = li_input()
        L.append(l)
        R.append(r)

    Query = [li_input() for _ in range(Q)]

    for p, q in Query:
        if p in l_lims:
            l_lim = l_lims[p]
        else:
            l_lim = bisect.bisect_left(L, p)
            l_lims[p] = l_lim

        ans = f(R[l_lim:], q)

        k = str(p) + "-" + str(q)
        if k not in anss:
            anss[k] = ans

        print(anss[k])


main()

Submission status: Wrong Answer

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

L = [None] * M
R = [None] * M
p = [None] * Q
q = [None] * Q

for i in range(M):
    print(i)
    L[i], R[i] = map(int, input().split())

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

for i in range(Q):
    count = 0
    for j in range(M):
        if p[i] <= L[j] and R[j] <= q[i]:
            count += 1
    print(count)

Submission status: Wrong Answer

Solution code:
import sys
import math
import collections
import itertools
import array
import inspect
import bisect

# Set max recursion limit
sys.setrecursionlimit(10000)


# Debug output
def chkprint(*args):
    names = {
        id(v): k
        for k, v in inspect.currentframe().f_back.f_locals.items()
    }
    print(', '.join(
        names.get(id(arg), '???') + ' = ' + repr(arg) for arg in args))


# Binary converter
def to_bin(x):
    return bin(x)[2:]


def li_input():
    return [int(_) for _ in input().split()]


# --------------------------------------------

dp = None


def f(R, q):
    R.sort()
    return bisect.bisect_right(R, q)


def main():
    N, M, Q = li_input()
    L, R = [], []

    for i in range(M):
        l, r = li_input()
        L.append(l)
        R.append(r)

    for i in range(Q):
        p, q = li_input()

        l_lim = bisect.bisect_left(L, p)
        print(f(R[l_lim:], q))


main()

Submission status: Wrong Answer

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

Submission status: Time Limit Exceeded

Solution code:
import itertools

N, M, Q = map(int, input().split(' '))
table = [[0]*N for _ in range(N)]

# O(N*M)
for _ in range(M):
  l, r = map(int, input().split(' '))
  for i in range(l):
    table[i][r-1] += 1
    
for i in range(N):
  table[i] = list(itertools.accumulate(table[i]))
      
for _ in range(Q):
  p, q = map(int, input().split(' '))
  print(table[p-1][q-1])

Submission status: Time Limit Exceeded

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

# O(N^2 * M)
for _ in range(M):
  l, r = map(int, input().split(' '))
  for i in range(l):
    for j in range(r-1,N):
      table[i][j] += 1
      
for _ in range(Q):
  p, q = map(int, input().split(' '))
  print(table[p-1][q-1])

Submission status: Time Limit Exceeded

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
n,m,q = ma()
L_rs=[[] for i in range(n)]
for i in range(m):
    l,r=ma()
    L_rs[l-1].append(r-1)
for i in range(n):
    L_rs[i].sort()
# print(L_rs)
def isok(num,val):##適宜変更
    return num<=val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ

def solve(L,R):##0idx
    ret=0
    for l in range(L,R+1):
        ret+=bisect(L_rs[l],R)+1
    return ret
ans = [[0]*n for i in range(n)]
for l in range(n):
    for r in range(n):
        ans[l][r]=solve(l,r)

for i in range(q):
    l,r=ma()
    print(ans[l-1][r-1])

Submission status: Time Limit Exceeded

Solution code:
ma = lambda :map(int,input().split())
lma = lambda :list(map(int,input().split()))
tma = lambda :tuple(map(int,input().split()))
ni = lambda:int(input())
yn = lambda fl:print("Yes") if fl else print("No")
ips = lambda:input().split()
import collections
import math
import itertools
import heapq as hq
n,m,q = ma()
L_rs=[[] for i in range(n)]
for i in range(m):
    l,r=ma()
    L_rs[l-1].append(r-1)
for i in range(n):
    L_rs[i].sort()
# print(L_rs)
def isok(num,val):##適宜変更
    return num<=val
def bisect(ls,val): ##valの関数isok(x,val)がTrueとなる一番右のindex を返す 全部Falseなら-1,Trueならlen(ls)-1
    ok = -1
    ng = len(ls)
    x = (ok+ng)//2
    while ng-ok>1:
        num = ls[x]
        if isok(num,val):
            ok = x
        else:
            ng = x
        x = (ok+ng)//2
    return ok ##一番右のTrueのindex  Trueの個数はok+1こ

def solve(L,R):##0idx
    ret=0
    for l in range(L,R+1):
        ret+=bisect(L_rs[l],R)+1
    return ret
for i in range(q):
    l,r=ma()
    print(solve(l-1,r-1))