Problem:


Score: 400 points

Problem Statement

In Takahashi Kingdom, there is a east-west railroad and N cities along it, numbered 1, 2, 3, ..., N from west to east.
A company called AtCoder Express possesses M trains, and the train i runs from City L_i to City R_i (it is possible that L_i = R_i).
Takahashi the king is interested in the following Q matters:

The number of the trains that runs strictly within the section from City p_i to City q_i, that is, the number of trains j such that p_i \leq L_j and R_j \leq q_i.

Although he is genius, this is too much data to process by himself. Find the answer for each of these Q queries to help him.

Constraints

N is an integer between 1 and 500 (inclusive).

M is an integer between 1 and 200 \ 000 (inclusive).

Q is an integer between 1 and 100 \ 000 (inclusive).

1 \leq L_i \leq R_i \leq N (1 \leq i \leq M)

1 \leq p_i \leq q_i \leq N (1 \leq i \leq Q)

Input

Input is given from Standard Input in the following format:

N M Q
L_1 R_1
L_2 R_2
:
L_M R_M
p_1 q_1
p_2 q_2
:
p_Q q_Q

Output

Print Q lines. The i-th line should contain the number of the trains that runs strictly within the section from City p_i to City q_i.

Sample Input 1

2 3 1
1 1
1 2
2 2
1 2

Sample Output 1

3

As all the trains runs within the section from City 1 to City 2, the answer to the only query is 3.

Sample Input 2

10 3 2
1 5
2 8
7 10
1 7
3 10

Sample Output 2

1
1

The first query is on the section from City 1 to 7. There is only one train that runs strictly within that section: Train 1.
The second query is on the section from City 3 to 10. There is only one train that runs strictly within that section: Train 3.

Sample Input 3

10 10 10
1 6
2 9
4 5
4 7
4 7
5 8
6 6
6 7
7 9
10 10
1 8
1 9
1 10
2 8
2 9
2 10
3 8
3 9
3 10
1 10

Sample Output 3

7
9
10
6
8
9
6
7
8
10



Sample input:
2 3 1
1 1
1 2
2 2
1 2


Sample output:
3

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

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

#print(L)

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

Submission status: Wrong Answer

Solution code:
import sys
import numpy as np

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    N, M, Q = map(int, input().split())
    start = [0] * (N + 1)
    end = [0] * (N + 1)

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

    # i番目もしくはi番目後に区間が始まる線路の数
    S = [0] * (N + 1)
    S[1] = M
    for i in range(1, N):
        S[i + 1] = S[i] - start[i]

    # i番目もしくはi番目後に区間が終わる線路の数
    E = [0] * (N + 2)
    for i in range(N, 1, -1):
        E[i] = end[i] + E[i + 1]

    ans = []
    for _ in range(Q):
        p, q = map(int, input().split())
        ans.append(S[p] - E[q + 1])

    for a in ans:
        print(a)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n, m, q = [int(x) for x in input().split()]

t_list = []
c_list = []
for _ in range(n):
    t_list.append([0] * n)
    c_list.append([0] * n)

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

for i in range(n):
    for j in range(n):
        if j == 0:
            c_list[i][j] = t_list[i][j]
            continue

        c_list[i][j] = t_list[i][j] + c_list[i][j - 1]

for _ in range(q):
    l, r = [int(x) for x in input().split()]
    ans = 0
    for j in range(l - 1, r):
        if r == 1:
            ans += c_list[j][0]
        elif l == 1:
            ans += c_list[j][r - 1]
        else:
            ans += c_list[j][r - 1] - c_list[j][l - 1]
    print(ans)

Submission status: Wrong Answer

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

