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())
NN = [ [0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    L, R = map( int, input().split())
    NN[L][R] += 1

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

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

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

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

    ans = x[p][q]
    print(ans)

Submission status: Wrong Answer

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

# 二次元累積和をとる
LR_sum = [[0] * (N+1) for _ in range(N+1)]
LR_sum[1][1] = LR[1][1]
## 初期化
for i in range(1, N+1):
    LR_sum[1][i] = LR_sum[1][i-1] + LR[1][i]
    LR_sum[i][1] = LR_sum[i-1][1] + LR[i][1]
## 累積和をとる
for i in range(2, N+1):
    for j in range(2, N+1):
        LR_sum[i][j] = LR_sum[i-1][j] + LR_sum[i][j-1] - LR_sum[i-1][j-1] + LR[i][j]

for tmp in LR:
    print(tmp)
print('sum')
for tmp in LR_sum:
    print(tmp)

for q in range(Q):
    l, r = map(int, input().split())
    print(LR_sum[r][r] - LR_sum[r][l-1] - LR_sum[l-1][r] + LR_sum[l-1][l-1])
    # print(LR_sum[r-1][l-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

inputs = raw_input().replace("\n", "")
N, M, Q = map(int, inputs.split(" "))

Ls = []
Rs = []
for i in xrange(M):
    inputs = raw_input().replace("\n", "")
    L, R = map(int, inputs.split(" "))
    Ls.append(L)
    Rs.append(R)

min_L = min(Ls)
max_L = max(Ls)
min_R = min(Rs)
max_R = max(Rs)

lr_counts = np.zeros((max_L-min_L+1, max_R-min_R+1))
for L, R in zip(Ls, Rs):
    lr_counts[L-min_L, R-min_R] += 1

q_inputs = []
for i in xrange(Q):
    q_input = raw_input().replace("\n", "")
    q_inputs.append(q_input)

relu = (lambda x: max(0, x))
print lr_counts
for q_input in q_inputs:
    p, q = map(int, q_input.split(" "))
    print int(np.sum(lr_counts[relu(p-min_L):relu(q-min_L+1), relu(p-min_R):relu(q-min_R+1)]))

Submission status: Wrong Answer

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



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

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

'''
#図のような正方形で累積和を考える
こう取ればLが1でRが10の時（一番右下の時)全ての区間が入るように和を計算できる

  1 2 3 4 5 6 7 8 9 10 ←R
10                   1
9
8
7                 1
6           1 1
5               1
4         1   2
3
2                 1
1           1
↑
L

例えば、L,R=5,8の電車はもちろん5,8の区間に含まれている。
ここで5,8の区間に含まれる電車の数を考えると5,7の電車や6,8の電車は含まれている...
という風に考えると累積和を取れる
ここで、6,7の区間に含まれる電車の数は5,7と6,8を数えることで2回計算されているのでマイナスする


'''

'''
for i in range(Q):
  answer=0
  Query=list(map(int,input().split()))
  for j in range(M):
    if train[j][0]>=Query[0] and train[j][1]<=Query[1]:
      answer+=1
  print(answer)
'''

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
for i in range(1, n + 1):
    for j in range(i, n + 1):
        ns[i][j] += ns[i][j - 1]
for j in range(1, n + 1):
    for i in range(1, j + 1):
        ns[i][j] += ns[i - 1][j]

for i in range(q):
    count = 0
    (l, r) = map(int, input().split(" "))
    print(ns[r][r] - ns[l - 1][r - 1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
n, m, q = map(int, input().split())
e = []
for i in range(n):
    e.append([])
for i in range(m):
    x, y = map(int, input().split())
    e[x-1].append(y)
for i in range(q):
    ans = 0
    x, y = map(int, input().split())
    for j in range(x - 1, y):
        ans += bisect_right(e[j], y, 0, len(e[j]))
    print(ans)

Submission status: Wrong Answer

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

A = [[0, 0] for i in range (n+1)]
B = [[0, 0] for i in range (n+1)]

for l, r in L:
    A[l][0] += 1
    A[r][1] += 1

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

for p, q in Q:
    print(B[q][1] - B[p-1][1] - B[p-1][0])

Submission status: Wrong Answer

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

A = [0] * (N * N)

for i in range(M):
    l, r = map(int, input().split())
    A = [a+1 if i%10 < l and i//10 >= (r-1) else a for i, a in enumerate(A)]

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

Submission status: Wrong Answer

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

import sys


def main():
    n, m, q = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]

    x = [[0 for j in range(n+1)] for i in range(n+1)]
    c = [[0 for j in range(n+1)] for i in range(n+1)]
    z = [[0 for j in range(n+1)] for i in range(n+1)]

    for i in range(m):
        l, r = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        x[l][r] += 1
    
    for i in range(1, n+1):
        for j in range(1, n+1):
            c[i][j] = c[i][j-1] + x[i][j]

    for j in range(1, n+1):
        for i in range(1, n+1):
            z[i][j] = z[i-1][j] + c[i][j]
    
    for i in range(q):
        qp, qq = [int(x) for x in sys.stdin.readline().rstrip().split(' ')]
        print(z[qq][qq] - z[qq][qp-1] - z[qp-1][qq] + z[qp][qp])


if __name__=='__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M,Q=[int(i) for i in input().split()]
LR = [[int(i)-1 for i in input().split()] for j in range(M)]
pq = [[int(i)-1 for i in input().split()] for j in range(Q)]

imosL = [0 for i in range(N)]
imosR = [0 for i in range(N)]

for l,r in LR:
	imosL[l]+=1
	imosR[r]+=1

for i in range(N-1):
	imosL[i+1]+=imosL[i]
for i in range(N-1,0,-1):
	imosR[i-1]+=imosR[i]
#print(imosL)
#print(imosR)
for p,q in pq:
	res=0
	if 0<p:
		res+=imosL[p-1]
	if q<N-1:
		res+=imosR[q+1]
	print(M-res)

Submission status: Wrong Answer

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

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

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

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

Submission status: Wrong Answer

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

a=[[0] * (n) for i in range(n)]
b=[[0] * (n) for i in range(n)]

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

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

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

N, M, Q = [int(elem) for elem in input().split(' ')]
lines = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
queries = [[int(elem) for elem in input().split(' ')] for _ in range(Q)]



def cuml_1d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1

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


    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        num_lines = 0
        for l in range(p, max(q + 1, N)):
            if p == 0:
                num_lines += cuml_coords[l][q]
            else:
                num_lines += cuml_coords[l][q] - cuml_coords[l][p]
        print(num_lines)

cuml_1d(N, lines, queries)

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)

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

train = np.array(train)
train = train * np.array([1,-1])
set = np.array([-1,1])
    
ansList = []
for qs in quest:
    a = train
    sch = np.array(qs)
    sch = sch * set
    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:
n, m, q = [int(i) for i in input().split()]
m_list = [[0 for i in range(n + 1)] for j in range(n + 1)]
dynamic = [[0 for i in range(n + 1)] for j in range(n + 1)]

a_to_b = [[0 for i in range(n + 1)] for j in range(n + 1)]
for i in range(m):
    l, r = [int(i) for i in input().split()]
    m_list[l][r] += 1

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

for i in range(2, n + 1):
    for j in range(i, n + 1):
        if i == j:
            dynamic[i][j] = m_list[i][j]
        else:
            dynamic[i][j] = \
                dynamic[i - 1][j] - \
                dynamic[i - 1][j - 1] - \
                m_list[i - 1][j]

for i in range(q):
    l, r = [int(i) for i in input().split()]
    print(dynamic[l][r])

Submission status: Wrong Answer

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

Ps = [0 for _ in range(N)]
Qs = [0 for _ in range(N)]
dp = [[0 for _ in range(N)] for _ in range(N)]

for i in range(M):
    if Trains[i] == [1, 1]:
        dp[0][0] += 1
    Ps[Trains[i][0] - 1] += 1
    Qs[Trains[i][1] - 1] += 1

for i in range(1, N):
    dp[0][i] = dp[0][i - 1] + Qs[i]


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

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

Submission status: Wrong Answer

Solution code:
def spaceinput():
    return list(map(int,input().split(" ")))

def f(l,r):
    global a,nl,nr,N
    #print(l,r)
    #print(a[l][r])
    if a[l][r]>=0:
        return a[l][r]

    if l-1>=1:
        if nl[l-1]>0:
            tmp=f(l-1,r)-nl[l-1]
            a[l][r]=tmp
            return tmp
        else:
            tmp=f(l-1,r)
            a[l][r]=tmp
            return tmp



    if r+1<=N:
        if nr[r+1]>0:
            tmp=f(l,r+1)-nr[r+1]
            a[l][r]=tmp
            return tmp
        else:
            tmp=f(l,r+1)
            a[l][r]=tmp
            return tmp



N,M,Q=spaceinput()

nr=[0]*(N+1)
nl=[0]*(N+1)

for i in range(M):
    s=spaceinput()
    nl[s[0]]+=1
    nr[s[1]]+=1

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

for i in range(Q):
    s=spaceinput()
    #print(s)
    ssss=f(s[0],s[1])
    #print("ans")
    #print(type(ssss))
    print(ssss)






#print(a)

Submission status: Wrong Answer

Solution code:
def spaceinput():
    return list(map(int,input().split(" ")))

def f(l,r):
    global a,nl,nr,N
    #print(l,r)
    #print(a[l][r])
    if a[l][r]>=0:
        return a[l][r]

    if l-1>=1:
        if nl[l-1]>0:
            tmp=f(l-1,r)-nl[l-1]
            a[l][r]=tmp
            return tmp
        else:
            tmp=f(l-1,r)
            a[l][r]=tmp
            return tmp



    if r+1<=N:
        if nr[r+1]>0:
            tmp=f(l,r+1)-nr[r+1]
            a[l][r]=tmp
            return tmp
        else:
            tmp=f(l,r+1)
            a[l][r]=tmp
            return tmp

    return f(l,r+1)



N,M,Q=spaceinput()

nr=[0]*(N+1)
nl=[0]*(N+1)

for i in range(M):
    s=spaceinput()
    nl[s[0]]+=1
    nr[s[1]]+=1

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

for i in range(Q):
    s=spaceinput()
    #print(s)
    ssss=f(s[0],s[1])
    #print("ans")
    #print(type(ssss))
    print(ssss)

Submission status: Wrong Answer

Solution code:
def main():
    N,M,Q=map(int,raw_input().split())
    LR=list()
    for x in xrange(M):
        LR.append(map(int,raw_input().split()))
    #print LR
    for x in xrange(Q):
        L,R=map(int,raw_input().split())
        #print L,R
        count=0
        for i in xrange(M):                                    
            if((L>=LR[i][0] or LR[i][0]<=R) and  R>=LR[i][1] ): count=count+1
        print(count)
#import sys
#sys.stdin=open("testdata01.txt","r")
#raw_input=sys.stdin.readline
main()
#sys.stdin.close()

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])
new_LR_list = list(zip(L_list,R_list,range(M)))
new_LR_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_LR_list[m][0] and new_LR_list[m][1]<= q_list[q]:
        ans_list = [lr for lr in new_LR_list if p_list[q] <= new_LR_list[m][0] and new_LR_list[m][1]<= q_list[q]]
        ans = len(ans_list)
    print(ans)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
L=[]
for i in range(M):
    lr=list(map(int,input().split()))
    lr.append(i)
    L.append(lr)
RR=L
L.sort(key=lambda x:x[0])
RR.sort(key=lambda x:x[1])
    
for _ in range(Q):
    p,q=map(int,input().split())
    R=RR
    a=0
    b=M-1
    while b-a>1:
        c=(a+b)//2
        if L[c][0]>=p: b=c
        else: a=c
    d=0
    e=M-1
    while e-d>1:
        f=(d+e)//2
        if L[f][1]>q: e=f
        else: d=f    
    print(e-b)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, raw_input().split())
