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:

import numpy as np
import sys
sys.setrecursionlimit(100000)



def acinput():
    return list(map(int, input().split(" ")))



directions=np.array([[1,0],[0,1],[-1,0],[0,-1]])
directions = list(map(np.array, directions))

mod = 10**9+7


def factorial(n):
    fact = 1
    for integer in range(1, n + 1):
        fact *= integer
    return fact



def serch(x, count):
    #print("top", x, count)
            

    for d in directions:
        nx = d+x
        #print(nx)
        if np.all(0 <= nx) and np.all(nx < (H, W)):
            if field[nx[0]][nx[1]] == "E":
                count += 1 
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)  
                continue
            if field[nx[0]][nx[1]] == "#":
                field[nx[0]][nx[1]] = "V"
                count = serch(nx, count)    
                 
    return count

N,M,Q=acinput()

A=np.zeros([N+1,N+1])

for i in range(M):
    tmp=acinput()
    A[tmp[0],tmp[1]]+=1
Acs=np.cumsum(A,axis=1 )
Acs=np.cumsum(Acs,axis=0)

for i in range(Q):
    tmp=acinput()
    print(Acs[tmp[1], tmp[1]]-Acs[tmp[1],tmp[0]-1]-Acs[tmp[0]-1,tmp[1]]+Acs[tmp[0]-1, tmp[0]-1])

Submission status: Wrong Answer

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

# 二次元累積和
# A[i1, j1] -> A[i2, j2] :=
# Acum[i2 + 1][j2 + 1] - Acum[i1][j2 + 1] - Acum[i2 + 1][j1] + Acum[i1][j1]
def two_dim_accumulate(a) -> list:
  h, w = len(a), len(a[0])
  acum = [[0 for _ in range(h + 1)] for _ in range(w + 1)]
  for i in range(h):
    for j in range(w):
      acum[i + 1][j + 1] = a[i][j]
  for i in range(1, h + 1):
    for j in range(1, w + 1):
      acum[i][j] += acum[i][j - 1]
  for j in range(1, w + 1):
    for i in range(1, h + 1):
      acum[i][j] += acum[i - 1][j]
  return acum

A = [[0 for _ in range(N)] for _ in range(N)]
for l, r in LR:
  A[l - 1][r - 1] += 1
Acum = two_dim_accumulate(A)
print(Acum)
  
for p, q in PQ:
  print(Acum[q][q] - Acum[p - 1][q] - Acum[q][p - 1] + Acum[p - 1][p - 1])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

for _ in range(q):
    p, q = map(int, input().split())
    print(max(SLlim[q] + SRlim[p] - m,0))

Submission status: Wrong Answer

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

for _ in range(q):
    p, q = map(int, input().split())
    print(SLlim[q] + SRlim[p] - m)

Submission status: Wrong Answer

Solution code:
#%%
import numpy as np

n, m, Q = map(int ,input().split())
l, r, p, q = [0] * m, [0] * m, [0] * Q, [0] * Q
count = [[0] * n for _ in range(n)]
for i in range(m):
    l[i], r[i] = map(lambda x: int(x) - 1, input().split())
    count[l[i]][r[i]] += 1
for i in range(Q):
    p[i], q[i] = map(lambda x: int(x) - 1, input().split())

print(np.array(count))

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

print(np.array(count))

for i in range(Q):
    if 0 <= p[i]-1:
        tmp = count[q[i]][q[i]] - count[p[i]-1][q[i]]
    else:
        tmp = count[q[i]][q[i]]
    print(tmp)

Submission status: Wrong Answer

Solution code:
#%%
import numpy as np

n, m, Q = map(int ,input().split())
l, r, p, q = [0] * m, [0] * m, [0] * Q, [0] * Q
count = [[0] * n for _ in range(n)]
for i in range(m):
    l[i], r[i] = map(lambda x: int(x) - 1, input().split())
    count[l[i]][r[i]] += 1
for i in range(Q):
    p[i], q[i] = map(lambda x: int(x) - 1, input().split())

#print(np.array(count))

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

#print(np.array(count))

for i in range(Q):
    if 0 <= p[i]-1:
        tmp = count[q[i]][q[i]] - count[p[i]-1][q[i]]
    else:
        tmp = count[n-1][q[i]]
    print(tmp)

Submission status: Wrong Answer

Solution code:
#%%