import sys
# import math
# from string import ascii_lowercase, ascii_upper_case, ascii_letters, digits, hexdigits
# import re                                    # re.compile(pattern) => ptn obj; p.search(s), p.match(s), p.finditer(s) => match obj; p.sub(after, s)
# from operator import itemgetter              # itemgetter(1), itemgetter('key')
# from collections import deque                # deque class. deque(L): dq.append(x), dq.appendleft(x), dq.pop(), dq.popleft(), dq.rotate()
# from collections import defaultdict          # subclass of dict. defaultdict(facroty)
# from collections import Counter              # subclass of dict. Counter(iter): c.elements(), c.most_common(n), c.subtract(iter)
# from heapq import heapify, heappush, heappop # built-in list. heapify(L) changes list in-place to min-heap in O(n), heappush(heapL, x) and heappop(heapL) in O(lgn).
# from heapq import nlargest, nsmallest        # nlargest(n, iter[, key]) returns k-largest-list in O(n+klgn).
# from itertools import count, cycle, repeat   # count(start[,step]), cycle(iter), repeat(elm[,n])
# from itertools import groupby                # [(k, list(g)) for k, g in groupby('000112')] returns [('0',['0','0','0']), ('1',['1','1']), ('2',['2'])]
# from itertools import starmap                # starmap(pow, [[2,5], [3,2]]) returns [32, 9]
# from itertools import product, permutations  # product(iter, repeat=n), permutations(iter[,r])
# from itertools import combinations, combinations_with_replacement
# from itertools import accumulate             # accumulate(iter[, f])
# from functools import reduce                 # reduce(f, iter[, init])
# from functools import lru_cache              # @lrucache ...arguments of functions should be able to be keys of dict (e.g. list is not allowed)
# from bisect import bisect_left, bisect_right # bisect_left(a, x, lo=0, hi=len(a)) returns i such that all(val<x for val in a[lo:i]) and all(val>-=x for val in a[i:hi]).
# from copy import deepcopy                    # to copy multi-dimentional matrix without reference
# from fractions import gcd                    # for Python 3.4 (previous contest @AtCoder)


def main():
    mod = 1000000007                # 10^9+7
    inf = float('inf')              # sys.float_info.max = 1.79...e+308
    # inf = 2 ** 64 - 1               # (for fast JIT compile in PyPy) 1.84...e+19
    sys.setrecursionlimit(10**6)    # 1000 -> 1000000
    def input(): return sys.stdin.readline().rstrip()
    def ii():    return int(input())
    def mi():    return map(int, input().split())
    def mi_0():  return map(lambda x: int(x)-1, input().split())
    def lmi():   return list(map(int, input().split()))
    def lmi_0(): return list(map(lambda x: int(x)-1, input().split()))
    def li():    return list(input())
    
    
    n, m, q = mi()
    train = [lmi() for _ in range(m)]
    query = [lmi() for _ in range(q)]

    """
    電車の運行区間のうち開始地点を x 座標で、終着地点を y 座標で表し二次元座標で管理する
    [i, j] 区間内で運行する電車は 0 <= x <= i, 0 <= y <= j の長方形区間内の全ての電車である
    """
    coordinate = [[0] * (n + 1) for _ in range(n + 1)]
    for start, end in train:
        coordinate[start][end] += 1
    
    # 二次元累積和に
    for i in range(n):
        for j in range(n):
            coordinate[i+1][j+1] += coordinate[i][j+1] + coordinate[i+1][j] - coordinate[i][j]
    
    # 各クエリに O(1) で答えられる！
    for l, r in query:
        print(coordinate[r][r] - coordinate[l-1][r] - coordinate[r][l-1] + coordinate[l-1][r-1])


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

class Cumulative_Sum_2D:
    def __init__(self, a):
        lai = len(a)
        laj = len(a[0])
        self.s = [[0] * (laj + 1) for _ in range(lai + 1)]
        for i in range(lai):
            for j in range(laj):
                self.s[i+1][j+1] = self.s[i+1][j] + a[i][j]
        for i in range(lai):
            for j in range(laj):
                self.s[i+1][j+1] += self.s[i][j+1]
    def sum(self, li, lj, ri, rj):
        s = self.s
        return s[ri][rj] - s[li][rj] - s[ri][lj] + s[li][lj]

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

cs = Cumulative_Sum_2D(a)
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    print(cs.sum(p,p,q+1,q+1))

Submission status: Wrong Answer

Solution code:
def main():
    n, m, Q = map(int, input().split())
    Train= [[0 for _ in range(n)] for _ in range(n)]
    
    for i in range(m):
        l, r = map(int, input().split())
        l, r = l - 1, r - 1
        Train[l][r] += 1
    
    P_Train = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(n):
        tmp = 0
        for j in range(n):
            tmp += Train[i][j]
            P_Train[i][j] = tmp

    for i in range(Q):
        p, q = map(int, input().split())
        p, q = p - 1, q - 1
        ans = solve(P_Train, n, p, q)
        print(ans)