L = []
R = []
for i in range(M):
	_l, _r = map(int, raw_input().split())
	L.append(_l)
	R.append(_r)

p = []
q = []
for i in range(Q):
	_p, _q = map(int, raw_input().split())
	p.append(_p)
	q.append(_q)


start_length_mat = [[0] * (N + 2) for i in range(N + 2)]

for i in range(M):
	start = L[i]
	length = R[i] - L[i] + 1
	for j in range(start + 1):
		for k in range(length, N + 2):
			start_length_mat[start - j][k] += 1

for i in range(Q):
	start = p[i]
	length = q[i] - p[i] + 1
	print(start_length_mat[start][length])

Submission status: Wrong Answer

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

for i in range(q):
  l,r = map(int,input().split())
  d = copy.deepcopy(num)
  e = d[l-1:r]
  hi = e[0]
  mi = e[len(e)-1]
  print(m + 2 - (min(e) + max(hi,mi)))

Submission status: Wrong Answer

Solution code:
n, m, Q = [int(i) for i in input().split()]
l_list = []
r_list = []
p_list = []
q_list = []
for _ in range(m):
    l, r = [int(i) for i in input().split()]
    l_list.append(l)
    r_list.append(r)

for _ in range(Q):
    p, q = [int(i) for i in input().split()]
    p_list.append(p)
    q_list.append(q)