n, m, Q = map(int ,input().split())
l, r, p, q = [0] * m, [0] * m, [0] * Q, [0] * Q
count = [[0] * n for _ in range(n)]
for i in range(m):
    l[i], r[i] = map(lambda x: int(x) - 1, input().split())
    count[l[i]][r[i]] += 1
for i in range(Q):
    p[i], q[i] = map(lambda x: int(x) - 1, input().split())

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

for i in range(Q):
    if 0 <= p[i]-1:
        tmp = count[n-1][q[i]] - count[p[i]-1][q[i]]
    else:
        tmp = count[n-1][q[i]]
    print(tmp)

Submission status: Wrong Answer

Solution code:
n, m, Q = map(int ,input().split())
l, r, p, q = [0] * m, [0] * m, [0] * Q, [0] * Q
count = [[0] * n for _ in range(n)]
for i in range(m):
    l[i], r[i] = map(lambda x: int(x) - 1, input().split())
    count[l[i]][r[i]] += 1
for i in range(Q):
    p[i], q[i] = map(lambda x: int(x) - 1, input().split())


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

for i in range(Q):
    if 0 <= p[i]-1:
        tmp = count[n-1][q[i]] - count[p[i]-1][q[i]]
    else:
        tmp = count[n-1][q[i]]
    print(tmp)

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)]
#print(LR)
#print(pq)

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

for L, R in LR:
  C[L][R] += 1
#print(C)

for i in range(N+1):
  for j in range(N+1):
    S[i][j] += S[i][j-1] + C[i][j]
#print(S)

for p, q in pq:
  tmp = 0
  for i in range(p, q+1):
    tmp += S[i][q] - S[i][p-1]
  print(tmp)
  
print("解説読んだ")

Submission status: Wrong Answer

Solution code:
n,m,q = map(int,input().split())
query = [[0 for j in range(500)] for i in range(500)]
for h in range(m):
    k,l = map(int,input().split())
    query[k-1][l-1] += 1
"""
def search(l,r):
    ans = 0
    for i in range(l,r+1):
        for j in range(l,r+1):
            ans += query[i][j]
    return ans
"""

#リストを累積和にする
for i in range(500):
    for j in range(500):
        if j == 0:
            continue
        query[i][j] = query[i][j] + query[i][j-1]
for i in range(500):
    for j in range(500):
        if j == 0:
            continue
        query[i][j] = query[i][j] + query[i-1][j]
        

for h in range(q):
    k,l = map(int,input().split())
    A,B,C = 0,0,0
    if k > 1:
        A = query[k-2][l-1]
        B = query[l-1][k-2]
        C = query[k-2][k-2]
    print(query[l-1][l-1] - A - B + C)

Submission status: Wrong Answer

Solution code:
import numpy as np

def solve(N, M, Q, L, R, p, q):
    u = np.zeros(N+2, dtype=int)
    v = np.zeros(N+2, dtype=int)
    l = [0] + sorted(L)
    r = [0] + sorted(R)
    for i in range(M):
        u[l[i]:l[i+1]] = M - i
        v[r[i]:r[i+1]] = M - i
    res = []
    for i in range(Q):
        h = u[p[i]-1] - v[q[i]]
        res.append(max(0, h))
    return "\n".join(map(str, res))

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import bisect
N,M,Q=map(int,input().split())
Rli=[[] for _ in range(N)]
for i in range(M):
  l,r=map(int,input().split())
  Rli[l-1].append(r)

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

Submission status: Wrong Answer

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

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

for l in range(N+1):
  sums=0
  for r in range(N):
    pos[l][r+1]=pos[l][r]+pos[l][r+1]
    
for r in range(N+1):
  sums=0
  for l in range(N):
    pos[l+1][r]=pos[l][r]+pos[l+1][r]

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

for i in range(n):
    for j in range(n+1):
        g[i+1+1][1+j]+=g[1+i][1+j]
for i in range(n+1):
    for j in range(n):
        g[1+i][1+j+1]+=g[1+i][j+1]
        
#r=[[0 for i in range(n+2)] for j in range(n+2)]
for i in range(n+1):
    for j in range(n+2):
        g[i+1][j]+=g[i][j]
for i in range(n+2):
    for j in range(n+1):
        g[i][j+1]+=g[i][j]