def solve(P_Train, n, p, q):
    ans = 0
    for i in range(p, q + 1):
        ans += P_Train[i][q] - P_Train[i][p]
    return ans


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

train = [[0 for _ in range(501)] for _ in range(501)]
train_total = [[0 for _ in range(501)] for _ in range(501)]
query = []

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

for j in range(q):
    x, y = map(int, input().split())
    query.append([x, y])

for left in range(0, 501):
    cnt = 0
    for right in range(0, 501):
        cnt += train[left][right]
        train_total[left][right] = cnt

for left, right in query:
    total = 0
    for row in range(left, right+1):
        num2 = train_total[row][right]
        num1 = train_total[row][left]
        total += (num2 - num1)
    print(total)

Submission status: Wrong Answer

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

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

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

ans = []
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    ans.append(A[q][q] - A[q][p] - A[p][q] - A[p][p])
print(*ans, sep='\n')

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
from itertools import accumulate
wa = [[0]*(N+1) for _ in range(N+1)]
import numpy as np

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

cwa = np.cumsum(np.cumsum(wa, axis=0), axis=1).tolist()
for i in range(Q):
    p, q = map(int, input().split())
    ans = cwa[N][q]-cwa[p-1][r]
    print(ans)

Submission status: Wrong Answer

Solution code:
# 区間が出る問題は累積和を疑おう
N, M, Q = map(int, input().split())
trainstart = [0] * N
trainend = [0] * N
for i in range(M):
    l, r = map(int, input().split())
    trainstart[l - 1] += 1
    trainend[r - 1] += 1
area = []
for i in range(Q):
    p, q = map(int, input().split())
    # インデックスを１からスタートにした方が便利
    area.append([p, q])

startsum = [0]
for i in range(N):
    # [0, 2, 3]
    # 都市0以前に始点がある鉄道0
    # 都市1以前に始点がある鉄道2...
    startsum.append(startsum[i] + trainstart[i])
endsum = [0]
for i in range(N):
    # [0, 1, 3]
    # 都市0以前に終点がある鉄道0
    # 都市1以前に終点がある鉄道1...
    endsum.append(endsum[i] + trainend[i])
ans = []
# 全体から例外を引いていく
for i in range(Q):
    """
    ＃＃＃＃＃
    　＃＃＃＃＃＃＃
    　　　　　　＃＃＃＃
    １２③４５６７８９⑩
    3 ~ 10の区間に含まれる鉄道の数は
    10までに終点がある鉄道の数 - (3 - 1)以前に始点がある鉄道の数
    (3 - 1)以前に始点がある鉄道の場合
    ①(3 - 1)以前に終点がある
    ②3 ~ 10に終点がある
    いずれにせよ鉄道が3 ~ 10の内に収まらずカウント対象外なため
    """
    ans.append(endsum[area[i][1]] - startsum[area[i][0] - 1])
for i in ans:
    print(i)

Submission status: Wrong Answer

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

L = [0]*n
R = [0]*n
for i in range(m):
  p,q = map(int,input().split())
  L[p-1] += 1
  R[q-1] += 1
    
cum_l = [0]*(n+1)
cum_r = [0]*(n+1)  
for i in range(n):
  cum_l[i+1] = cum_l[i] + L[i]
  cum_r[i+1] = cum_r[i] + R[i]

for j in range(Q):
  p,q = map(int,input().split())
  print(min(cum_l[q]-cum_l[p-1], cum_r[q]-cum_r[p-1]))

Submission status: Wrong Answer

Solution code:
import sys
# import math
# import bisect
import numpy as np


# import copy
# import heapq
# from collections import deque
# import decimal

# sys.setrecursionlimit(100001)
# INF = sys.maxsize
# MOD = 10 ** 9 + 7

