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())
trains = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    L, R = map(int, input().split())
    trains[L][R] += 1
for i in range(1, N + 1):
    for j in range(1, N + 1):
        trains[i][j] += trains[i - 1][j]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        trains[i][j] += trains[i][j - 1]
print(trains)
ans = [0] * Q
for k in range(Q):
    p, q = map(int, input().split())
    ans[k] = trains[q][q] - trains[p-1][q] - trains[q][p-1] + trains[p-1][p-1]
for A in ans:
    print(A)

Submission status: Wrong Answer

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,M,Q = map(int,input().split())

a = [0]*(N+1)
b = [0]*(N+1)
for i in range(M):
    l,r = map(int,input().split())
    a[l] += 1
    b[r] += 1

sum1 = [0]*(N+1)
sum2 = [0]*(N+1)
for i in range(1,N+1):
    sum1[i] = sum1[i-1] + a[i]
    sum2[i] = sum2[i-1] + b[i]

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

Submission status: Wrong Answer

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

# 累積和
s_s = [0]*n
s_g = [0]*n
s_s[-1] = start[-1]
s_g[0] = goal[0]
for i in range(n-1):
    s_g[i+1] = s_g[i] + goal[i+1]
for i in range(n-1)[::-1]:
    s_s[i] = s_s[i+1] + start[i]
#print(start)
#print(s_s)
#print(goal)
#print(s_g)


for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    out = m - s_s[x]
    ans = s_g[y] - out
    print(ans)

Submission status: Wrong Answer

Solution code:
# Reference: https://ikatakos.com/pot/programming_algorithm/data_structure/binary_indexed_tree
# Fenwick Tree
class BinaryIndexedTree:
    # a = [0] * n
    # O(n)
    def __init__(self, n):
        self.size = n
        self.data = [0] * (n+1)

    # return sum(a[0:i])
    # O(log(n))
    def cumulative_sum(self, i):
        ans = 0
        while i > 0:
            ans += self.data[i]
            i -= i & -i
        return ans

    # a[i] += x
    # O(log(n))
    def add(self, i, x):
        i += 1
        while i <= self.size:
            self.data[i] += x
            i += i & -i

from sys import stdin
input = stdin.buffer.readline

def main():
    n, m, q = map(int, input().split())
    lr = [tuple(map(int, input().split())) for _ in range(m)]
    pq = [(0, 0, 0)] * q
    for ind in range(q):
        i, j = map(int, input().split())
        pq[ind] = (i, j, ind)

    lr.sort(key=lambda x: x[0])
    l = [i for i, j in lr]
    r = [j for i, j in lr]
    pq.sort(key=lambda x: x[0])

    BIT = BinaryIndexedTree(n+1)
    for i in r:
        BIT.add(i, 1)

    # search r[lr_ind:]
    lr_ind = 0
    ans = [0] * q
    for left, right, pq_ind in pq:
        while lr_ind < n and l[lr_ind] < left:
            BIT.add(r[lr_ind], -1)
            lr_ind += 1

        ans[pq_ind] = BIT.cumulative_sum(right+1)

    for i in ans:
        print(i)

main()

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
sta_num = [0] * (N+1)
fin_num = [0] * (N+1)
for _ in range(M):
    s,f = map(int, input().split())
    sta_num[s] += 1
    fin_num[f] += 1
for i in range(1, N+1):
    sta_num[i] += sta_num[i-1]
    fin_num[i] += fin_num[i-1]
for _ in range(Q):
    a,b = map(int, input().split())
    print(fin_num[b] - sta_num[a-1])

Submission status: Wrong Answer

Solution code:


def read_int():
    return int(input().strip())


def read_ints():
    return list(map(int, input().strip().split(' ')))