for i in range(q):
    a,b=map(int,input().split())
    b+=1
    print(g[b][b]+g[a][a]-2*g[a][b])

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
m, n, q = map(int, input().split())
train_lis = []
city_lis = []
rm_tbl = [[0 for i in range(m)] for i in range(m)]
for i in range(n):
    train_lis.append(list(map(int, input().split())))
    rm_tbl[train_lis[i][1] - 1][train_lis[i][0] - 1] = 1
for i in range(q):
    city_lis.append(list(map(int, input().split())))
sum_tbl = [[0 for i in range(m)] for i in range(m)]

for i in range(m):
    for j in range(m):
        sum_tbl[i][j] = sum_tbl[i - 1][j] + rm_tbl[i][j]
for i in range(q):
    l = city_lis[i][0] - 1
    r = city_lis[i][1] - 1
    tmp_sum = 0
    for j in range(l, r + 1):
        if l == 0:
            tmp_sum += sum_tbl[r][j]
        else:
            tmp_sum += sum_tbl[r][j] - sum_tbl[l - 1][j]
    print(tmp_sum)

Submission status: Wrong Answer

Solution code:
m, n, q = map(int, input().split())
train_lis = []
city_lis = []
rm_tbl = [[0 for i in range(m)] for i in range(m)]
for i in range(n):
    train_lis.append(list(map(int, input().split())))
    rm_tbl[train_lis[i][1] - 1][train_lis[i][0] - 1] = 1
for i in range(q):
    city_lis.append(list(map(int, input().split())))
for i in range(q):
    l = city_lis[i][0] - 1
    r = city_lis[i][1] - 1
    tmp_sum = 0
    for j in range(l, r + 1):
        for k in range(l, r + 1):
#             print(l)
            tmp_sum += rm_tbl[j][k]
    print(tmp_sum)

Submission status: Wrong Answer

Solution code:
import bisect,sys
input = sys.stdin.readline
n,m,q = map(int, input().split( ))

L_ = [[] for i in range(n+1)]

for i in range(m):
    li,ri = map(int, input().split( ))
    L_[li].append(ri)
#配列アクセスを除外
L = [tuple(L_[i]) for i in range(n+1)]
#O(q*n*log m)
#print(L)
for i in range(q):
    pi, qi = map(int, input().split( ))
    ans = 0
    for j in range(pi,qi+1):
        t = bisect.bisect_right(L[j], qi)
        ans += t
        #print(t)
    print(ans)

Submission status: Wrong Answer

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

L = [[] for i in range(n+1)]

for i in range(m):
    li,ri = map(int, input().split( ))
    L[li].append(ri)
#O(q*n*log m)
for i in range(q):
    pi, qi = map(int, input().split( ))
    ans = 0
    for j in range(pi,qi+1):
        t = bisect.bisect_right(L[j], qi)
        ans += t
        #print(t)
    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,m,q=map(int, input().split())  
a=[list(map(int, input().split())) for i in range(m)]
b=[list(map(int, input().split())) for i in range(q)]

x=np.zeros((501, 501))

for i in range(m):
    x[a[i][0], a[i][1]]+=1

x = np.cumsum(x, axis=0)
x = np.cumsum(x, axis=1)

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2, v2]
    a2=x[v2, v1-1]
    a3=x[v1-1, v2]
    a4=x[v1-1, v1-1]
    print(a1-a2-a3+a4)

Submission status: Wrong Answer

Solution code:
import numpy as np

n,m,q=map(int, input().split())  
a=[list(map(int, input().split())) for i in range(m)]
b=[list(map(int, input().split())) for i in range(q)]

x=np.zeros((501, 501))

for i in range(m):
    x[a[i][0]][a[i][1]]+=1

x= np.cumsum(x, axis=0)
x= np.cumsum(x, axis=1)

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2,v2]
    a2=x[v2,v1-1]
    a3=x[v1-1,v2]
    a4=x[v1-1,v1-1]
    print(a1-a2-a3+a4)

Submission status: Wrong Answer

Solution code:
# D - AtCoder Express 2

import numpy as np
import sys

N, M, Q = map(int, input().split())
LRpq = np.array(sys.stdin.read().split(), np.int64)
L = LRpq[:2*M:2]
R = LRpq[1:2*M:2]
p = LRpq[2*M::2]
q = LRpq[2*M+1::2]

Submission status: Wrong Answer

Solution code:
# D - AtCoder Express 2

import numpy as np
import sys