# ===CODE===
def main():
    n,m,q = map(int,input().split())
    ruisekiwa_s = [0 for _ in range(n+1)]
    ruisekiwa_t = [0 for _ in range(n+1)]
    for _ in range(m):
        l,r = map(int, input().split())
        ruisekiwa_s[l]+=1
        ruisekiwa_t[r]+=1

    for i in range(1, n+1):
        ruisekiwa_s[i] += ruisekiwa_s[i-1]
        ruisekiwa_t[i] += ruisekiwa_t[i-1]

    for _ in range(q):
        s,t = map(int,input().split())
        ans = ruisekiwa_t[t] - ruisekiwa_s[s-1]
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:

import numpy as np
def resolve():
    N, M, Q = map(int, input().split())
    S = np.zeros(((N+1),(N+1)))
    for _ in range(M):
        l, r = map(int, input().split())
        # L,Rの区間にある本数
        S[l][r] += 1

    # ゼータ変換（横縦累積和） axis=1:横, axis=0:縦
    S = np.cumsum(S, axis=1).cumsum(axis=0)

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

if __name__ == "__main__":
    resolve()

Submission status: Wrong Answer

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

# for i in range(N):
#     for j in range(N):
#         X[i+1][j+1] += X[i][j+1] + X[i+1][j]
# print(*X, sep='\n')
# print('')

for i in range(N+1):
    for j in range(N):
        X[i][j+1] += X[i][j]
# print(*X, sep='\n')

for i in range(N+1):
    for j in range(N):
        # print(i, j)
        X[j+1][i] += X[j][i]
ans = []
for _ in range(Q):
    p, q = map(int, input().split())
    ans.append(X[q][q] - X[q][p-1] - X[p-1][q] + X[p-1][p-1])
    # print(ans)
# print(*X, sep='\n')
print(*ans, sep='\n')

Submission status: Wrong Answer

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

# for i in range(N):
#     for j in range(N):
#         X[i+1][j+1] += X[i][j+1] + X[i+1][j]
# print(*X, sep='\n')
# print('')

for i in range(N+1):
    for j in range(N):
        X[i][j+1] += X[i][j]
# print(*X, sep='\n')

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

for _ in range(Q):
    p, q = map(int, input().split())
    ans = X[q][q] - X[q][p-1] - X[p-1][q] + X[p-1][p-1]
    print(ans)
# print(*X, sep='\n')

Submission status: Wrong Answer

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

grid = [[0] * (N + 1) for _ in range(N + 1)]
for l, r in X:
    grid[l][r] += 1

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

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

for p, q in Y:
    print(grid[q][q] + grid[p - 1][p - 1] + grid[p - 1][q] + grid[q][p - 1])

Submission status: Wrong Answer

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

grid = [[0] * (N + 1) for _ in range(N + 1)]
for l, r in X:
    grid[l][r] += 1

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

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

for p, q in Y:
    print(grid[p][q] + grid[p - 1][q - 1] + grid[p - 1][q] + grid[p][q - 1])

Submission status: Wrong Answer

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

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

# 累積和
# ２次元累積和
c=[[0]*(n+1) for i in range(n+1)]
for i,j in a:
    c[i][j]+=1

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

for i,j in b:
    ans=c[j][j]-c[i-1][j]-c[j][i-1]+c[i][i]
    print(ans)

Submission status: Wrong Answer

Solution code:
S = input()
ans = 0
for i in range(len(S)):
    for j in range(i,len(S)):
        print(S[i:j+1])
        flag = True
        for k in S[i:j+1]:
            if not (k=='A' or k=='C' or k=='G' or k=='T'):
                flag = False
                break
        if flag:
            ans = max(ans, len(S[i:j+1]))
print(ans)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
r = [[0 for i in range(N)] for j in range(N)]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
        if j - 1> 0:
            q = q - r[j-1][j-2]
    print(q)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
        if j - 1> 0:
            q = q - r[j-1][j-2]
    print(q)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if j > 0:
            r[i][j] = r[i][j-1] + p[i][j]
        else:
            r[i][j] = p[i][j]
for i in range(len(Qlist)):
    q = 0
    print(q)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
        if j - 1> 0:
            q = q - r[j-1][j-2]
    print(q)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        if j > 0:
            r[i][j] = r[i][j-1] + p[i][j]
        else:
            r[i][j] = p[i][j]