def solve():
    N, M, Q = read_ints()
    dp = [ [0 for _ in range(N)] for _ in range(N) ]
    left = [0 for _ in range(N)]
    right = [0 for _ in range(N)]
    length_to_pairs = [[] for _ in range(N)]

    for _ in range(M):
        L, R = read_ints()
        L -= 1
        R -= 1
        length_to_pairs[R-L].append((L, R))
        if L == R:
            dp[L][L] = right[L] = left[L] = 1

    for l in range(1, N):
        for i in range(N-l):
            dp[i][i+l] += right[i]+left[i+l]
            if l > 1:
                dp[i][i+l] += dp[i+1][i+l-1]
        for L, R in length_to_pairs[l]:
            dp[L][R] += 1
            right[L] += 1
            left[R] += 1

    for _ in range(Q):
        q0, q1 = read_ints()
        print(dp[q0-1][q1-1])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
x=[[0]*N for _ in range(N)]
c=x
for i in range(M):
  l,r=map(lambda x:int(x)-1,input().split())
  x[l][r]+=1
for i in range(N):
  for j in range(N):
    if j==1:
      c[i][j]=x[i][j]
    else:
      c[i][j]=c[i][j-1]+x[i][j]
for i in range(Q):
  p,q=map(lambda x:int(x)-1,input().split())
  count=0
  for i in range(p,q+1):
    if p!=0:
      count+=c[i][q]-c[i][p-1]
    else:
      count+=c[i][q]
  print(count)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
S = [0]*(N+2)
O = [0]*(N+2)

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

for i in range(1, N+2):
    O[i] = O[i-1] + O[i]
    S[i] = S[i-1] + S[i]

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

Submission status: Wrong Answer

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

lr=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    li,ri=map(int,input().split())
    lr[li][ri]+=1
    
for i in range(n+1):
    asum=0
    for j in range(n+1):
        asum+=lr[i][j]
        lr[i][j]=asum
            
for i in range(q):
    pi,qi=map(int,input().split())
    pi-=1
    qi-=1
    asum=0
    for j in range(pi,qi+1):
        asum+=lr[j][qi]-lr[j][j-1]
    print(asum)

Submission status: Wrong Answer

Solution code:
#左側+3*10**5、右側+1をして、クエリにO(1)で答える。
from collections import defaultdict
import sys
#初期入力
input = sys.stdin.readline  #文字列では使わない
N,M,Q = map(int, input().split())

#L =[0]*(N+1)
#R =[0]*(N+1)
L =defaultdict(int)
R =defaultdict(int)
for i in range(M):
    l,r = map(int, input().split())
    for il in range(1,l+1):
        L[il] +=1
    for ir in range(r,N+1):
        R[ir] +=1

#クエリを入力⇒答える
for i in range(Q):
    p,q = map(int, input().split())
    """
    if L[p] < R[q]:
        print(L[p],"L")
    else:
        print(R[q],"R")
    """
    ans =min(L[p],R[q])
    print(ans)

Submission status: Wrong Answer

Solution code:
#左側+3*10**5、右側+1をして、クエリにO(1)で答える。

import sys
#初期入力
input = sys.stdin.readline  #文字列では使わない
N,M,Q = map(int, input().split())

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

#クエリを入力⇒答える
for i in range(Q):
    p,q = map(int, input().split())
    """
    if L[p] < R[q]:
        print(L[p],"L")
    else:
        print(R[q],"R")
    """
    ans =min(L[p],R[q])
    print(ans)

Submission status: Wrong Answer

Solution code:
# 初期入力
from bisect import bisect_right
import sys
input = sys.stdin.readline  #文字列では使わない
N,M,Q = map(int, input().split())
LR =[[0]*(N) for i in range(N)]
LR_dic ={i:[] for i in range(1,N+1)}
for i in range(M):
    L,R = map(int, input().split())
    LR_dic[L].append(R)

#pq =[[0]*(N) for i in range(N)]
count =[]
for i in range(Q):
    cot =0
    p,q = map(int, input().split())
    for j in range(p,q+1):
        cot +=bisect_right(LR_dic[j],q)
    count.append(cot)
#print(LR_dic)
print(*count,sep="\n")

Submission status: Wrong Answer

Solution code:
from copy import deepcopy

N,M,Q=map(int,input().split())
data=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
  l, r =map(int,input().split())
  data[l][r] = 1
  
cum = []
for i in range(N+1):
  tmp = [0]
  for j in range(N+1):
    tmp.append(data[i][j]+tmp[-1])
  cum.append(tmp)