N, M, Q = map(int, input().split())
L, R, = [], []
p, q = np.array([],np.int64), np.array([],np.int64)
for _ in range(M):
    l, r = map(int, sys.stdin.readline().split())
    L.append(l)
    R.append(r)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M, Q = map(int, input().split())
L, R, = [], []
p, q = np.array([],np.int64), np.array([],np.int64)
for _ in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

Submission status: Wrong Answer

Solution code:
import numpy as np

N, M, Q = map(int, input().split())
L, R, = [], []
p, q = np.array([],np.int64), np.array([],np.int64)
for _ in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p = np.append(p, [tmp_p])
    q = np.append(q, [tmp_q])

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys
buf = sys.stdin.buffer
 
N, M, Q = map(int, buf.readline().split())
city = np.zeros((N + 1, N + 1), np.int32)
LRpq = np.array(buf.read().split(), np.int32)
 
L = LRpq[:2 * M:2]
R = LRpq[1:2 * M:2]
p = LRpq[2 * M::2]
q = LRpq[2 * M + 1::2]

Submission status: Wrong Answer

Solution code:
n,m,q=map(int,input().split())
b=[501*[0]for i in range(501)]
for i in range(m):
  r,l=map(int,input().split())
  b[r][l]+=1
for i in range(500):
  for j in range(1,500):b[i][j]+=b[i][j-1]
for i in range(1,500):
  for j in range(500):b[i][j]+=b[i-1][j]
for i in range(q):
  l,r=map(int,input().split())
  print(b[r][r]-b[l-1][r]-b[r][l-1]+b[l-1][l-1])
#  >>優しい言葉を投げかければそのコードはACする<<

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# ABC106D - AtCoder Express 2
from itertools import accumulate as acc


def main():
    # 2D cumulative sum
    N, M, Q, *X = map(int, open(0).read().split())
    LR, PQ = X[: 2 * M], X[2 * M :]
    imos = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in zip(*[iter(LR)] * 2):
        imos[l][r] += 1
    imos = [list(acc(a)) for a in zip(*[acc(a) for a in imos])]
    ans = []
    for p, q in zip(*[iter(PQ)] * 2):
        cur = imos[q][q] - imos[p - 1][q]
        ans.append(cur)
    print("\n".join(map(str, ans)))


if __name__ == "__main__":
    main()

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

Sumtable = [[0 for _ in range(N+1)] for _ in range(N+1)]
for l,r in LR:
  Sumtable[l][r] += 1
#print(Sumtable)
for i in range(1,N+1):
  for j in range(1,N+1):
    Sumtable[i][j] += Sumtable[i-1][j] + Sumtable[i][j-1] - Sumtable[i-1][j-1]
#print(Sumtable)

for p,q in PQ:
  print(Sumtable[q][q] - Sumtable[p-1][q] - - Sumtable[q][p-1] + Sumtable[p-1][p-1])

Submission status: Wrong Answer

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

for i in range(q):
    question = list(map(int, input().split()))
    count = 0
    for k in train:
        if question[0] <= k[0]:
            break

        elif question[1] >= k[1]:
            count += 1

    print(count)

Submission status: Wrong Answer

Solution code:
import bisect
N,M,Q = map(int,input().split())
I = {}
for _ in range(M):
    L,R = map(int,input().split())
    if L not in I:
        I[L] = []
    I[L].append(R)
A = sorted(list(I.keys()))
for _ in range(Q):
    p,q = map(int,input().split())
    indL = bisect.bisect_left(A,p)
    indR = bisect.bisect_right(A,q)
    cnt = 0
    for i in range(indL,indR):
        a = A[i]
        ind = bisect.bisect_right(I[a],q)
        cnt += ind
    print(cnt)

Submission status: Wrong Answer

Solution code:
import numpy as np
N,M,Q = [int(x) for x in input().split()]
ans = np.array([[0,0,0] for _ in range(N+1)])
for _ in range(M):
  L,R = [int(x) for x in input().split()]
  ans[L+1:R,1] +=1
  ans[L,0] += 1
for i in range(N-1,-1,-1):
  ans[i,2] = ans[i+1,2]+ans[i+1,0]
for _ in range(Q):
  p,q = [int(x) for x in input().split()]
  if (ans[p,1]+ans[q,1]+ans[p,2]-ans[q,2])<=M:
  	print(M-(ans[p,1]+ans[q,2]+ans[q,1]))
  else:
    a = abs(M-(ans[p,1]+ans[q,1]+ans[p,2]-ans[q,2]))
    print(M-(ans[p,1]+ans[q,2]+ans[q,1])+a)