for i in range(len(Qlist)):
    q = 0
    print(q)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(N):
    for j in range(N):
        r[i][j] = r[i][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
    print(q)
print(p)
print(r)

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

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

for q in range(n):
    for p in reversed(range(1,n)):
        M[q][p-1]+=M[q][p]
for p in range(n):
    for q in range(n-1):
        M[q+1][p]+=M[q][p]        

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

Submission status: Wrong Answer

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

for q in range(n):
    for p in reversed(range(1,n)):
        M[q][p-1]+=M[q][p]
for p in range(n):
    for q in range(n-1):
        M[q+1][p]+=M[q][p]        

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

Submission status: Wrong Answer

Solution code:
N,M,Q = [int(x) for x in input().split()]
ruil = [0] * (N+1)
ruir = [0] * (N+1)
for i in range(M):
    l,r = [int(x) for x in input().split()]
    ruil[l] += 1
    ruir[r] += 1
for i in range(1,N+1):
    ruil[i] = ruil[i-1] + ruil[i]
    ruir[i] = ruir[i-1] + ruir[i]
print(ruil,ruir)
for i in range(Q):
    p,q = [int(x) for x in input().split()]
    if p == q:
      print(ruil[p] - ruil [q-1])
    else:
      print(ruil[p] - ruir[q-1] + ruil[p+1] - ruil[q])

Submission status: Wrong Answer

Solution code:
class BIT_2D():
    def __init__(self,h,w):
        self.h=h
        self.w=w 
        self.table=[[0]*(w+1) for _ in range(h+1)]

    def add(self,i,j,x):
        init_j=j
        while i<=self.h:
            while j<=self.w:
                self.table[i][j]+=x
                j+=(j&-j)
            j=init_j
            i+=(i&-i)
        return None

    def sum(self,i,j):
        s=0
        init_j=j
        while i>0:
            while j>0:
                s+=self.table[i][j]
                j-=(j&-j)
            j=init_j
            i-=(i&-i)
        return s
      
n,m,q=map(int,input().split())
bit2d=BIT_2D(n,n)
for i in range(m):
  i,j=map(int,input().split())
  bit2d.add(i,j,1)
for i in range(q):
  i,j=map(int,input().split())
  ans=bit2d.sum(j,j)-bit2d.sum(j-1,i)-bit2d.sum(i-1,j)+bit2d.sum(i,i)
  print(ans)

Submission status: Wrong Answer

Solution code:

def f(h,w,a):
    da = [[0]*w for _ in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i-1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i-1][j] + cnt_w
    return da

def Calc(p,q,x,y, da):
    if p>x  or q>y:
        return 0
    if p==0 or q==0:
        return da[x][y]
    if p==0:
        return da[x][y] - da[x][q-1]
    if q==0:
        return da[x][y] - da[p-1][y]
    return da[x][y] - da[x][q-1] - da[p-1][y] + da[p-1][q-1]

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

d = f(N,N,t)
query = []
for _ in range(Q):
    p,q = map(int,input().split())
    p -= 1
    q -= 1
    print(Calc(p,p,q,q,d))

Submission status: Wrong Answer

Solution code:
import bisect
l,m,q = map(int,input().split())
L, R = [], []
for _ in range(m):
    l,r = map(int,input().split())
    L.append(l)
    R.append(r)

L.sort()
R.sort()
res = []

for _ in range(q):
    p,q = map(int,input().split())
    p_idx = bisect.bisect_left(L, p)
    q_idx = bisect.bisect_right(R, q)
    res.append(q_idx - p_idx)
for r in res:
    print(r)

Submission status: Wrong Answer

Solution code:
N,M,Q=map(int,input().split())
L,R=[],[]
for i in range(M):
  l,r=map(int,input().split())
  L.append(l)
  R.append(r)
Pl,Ql=[],[]
for i in range(Q):
  pq=list(map(int,input().split()))
  Pl.append(pq[0])
  Ql.append(pq[1])
c=[[0 for i in range(N+1)] for i in range(N+1)]
for i in range(M):
  c[L[i]][R[i]]+=1
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i][j-1]
for i in range(1,N+1):
  for j in range(1,N+1):
    c[i][j]+=c[i-1][j]
for i in range(Q):
  ans=c[R[i]][R[i]]-c[L[i]-1][R[i]]-c[R[i]][L[i]-1]+c[L[i]-1][L[i]-1]
  print(ans)