start_map = [0 for i in range(n)]
end_map = [0 for i in range(n)]
unique_map = [0 for i in range(n)]

for i in range(m):
    l = l_list[i]
    r = r_list[i]
    start_map[l - 1]+=1
    end_map[r - 1]+=1

accum_unique_list = [sum(unique_map[:n+1]) for i in range(n)]
dp = [[0 for j in range(n)]for i in range(n)]


dp[0][n-1] = m
for q in range(n-2, -1, -1):
    end_num = end_map[q+1]
    dp[0][q] = dp[0][q+1] - end_num

for p in range(1, n):
    start_num = start_map[p-1]
    dp[p][n-1] = dp[p-1][n-1] - start_num

for p in range(1, n):
    for q in range(n-2, -1, -1):
        end_num = end_map[q+1]
        dp[p][q] = dp[p][q+1] - end_num


for i in range(Q):
    count = 0
    p = p_list[i]
    q = q_list[i]
    num = dp[p-1][q-1]
    print(num)

Submission status: Wrong Answer

Solution code:
# S = input()
# K = int(input())
N, M, Q = map(int, input().split())
# A = 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)]

ar = [[0] * (N+1) for _ in range(N+1)]
arL = [0 for _ in range(N+1)]
arR = [0 for _ in range(N+1)]