Submission status: Wrong Answer

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

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

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

for x,y in [map(int,input().split()) for i in range(q)]:
    print(book[y][y]-book[y][x-1]-book[x-1][y]+book[x][x])

Submission status: Wrong Answer

Solution code:
import sys
import math
from collections import defaultdict

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))

#################

#時間計測

from bisect import bisect_right
from operator import itemgetter

N,M,Q = II()
x = []
for _ in range(M):
    L,R = II()
    x.append((L-1, R-1))
query = []
for _ in range(Q):
    p0,q0 = II()
    query.append((p0-1,q0-1))

x.sort(key=itemgetter(1))

y = [[float('inf')]*M for _ in range(N)]
c = [0]*N
for i in range(M):
    for j in range(x[i][0]+1):
        y[j][c[j]] = x[i][1]
        c[j] += 1
'''
ans = 0
for q in query:
    print(bisect_right(y[q[0]], q[1]))
'''

Submission status: Wrong Answer

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

L = [0] * M
R = [0] * M
p = [0] * Q
q = [0] * Q
Lcount = [0] * N
Rcount = [0] * N

intminus = lambda x:int(x)-1

for i in range(M):
    L[i],R[i] = map(intminus,input().split())
    Lcount[L[i]] += 1
    Rcount[R[i]] += 1
for j in range(Q):
    p[j],q[j] = map(intminus,input().split())

#print(L,R)
#print(p,q)

Lsum, Rsum = 0, 0

Linfo = [0] * N #start before or on i
Rinfo = [0] * N #end before or on i
Linfo[0] = Lcount[0]
Rinfo[0] = Rcount[0]

for k in range(1,N):
    Linfo[k] = Linfo[k-1] + Lcount[k]
    Rinfo[k] = Rinfo[k-1] + Rcount[k]

#print(info)

for j in range(Q):
    if p[j] == 0:
        print(Rinfo[q[j]])
    else:
        print(Rinfo[q[j]]-Linfo[p[j]-1])

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

sq = [[0] * n for _ in range(n)]

for i in range(m):
    l = lr[i][0]
    r = lr[i][1]
    sq[l-1][r-1] += 1