Submission status: Wrong Answer

Solution code:
N, M, Q = map(int, input().split())
L, R = [], []
for _ in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

p, q = [], []
for _ in range(Q):
    tmp = list(map(int, input().split()))
    p.append(tmp[0])
    q.append(tmp[1])

cum_sum = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
    cum_sum[L[i]][R[i]] += 1

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

def get_sum_range(L, R):
    ans = cum_sum[R][R] - cum_sum[R][L-1] - cum_sum[L-1][R] - cum_sum[L-1][L-1]
    return ans

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
[n,m,q] = map(int,input().split())
lr = []
pq = []
a = []
#print('n:{}, m:{}, q:{}'.format(n,m,q))

for i in range(m):
  lr.append(list(map(int,input().split())))

for i in range(q):
  pq.append(list(map(int,input().split())))

#print('lr:{}'.format(lr))
#print('pq:{}'.format(pq))

for i in range(q):
  if i > 0:
    for k in range(i-1):
      if pq[k][0] == pq[i][0] and pq[k][1] == pq[i][1]:
        a.append(a[k])
  if len(a) != i+1:
    cnt = 0
    for j in range(m):
      if pq[i][0] <= lr[j][0] and lr[j][1] <= pq[i][1]:
        cnt += 1
    a.append(cnt)

print('{}'.format(a[i]))

Submission status: Wrong Answer

Solution code:
import bisect
N, M, Q = map(int, input().split())
L = [] # 電車の西の果て
R = [] # 電車の東の果て
p = []
q = []

for _ in range(M):
	l, r = map(int, input().split())
	L.append(l)
	R.append(r)
	
for _ in range(Q):
	l, r = map(int, input().split())
	p.append(l)
	q.append(r)

# i - 1 番目に i 以東で始まる電車の本数を記録(NlogN)
train_easter = []
for i in range(1, N + 1):
	easter_num = M - bisect.bisect_left(L, i)
	train_easter.append(easter_num)
	
# print(train_easter)
	
# 答えの記録(NlogN)
for i in range(Q):
	easter_num = train_easter[p[i] - 1]
	east_lst = R[(M - easter_num) :] # i 以東で始まった電車の終着駅リスト
	east_lst.sort()
	# print(east_lst)
	ans = bisect.bisect_right(east_lst, q[i])
	print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline
from itertools import accumulate
sys.setrecursionlimit(100000000)

def main():
    n,m,q=map(int,input().split())
    L1=[0]*n
    L2=[0]*n

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

    for _ in range(q):
        p,q=map(int,input().split())
        p-=1
        q-=1
        if p==0:
            print(L2[q])
        else:
            print(L2[q]-L1[p-1]-L2[p-1])  

if __name__=='__main__':
    main()

Submission status: Wrong Answer

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

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

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!
N,M,Q=map(int,input().split())

start=[0]*N
end=[0]*N

for _ in range(M):
    p,q=map(int,input().split())
    start[p-1]+=1
    end[q-1]+=1

for i in range(len(start)-1):
    start[i+1]+=start[i]
    end[i+1]+=end[i]
print(start)
print(end)

#一時保存

Submission status: Wrong Answer

Solution code:
import collections
import heapq
import bisect
import sys
input = sys.stdin.readline
N, M, Q = map(int, input().split())
LR = [tuple(map(int, input().split())) for i in range(M)]

table = collections.defaultdict(list)
for l, r in LR:
    heapq.heappush(table[l], r)

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

Submission status: Wrong Answer

Solution code:

def resolve():
    N,M,Q=map(int,input().split())
    mp=[[0 for i in range(N+2)] for i in range(N+1)]
    for _ in range(M):
        L,R=map(int,input().split())

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



if __name__ == "__main__":
    resolve()
    #unittest.main()

Submission status: Wrong Answer

Solution code:
import bisect
N, M, Q = map(int, input().split())
S = []
E = []
V = []
for i in range(M):
  s, e = map(int, input().split())
  S.append(s)
  E.append(e)
S.sort()
E.sort()
for i in range(Q):
  v = list(map(int, input().split()))
  n = bisect.bisect_left(S, v[0])
  m = bisect.bisect_right(E, v[1])
  print(min(len(S) - n, m))