for left in range(N+1):
    count = 0
    for i in range(M):
        if left <= LR[i][0]:
            count += 1

    arL[left] = count

for right in range(N+1):
    count = 0
    for i in range(M):
        if right >= LR[i][1]:
            count += 1

    arL[right] = count

for left in range(N+1):
    for right in range(N + 1):
        ar[left][right] = arL[left] * arR[right]


for i in range(Q):
    print(ar[pq[i][0]][pq[i][1]] + (pq[i][0] - 1) * (pq[i][0] - 1) + (N-pq[i][1])*(N-pq[i][1]) - M)

Submission status: Wrong Answer

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

A=[ 0 for i in range(N+2) ]

for i in range(M):
	l,r=map( int , raw_input().split() )
	A[l]+=1
	A[r+1]-=1

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

AL=[]
a_max=-1
for x in A:
	if a_max<x:
		a_max=x
	AL.append(a_max)

a_max=-1
AR=[ 0 for i in range(N+2) ]
for i in range(N+1,-1,-1):
	x=A[i]
	if a_max<x:
		a_max=x
	AR[i]=a_max
	

P=[ map( int , raw_input().split() ) for i in range(Q) ]


for x,y in P:
	print M-(AL[x-1]+AR[y+1])

Submission status: Wrong Answer

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

for i in range(m):
    x = lr[i]
    nxn[x[0]-1][x[1]-1]+=1
mm[n-1][0]+=nxn[n-1][0]
for i in range(1,n):
    mm[n-1][i] += mm[n-1][i-1]+nxn[n-1][i]
for i in range(1,n):
    mm[i][0] += mm[i-1][0]+nxn[i][0]
for i in range(n-2,-1,-1):
    for j in range(i,n):
        mm[i][j] += mm[i+1][j]+mm[i][j-1]+nxn[i][j]