cum2 = [cum[-1]]
for i in range(N,0,-1):
  tmp = deepcopy(cum2[-1])
  for j in range(1,N+2):
    tmp[j] += cum[i-1][j]
  cum2.append(tmp)
cum2 = cum2[::-1]

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

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from itertools import accumulate
import numpy as np

n, m, q = list(map(int, input().split()))
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]

data = [[0]*500 for i in range(500)]
# data = [[0]*10 for i in range(10)]

for l, r in lr:
    data[l-1][r-1] += 1


# for i in range(0, 500):
#     data[i] = list(accumulate(data[i]))

# print(data)
# for p, q in pq:
#     ans = 0
#     if p == 1:
#         for i in range(p-1, q-1+1):
#             ans += data[i][q-1]
#     else:
#         for i in range(p-1, q-1+1):
#             ans += data[i][q-1]-data[i][p-1-1]
#     print(ans)

data = np.array(data)

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

print(data[:10, :10])
for p, q in pq:
    ans = 0
    if p == 1:
        ans = data[q-1][q-1]
    else:
        ans = data[q-1][q-1]-data[p-1-1][p-1-1]
    print(ans)
# for p, q in pq:
#     ans = 0
#     if p == 1:
#         for i in range(p-1, q-1+1):
#             ans += data[i][q-1]
#     else:
#         for i in range(p-1, q-1+1):
#             ans += data[i][q-1]-data[i][p-1-1]
#     print(ans)

Submission status: Wrong Answer

Solution code:
N,M,Q = list(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())))

s = [[0 for i in range(N)] for j in range(N)]

for i in range(M):
    start = LR[i][0]
    goal = LR[i][1]
    for y in range(goal-1, N):
        for x in range(start-1, N):
            s[y][x] += 1

for i in range(Q):
    p = pq[i][0]
    q = pq[i][1]
    if p > 1 and q > 1:
        answer = s[q-1][q-1] - s[q-1][p-1-1] - s[p-1-1][q-1] + s[p-1-1][p-1-1]
    elif p == 1 and q > 1:
        answer = s[q-1][q-1]
    print(answer)

Submission status: Wrong Answer

Solution code:
from bisect import bisect

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

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

for _ in range(M):
  L, R = map(int, input().split())
  G[L].append(R)

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

Submission status: Wrong Answer

Solution code:
import sys
from itertools import accumulate