c = [[0] * n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if j == 0:
            c[i][j] = sq[i][j]
        else:
            c[i][j] = sq[i][j] + c[i][j-1]
            
for i in range(q):
    p = pq[i][0]
    q = pq[i][1]
    ans = 0
    for j in range(p, q + 1):
        ans += c[j-1][q-1] - c[j-1][p-1]
    print(ans)

Submission status: Wrong Answer

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

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

for i in range(M):
  L, R = map(int, input().split())
  X[L-1][R-1] += 1
for i in range(N):
  for j in range(1,N+1):
    D[i][j] = D[i][j-1]+X[i][j]
for i in range(Q):
  p, q = map(int, input().split())
  p -= 1
  q -= 1
  ans = 0
  for j in range(p,q+1):
    ans += D[j][q] - D[j][p]
  print (int(ans))

Submission status: Wrong Answer

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

D = np.zeros((N,N))
for i in range(M):
  L, R = map(int, input().split())
  D[L-1][:R] += 1
for i in range(Q):
  p, q = map(int, input().split())
  p -= 1
  q -= 1
  ans = 0
  for j in range(p,q+1):
#    print (j,D[j][p],D[j][q])
    ans += D[j][p] - D[j][q]
  print (int(ans))

Submission status: Wrong Answer

Solution code:
# import sys
# input = sys.stdin.readlines()
n, m, q = map(int, input().split())

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

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

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


for i in range(n + 1):
    print(d[i])
for _ in range(q):
    l, r = map(int, input().split())
    print(d[r][r] - d[r][l - 1] - d[l - 1][r] + d[l - 1][l - 1])

Submission status: Wrong Answer

Solution code:
# import sys
# input = sys.stdin.readlines()
n, m, q = map(int, input().split())
inl = [0] * (n + 1)
outl = [0] * (n + 1)

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

for i in range(n):
    inl[i + 1] = inl[i] + inl[i + 1]
    outl[i + 1] = outl[i] + outl[i + 1]
for _ in range(q):
    l, r = map(int, input().split())
    print(inl[r] - (inl[r] - outl[r]) - (inl[l - 1] - outl[l - 1]))

Submission status: Wrong Answer

Solution code:
import numpy as np
n, m, q = map(int, input().split())
kukan = np.zeros((n+1, n+1))
for _ in range(m):
    l, r = map(int, input().split())
    kukan[r][l] += 1

# まず終点の側から考える
# iまでに終わる線分の数はi-1までの累積和
for i in range(1, n+1):
    kukan[i] += kukan[i-1]
# 次に始点の側から考える
# i以降に始まる線分の数はi-1までの総和
for i in range(1, n+1):
    kukan[:, i] += kukan[i-1]

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

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

import bisect
import numpy as np

l_all = []
r_all = []
for i in range(M):
    l_all.append(lr[i][0])
    r_all.append(lr[i][1])

l_sorted = sorted(l_all)
l_argsort = np.argsort(l_all)
r_sorted = sorted(r_all)
r_argsort = np.argsort(r_all)

for i in range(Q):
    loc1 = bisect.bisect_left(l_sorted, pq[i][0])
    loc2 = bisect.bisect_right(r_sorted, pq[i][1])

    print(np.sum(np.logical_and(l_argsort >= loc1, r_argsort < loc2)))

Submission status: Wrong Answer

Solution code:
N,M,Q = map(int, input().split())
train = []
quest = []
ans = []
for i in range(M):
    train.append([int(x) for x in input().split()])
for j in range(Q):
    quest.append([int(x) for x in input().split()])

List = []
for s in range(N):
    List.append([])

for k in range(N):
    for l in range(k+1):
        List[k].append(0)

for i in range(M):
    List[N-(train[i][1]-train[i][0]+1)][train[i][0]-1] += 1

num = N-1

while num >= 1:
    for j in range(len(List[num-1])):
        List[num-1][j] += List[num][j] + List[num][j+1]
    num -= 1
for k in range(Q):
    print( List[N-(quest[k][1]-quest[k][0]+1)][quest[k][0]-1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

    check = np.zeros((N+1, N+1))

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

    # print(check)
    for i in range(1, N+1):
        check[i] += check[i-1]
    for i in range(1, N+1):
        check[:,i] += check[:,i-1]
    # print(check)

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

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy

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

train_map = np.zeros((n, n), dtype=np.int)
s = copy.deepcopy(train_map)
numbers = []

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

for i in range(n):
    tmp = 0
    for j in range(n):
        tmp += train_map[i][j]
        s[i][j] = tmp

for i in range(q):
    st, go = map(int, input().split())
    number = 0
    for j in range(st-1, go):
        continue
        if st ==1:
            number += s[j][go-1]
            continue
        number += s[j][go-1] - s[j][st-2]

    numbers.append(number)

exit()

print(train_map[0][0])


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

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

s = copy.deepcopy(train_map)

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

for i in range(n):
    tmp = 0
    for j in range(n):
        tmp += train_map[i][j]
        s[i][j] = tmp

exit()

for i in range(q):
    st, go = map(int, input().split())
    number = 0
    """
    for j in range(st-1, go):
        if st ==1:
            number += s[j][go-1]
            continue
        number += s[j][go-1] - s[j][st-2]
    """
    numbers.append(number)

for num in numbers:
    print(num)

Submission status: Wrong Answer

Solution code:
import numpy as np
import copy

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

train_map = np.zeros((n, n), dtype=np.int)
s = copy.deepcopy(train_map)
numbers = []

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

for i in range(n):
    tmp = 0
    for j in range(n):
        tmp += train_map[i][j]
        s[i][j] = tmp

for i in range(q):
    st, go = map(int, input().split())
    number = 0
    for j in range(st-1, go):
        continue
        if st ==1:
            number += s[j][go-1]
            continue
        number += s[j][go-1] - s[j][st-2]

    numbers.append(number)

exit()

print(train_map[0][0])


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

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

s = copy.deepcopy(train_map)

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

for i in range(n):
    tmp = 0
    for j in range(n):
        tmp += train_map[i][j]
        s[i][j] = tmp

exit()

for i in range(q):
    st, go = map(int, input().split())
    number = 0
    """
    for j in range(st-1, go):
        if st ==1:
            number += s[j][go-1]
            continue
        number += s[j][go-1] - s[j][st-2]
    """
    numbers.append(number)

for num in numbers:
    print(num)