for i in range(q):
    a = pq[i]
    print(mm[a[0]-1][a[1]-1])

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
#print(N,M,Q)
list1=[]
for b in range(N+2):
    list1.append([0])

for i in range(1,M+1):
    ts,tg=map(int,input().split())
    for a in range(len(list1)):
        if ts==tg:
            if a==ts:
                pass
            else:
                list1[a].append(i)
        elif a<ts or tg<a:
            list1[a].append(i)
print(list1)

for j in range(Q):
    qs,qg=map(int,input().split())
    cnt=0
    for k in range(1,M+1):
        if k in list1[qs-1] and k in list1[qg+1]:
            cnt+=1
    print(cnt)

Submission status: Wrong Answer

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

import numpy as np

L = np.zeros(M)
R = np.zeros(M)
for i in range(M):
    L[i], R[i] = [int(i) for i in input().split()]
p = np.zeros(Q)
q = np.zeros(Q)
for i in range(Q):
    p[i], q[i] = [int(i) for i in input().split()]

keep = 0

ans = [0 for i in range(Q)]

for i in range(Q):
    count = 0
    for j in range(keep,M):
        if L[j] >= p[i]:
            if L[j] > q[i]:
                ans[i] = count
                break
            else:
                if R[j] <= q[i]:
                    count += 1
                    if j == M-1:
                        ans[i] = count
                        break
        else:
            keep = j

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

Submission status: Wrong Answer

Solution code:
import copy

N, M, Q = [int(i) for i in input().split()]
l = []
r = []
p = []
q = []
ans = [0 for _ in range(Q)]
for i in range(M):
    l_, r_ = [int(i) for i in input().split()]
    l.append(l_)
    r.append(r_)

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

def main():
    print('l = {}. r = {}'.format(l, r))
    print('p = {}. q = {}'.format(p, q))
    a = sorted([(p_, q_, i) for i, (p_, q_) in enumerate(zip(p,q))])
    b = sorted([(l_, r_) for l_, r_ in zip(l, r)])
    print(a)
    print(b)
    for i, (p_, q_, idx) in enumerate(a):
        if i == 0:
            d = copy.deepcopy(b)
            c = 0
            removes = []
        else:
            print('p[{}] = {}, p[{}] = {}'.format(i-1, a[i-1][0], i,p_))
            if a[i-1][0] != p_:
                c = 0
                d = copy.deepcopy(b)
                removes = []
                print('before c = {}'.format(c))
        for j, (l_, r_) in enumerate(d):
            if j in removes:
                continue
            if (p_ <= l_) and (q_ >= r_):
                c += 1
                removes.append(j)
        print('idx = {}, c = {}'.format(idx, c))
        ans[idx] = c
    for item in ans:
        print(item)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]
enuq = list(enumerate(qs))
 
enuq.sort(key = lambda x:x[1][0])
ansli = [0 for i in range(q)]


for (i,(p,q)) in enuq:
    for (j,(l,r)) in enumerate(rails):
        if p<=l and r<=q:
            ansli[i]=ansli[i]+1
        elif l<p:
            rails.pop(j)


for a in ansli:
    print(a)

Submission status: Wrong Answer

Solution code:
from collections import Counter