def main():
    input = sys.stdin.buffer.readline
    n, m, q = map(int, input().split())
    l_cnt = [0] * (n + 1)
    r_cnt = [0] * (n + 1)
    for _ in range(m):
        l, r = map(int, input().split())
        l_cnt[l] += 1
        r_cnt[r] += 1
    l_acc = list(accumulate(l_cnt))
    r_acc = list(accumulate(r_cnt))
    for _ in range(q):
        p, q = map(int, input().split())
        print(r_acc[q] - l_acc[p - 1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
N, M , Q = map(int, input().split())
import numpy as np
Rui = [[0]*N]*N
Rui = np.array(Rui)

for i in range (0, M):
	A, B = map(int, input().split())
	for j in range (0,A):
		Rui[j]+=1
	for k in range (B-1, N):
		Rui[k]-=1

for i in range (0, Q):
	A, B = map(int, input().split())
	print(Rui[A-1][B-1])

Submission status: Wrong Answer

Solution code:
from bisect import bisect_right
N, M, Q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(M)]

lr.sort()
lst = [[] for _ in range(N)]

for l, r in lr:
    for i in range(l+1):
        lst[i-1].append(r-1)
for i in range(N):
    lst[i].sort()

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

Submission status: Wrong Answer

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 
#mod = 998244353
from decimal import *
#import numpy as np
#decimal.getcontext().prec = 10

N, M, Q = MAP()
LR = [LIST() for _ in range(M)]
pq = [LIST() for _ in range(Q)]

l = [0]*(N+2)
r = [0]*(N+2)
for L, R in LR:
	l[L] += 1
	r[R] += 1

l = list(accumulate(l))
r = list(accumulate(r))

for p, q in pq:
	ans = M - max(l[p-1], r[-1]-r[q])
	print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M, Q = mapint()
query = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l, r = mapint()
    query[l][r] += 1
from itertools import accumulate
for i in range(N+1):
    query[i] = list(accumulate(query[i]))
for i in range(1, N+1):
    for j in range(N+1):
        query[i][j] += query[i-1][j]

for _ in range(Q):
    p, q = mapint()
    print(query[N][q]-query[p-1][r-1])

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from operator import add, mul
n,m,q=map(int,input().split())

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

#import numpy as np
#b=np.array(b)
#print(a)
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    #a[(r-1):n,0:l]+=1
    for j in range(r-1,n):
        for k in range(l):
            a[j][k]+=1
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[l-1][r-1]+=1

#print(a)

for i in range(n):
    a[i]=list(accumulate(a[i]))

#print(a)

for i in range(n):
    for j in range(n-i):
        a[n-i-j-2][n-i-1]+=a[n-i-j-1][n-i-1]
        #print(a)

#print(a)

'''
for l in range(n):
    for r in range(l,n):
        temp=a[r][l]
        for i in range(r,n):
            for j in range(0,l+1):
                b[i][j]+=temp
        #b[r:n,0:l+1]+=temp
'''
#print(a)
#print(b)

for i in range(q):
    P,Q=map(int,input().split())
    print(a[(P-1)][(Q-1)])
'''
for i in range(que):
    p,q=MI()
    if p==1:
        ans=lis[q-1][q-1]
    else:
        ans=lis[q-1][q-1]-lis[p-2][q-1]
    print(ans)
'''

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
from operator import add, mul
n,m,q=map(int,input().split())

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

#import numpy as np
#b=np.array(b)
#print(a)
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    #a[(r-1):n,0:l]+=1
    for j in range(r-1,n):
        for k in range(l):
            a[j][k]+=1
'''
for i in range(m):
    l,r=map(int,input().split())
    #print(a[(r-1):n,0:l])
    a[l-1][r-1]+=1

#print(a)

for i in range(n):
    a[i]=list(accumulate(a[i]))

#print(a)

for i in range(n):
    for j in range(n-i):
        a[n-i-j-2][n-i-1]+=a[n-i-j-1][n-i-1]
        #print(a)

print(a)

'''
for l in range(n):
    for r in range(l,n):
        temp=a[r][l]
        for i in range(r,n):
            for j in range(0,l+1):
                b[i][j]+=temp
        #b[r:n,0:l+1]+=temp
'''
#print(a)
#print(b)

for i in range(q):
    P,Q=map(int,input().split())
    print(a[(P-1)][(Q-1)])
'''
for i in range(que):
    p,q=MI()
    if p==1:
        ans=lis[q-1][q-1]
    else:
        ans=lis[q-1][q-1]-lis[p-2][q-1]
    print(ans)
'''

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
from collections import *

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

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

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

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

Submission status: Wrong Answer

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

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

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

for j in range(n+1):
  for i in range(n):
    d[j][i+1]=d[j][i]
    
for qq in range(q):
  x,y=map(int,input().split())
  print(d[y][y]-d[y][x-1]-d[x-1][y]+d[x-1][x-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_)]
lr.sort(key=lambda x:x[0])
left_=[0]*(n+1)  # left[i]:左からi個目までの町を通る列車
right_=[0]*(n+1) # right[i]:右からi個目までの町を通る列車
for l,r in lr:
  left_[l]+=1
  right_[n-r+1]+=1
tmpl=0
tmpr=0
left=[]
right=[]
for i in range(n+1):
  tmpl+=left_[i]
  tmpr+=right_[i]
  left.append(tmpl)
  right.append(tmpr)
for p,q in pq:
  a=m-left[p-1]-right[n-q]
  print(a)

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d

n, m, q = map(int, input().split())
trains = []
for _ in range(m):
    l, r = map(int, input().split())
    trains.append([l, r])

queries = []
for _ in range(q):
    p, q2 = map(int, input().split())
    queries.append([p, q2])

s = [[0] * (n + 1) for _ in range(n + 1)]
a = [[0] * n for _ in range(n)]

for l, r in trains:
    a[l - 1][r - 1] = a[l - 1][r - 1] + 1

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

# print(a)
# print(s)
for p, q in queries:
    print(s[q][q] - s[p - 1][q] - s[q][p - 1] + s[p - 1][q - 1])

Submission status: Wrong Answer

Solution code:
# https://atcoder.jp/contests/abc106/tasks/abc106_d

n, m, q = map(int, input().split())
trains = []
for _ in range(m):
    l, r = map(int, input().split())
    trains.append([l, r])

queries = []
for _ in range(q):
    p, q2 = map(int, input().split())
    queries.append([p, q2])

s = [[0] * (n + 1) for _ in range(n + 1)]
a = [[0] * n for _ in range(n)]

for l, r in trains:
    a[l - 1][r - 1] = a[l - 1][r - 1] + 1

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

# print(a)
# print(s)
for p, q in queries:
    print(s[q][q] - s[p - 1][q - 1])

Submission status: Wrong Answer

Solution code:
import numpy as np

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

left = np.zeros(shape=N + 1, dtype=int)
right = np.zeros(shape=N + 1, dtype=int)
for _ in range(M):
    L, R = map(int, input().split(' '))
    left[L] += 1
    right[R] += 1

left = left.cumsum()
right = right.cumsum()

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

Submission status: Wrong Answer

Solution code:
from itertools import accumulate

N,M,Q = map(int,input().split())
al = [0]*(N+2)
bl = [0]*(N+2)
for i in range(M):
  L,R = map(int,input().split())
  al[R] += 1
  bl[L] += 1
  
al = list(accumulate(al))
bl = list(accumulate(bl))

for i in range(Q):
  L,R = map(int,input().split())
  print(al[R]-bl[L-1])

Submission status: Wrong Answer

Solution code:
from sys import stdin
import numpy as np
N,M,Q = [int(x) for x in stdin.readline().rstrip().split()]

cumsum_2d = np.zeros([N+1,N+1]) 
for i in range(M):
    L,R = [int(x) for x in stdin.readline().rstrip().split()]
    cumsum_2d[L,R] += 1
    
for i in range(Q):
    p,q = [int(x) for x in stdin.readline().rstrip().split()]
    sum_all = cumsum_2d[0:q+1,0:q+1].sum()
    sum1 = cumsum_2d[0:p,0:p].sum()
    sum2 = cumsum_2d[p:q+1,0:p].sum()
    sum3 = cumsum_2d[0:p,p:q+1].sum()
    print(int(sum_all+sum1-sum2-sum3))

Submission status: Wrong Answer

Solution code:
def solve():
    N, M, Q, *x = map(int, open(0).read().split())
    LR, pq = x[:2*M], x[2*M:]

    mat = [[0] * (N + 1) for _ in range(N + 1)]
    c = [[0] * (N + 1) for _ in range(N + 1)]
    # ここでマトリックス作ってる
    for l, r in zip(*[iter(LR)] * 2):
        mat[l][r] += 1
    # 累積和のためのマトリックス作成
    for l in range(N+1):
        for r in range(N+1):
            for k in range(r+1):
                c[l][r] += mat[l][k]
    # S計算
    for p, q in zip(*[iter(pq)] * 2):
        print(c[p][q] - c[p][p-1] + c[q][q] - c[1][p-1])


if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
areas = [[0 for _ in range(N + 2)] for _ in range(N + 2)]

for _ in range(M):
    left, right = map(int, input().split())
    areas[left][right] += 1
# print(areas)
for i in range(1, N + 2):
    for j in range(1, N + 2):
        areas[i][j] += areas[i][j - 1]
print(areas)
for _ in range(Q):
    left, right = map(int, input().split())
    cost = 0
    for i in range(left, right + 1):
        cost += areas[i][right] - areas[i][left - 1]
    print(cost)

Submission status: Wrong Answer

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

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

print(graph)

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

Submission status: Wrong Answer

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

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

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

Submission status: Wrong Answer

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

print(graph)

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

print(graph)

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import numpy as np
import sys

input=sys.stdin.readline

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

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

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

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


print(train_array)

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

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

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

print(train_array_ruisekiwa)

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

    print(ans)

Submission status: Wrong Answer

Solution code:
import numpy as np

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

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

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

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


#print(train_array)

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

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

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

#print(train_array_ruisekiwa)

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

    print(ans)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
llist=[0]*N
rlist=[0]*N
cuml=[0]*N
cumr=[0]*N
query=[]
for i in range(M):
    l,r=map(int,input().split())
    l=l-1
    r=r-1
    llist[l]=llist[l]+1
    rlist[r]=rlist[r]+1
#print(llist,rlist)
query=[list(map(int,input().split())) for _ in range(Q)]
cumr[0]=rlist[0]
cuml[N-1]=llist[N-1]
for i in range(N-1):
    cumr[i+1]=cumr[i]+rlist[i+1]
    cuml[N-i-2]=cuml[N-i-1]+llist[N-i-2]
#print(cuml,cumr)
#print(query)
for i in query:
    l=i[0]-1
    r=i[1]-1
    print((cuml[l]+cumr[r])-M)

Submission status: Wrong Answer

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

n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]
data = [[0] * n for _ in range(n)]
for l, r in lr:
    data[l - 1][r - 1] += 1


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

for s in range(n):
    for t in range(n):
        if t == 0:
            ex[s][t] = data[s][0]
        else:
            ex[s][t] = ex[s][t - 1] + data[s][t]
"""
for A in range(n):
    print(data[A])
print("-------------")

for B in range(n):
    print(ex[B])
"""

for p, q in pq:
    ans = 0
    if p == 1:
        for i in range(p - 1, q):
            ans += ex[i][q - 1]
    else:
        for i in range(p - 1, q):
            ans += ex[i][q - 1] - ex[i][p - 1]
    print(ans)

Submission status: Wrong Answer

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

n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]
data = [[0] * n for _ in range(n)]
for l, r in lr:
    data[l - 1][r - 1] += 1


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

for s in range(n):
    for t in range(n):
        if t == 0:
            ex[s][t] = data[s][0]
        else:
            ex[s][t] = ex[s][t - 1] + data[s][t]
"""
for A in range(n):
    print(data[A])
print("-------------")

for B in range(n):
    print(ex[B])
"""

for p, q in pq:
    ans = 0
    if p == 1:
        for i in range(n):
            ans += ex[i][q - 1]
    else:
        for i in range(p-1, q):
            ans += ex[i][q - 1] - ex[i][p - 1]
    print(ans)

Submission status: Wrong Answer

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

n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]
data = [[0] * n for _ in range(n)]
for l, r in lr:
    data[l - 1][r - 1] += 1


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

for s in range(n):
    for t in range(n):
        if t == 0:
            ex[s][t] = data[s][0]
        else:
            ex[s][t] = ex[s][t - 1] + data[s][t]
"""
for A in range(n):
    print(data[A])
print("-------------")

for B in range(n):
    print(ex[B])
"""
for p, q in pq:
    ans = 0
    if p == 1 and q == n:
        for i in range(n):
            ans += ex[i][q - 1]
    else:
        for i in range(p-1, q):
            ans += ex[i][q - 1] - ex[i][p - 1]
    print(ans)

Submission status: Wrong Answer

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

n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for _ in range(m)]
pq = [list(map(int, input().split())) for _ in range(q)]
data = [[0] * n for _ in range(n)]
for l, r in lr:
    data[l - 1][r - 1] += 1


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

for s in range(n):
    for t in range(n):
        if t == 0:
            ex[s][t] = data[s][0]
        else:
            ex[s][t] = ex[s][t - 1] + data[s][t]
"""
for A in range(n):
    print(data[A])
print("-------------")

for B in range(n):
    print(ex[B])
"""
for p, q in pq:
    ans = 0
    for i in range(p-1, q):
        ans += ex[i][q - 1] - ex[i][p - 1]
    print(ans)

Submission status: Wrong Answer

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


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


main()