def bin(ll, target, key):  # リストにtargetが最初に含まれる位置
    if len(ll) < 100:
        if target in [key(a) for a in ll]:
            return [key(a) for a in ll].index(target)
        return -1

    length = len(ll)
    l, r = ll[:length // 2], ll[length // 2:]
    if key(r[0]) == target:
        if key(l[-1]) != target:
            return len(l)
        return bin(l, target, key)
    elif key(r[0]) > target:
        return bin(l, target, key)
    else:
        return len(l) + bin(r, target, key)


def main():
    n, m, q = [int(a) for a in input().split()]
    QQQ = q
    LRi = sorted([[int(a) for a in input().split()] for _ in range(m)], key=lambda it: it[0])

    PQi = [([int(a) for a in input().split()], k) for k in range(q)]
    PQi = sorted(PQi, key=lambda a: a[0][1])
    PQi = sorted(PQi, key=lambda a: a[0][0])

    TABLE = []  # iから始まる列車のRとその数
    ii = 0
    for i in range(1, n + 1):
        a = []  # iから伸びる列車の右端
        while True:
            if ii >= len(LRi):
                break
            l, r = LRi[ii]
            if l == i:
                a.append(r)
                ii += 1
            else:
                break
        # a = sorted(a)
        c = Counter(a)

        TABLE.append([(a, c[a]) for a in sorted(c.keys())])

    ii = 0
    res = {}
    while True:
        if ii >= len(PQi):
            break

        (l, r), k = PQi[ii]# pqに対して、その範囲内のカウンタ全部取得
        counts = []
        for i in range(l, r + 1):
            count = TABLE[i - 1]  # タプル kまでの数v
            for rrrr, nnnnn in count:
                if rrrr <= r:
                    counts.append((rrrr, nnnnn))
                else:
                    break
        lls = [(r, k)]  # 同じlから始まるQ
        ii += 1
        while True:
            if ii >= len(PQi):
                break
            (ll, rr), kk = PQi[ii]
            if ll == r:
                lls.append((rr, kk))
                ii += 1
            else:
                break

        lls = sorted(lls, key=lambda a: a[0])
        b = 0
        c = 0
        for r, k in lls:
            while True:
                if c >= len(counts):
                    break
                kk, v = counts[c]
                if kk <= r:
                    b += v
                    c += 1
                else:
                    break
            res[k] = b
    for i in range(QQQ):
        print(res[i])

    # for p, q in PQi:
    #     a = []  # iから伸びる列車の右端
    #     while True:
    #         l, r = LRi[ii]
    #         ii += 1
    #         if l == i:
    #             a.append(r)
    #         else:
    #             break
    #     # a = sorted(a)
    #     c = Counter(a)


# def count_contain(l, r):
#     l_index = bin(LRi, l, lambda a: a[0])
#     while True:
#         L,R = LRi[l_index]


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,M,Que = map(int,input().split())
#M本の列車それぞれの走る区間の条件
L,R = [],[]
for i in range(M):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)
#Que個の問題それぞれの区間
P,Q = [],[]
for j in range(Que):
    p,q = map(int,input().split())
    P.append(p)
    Q.append(r)

#Que個の解答

for k in range(Que):
    Ans = 0
    for kk in range(M):
        if (P[k] <= L[kk]) and (R[kk] <= Q[k]):
            Ans += 1
    print(Ans)

Submission status: Wrong Answer

Solution code:
from bisect import bisect_left

n, m, q = map(int, input().split())
LR = [0]*m
for i in range(m):
    LR[i] = list(map(int, input().split()))
P = [0]*q
Q = [0]*q
for i in range(q):
    P[i], Q[i] = map(int, input().split())

LR.sort(key=lambda x: (x[0], x[1]))
L = list(map(lambda x: x[0], LR))
R = list(map(lambda x: x[1], LR))
#print(LR)

B = [0]*(n+2)
C = [[0]*(n+1) for _ in range(n+1)]
for i in range(1,n+1):
    B[i] = bisect_left(L, i)
B[i+1] = n

for i in range(1,n+1):
    l = B[i]
    r = B[i+1]-1
    R2 = R[l:r+1]
    #print(l, r, R2)
    for j in range(i,n+1):
        C[i][j] = bisect_left(R2, j+1)
    #print(i, C[i])

for i in range(q):
    ans = 0
    for j in range(P[i], Q[i]+1):
        ans += C[j][Q[i]]
    print(ans)

Submission status: Wrong Answer

Solution code:
import bisect
import numpy as np
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(np.array(lr).transpose())
index_dict={}
r_dict={} 
d = {}
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 i in range(Q):
    p,q = map(int,input().split())
    if p not in d:
        d[p]={}
    else:
        if q not in d[p]:
            I = index_dict[p]
            r = r_dict[p]
            I = bisect.bisect(r,q)
            print(I)
            d[p][q]=I
        else:
            print(d[p][q])

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])
new_LR_list = list(zip(L_list,R_list,range(M)))
new_LR_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_LR_list[m][0] and new_LR_list[m][1]<= q_list[q]:
             ans +=1
        else:
            break    
    print(ans)

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