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: Accepted

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

Submission status: Accepted

Solution code:
#
# 　　  ⋀_⋀　 
#　　  (･ω･)  
# .／ Ｕ ∽ Ｕ＼
#  │＊　合　＊│
#  │＊　格　＊│ 
#  │＊　祈　＊│ 
#  │＊　願　＊│ 
#  │＊　　　＊│ 
#      ￣
#
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,ceil,sqrt,factorial,hypot,log #log2ないｙｐ
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M,Q = MI()
    LR=LLIN_(M)
    PQ=LLIN(Q)

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

    cumsum_2d = [[0]*(N+1) for _ in range(N+1)]
    
    for i in range(N):
        for j,d in enumerate(D[i]):
            cumsum_2d[i+1][j+1] = d

    for i in range(N):
        for j,d in enumerate(D[i]):
            cumsum_2d[i+1][j+1] += cumsum_2d[i+1][j] + cumsum_2d[i][j+1] - cumsum_2d[i][j]
    
    for p,q in PQ:
        print(cumsum_2d[q][q]-cumsum_2d[p-1][q]-cumsum_2d[q][p-1]+cumsum_2d[p-1][p-1])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys

*I, = map(int, sys.stdin.read().split())
n, m, Q = I[:3]
lr = zip(*[iter(I[3:3+m*2])] * 2)
pq = zip(*[iter(I[3+m*2:])] * 2)

def main():
    res = [[0] * (n + 2) for _ in range(n+2)]
    
    for l, r in lr:
        res[1][r] += 1
        res[1][n+1] -= 1
        res[l+1][r] -= 1
        res[l+1][n+1] += 1
    
    for i in range(1, n+2):
        for j in range(1, n+1):
            res[i][j+1] += res[i][j]

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

    for p, q in pq:
        yield res[p][q]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys

*I, = map(int, sys.stdin.read().split())
n, m, Q = I[:3]
lr = zip(*[iter(I[3:3+m*2])] * 2)
pq = zip(*[iter(I[3+m*2:])] * 2)

def main():
    res = [[0] * (n + 2) for _ in range(n+2)]
    
    for l, r in lr:
        res[1][r] += 1
        res[1][n+1] -= 1
        res[l+1][r] -= 1
        res[l+1][n+1] += 1
    
    for i in range(n+1):
        for j in range(n+1):
            res[i][j+1] += res[i][j]

    for j in range(n+1):
        for i in range(n+1):
            res[i+1][j] += res[i][j]
    
    for p, q in pq:
        yield res[p][q]

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
import numpy as np

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m, q = I[:3]
l, r = I[3:3+m*2].reshape(-1, 2).T
p, q = I[3+m*2:].reshape(-1, 2).T

def main():
    res = np.zeros((n+2, n+2), dtype=np.int64)

    np.add.at(res, (1, r), 1)
    res[1, n+1] += -1 * m
    np.add.at(res, (l+1, r), -1)
    np.add.at(res, (l+1, n+1), 1)
    res = np.cumsum(res, axis=1)
    res = np.cumsum(res, axis=0)

    ans = res[p, q]
    return ans

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
import numpy as np

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m, q = I[:3]
l, r = I[3:3+m*2].reshape(-1, 2).T
p, q = I[3+m*2:].reshape(-1, 2).T

def main():
    res = np.zeros((n+2, n+2), dtype=np.int64)
    
    np.add.at(res, (1, r), 1)
    np.add.at(res, (l+1, r), -1)
    np.add.at(res, (1, n+1), -1)
    np.add.at(res, (l+1, n+1), 1)
    res = np.cumsum(res, axis=0)
    res = np.cumsum(res, axis=1)

    ans = res[p, q]
    return ans

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, Q = list(map(int, sys.stdin.buffer.readline().split()))
LR = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
P, Q = list(zip(*[map(int, sys.stdin.buffer.readline().split()) for _ in range(Q)]))

P = np.array(P, dtype=int)
Q = np.array(Q, dtype=int)

counts = np.zeros((N + 1, N + 1), dtype=int)
for l, r in LR:
    counts[l, r] += 1
cum = counts.cumsum(axis=1).cumsum(axis=0)

ans = cum[Q, Q] - cum[P - 1, Q] - cum[Q, P - 1] + cum[P - 1, P - 1]
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7
# MOD = 998244353


N, M, Q = list(map(int, sys.stdin.buffer.readline().split()))
LR = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
PQ = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

counts = np.zeros((N + 1, N + 1), dtype=int)
for l, r in LR:
    counts[l, r] += 1
cum = counts.cumsum(axis=1).cumsum(axis=0)

for p, q in PQ:
    ans = cum[q, q] - cum[p - 1, q] - cum[q, p - 1] + cum[p - 1, p - 1]
    print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

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


# MOD = 998244353

class BinaryIndexedTree:
    # http://hos.ac/slides/20140319_bit.pdf
    def __init__(self, size):
        """
        :param int size:
        """
        self._bit = [0] * size
        self._size = size

    def add(self, i, w):
        """
        i 番目に w を加える
        :param int i:
        :param int w:
        """
        x = i + 1
        while x <= self._size:
            self._bit[x - 1] += w
            x += x & -x

    def sum(self, i):
        """
        [0, i) の合計
        :param int i:
        """
        ret = 0
        while i > 0:
            ret += self._bit[i - 1]
            i -= i & -i
        return ret

    def __len__(self):
        return self._size


def argsort(li, key=None, reverse=False):
    return [i for _, i in sorted(
        [(a, i) for i, a in enumerate(li)], key=(lambda t: key(t[0])) if key else None, reverse=reverse
    )]


N, M, Q = list(map(int, sys.stdin.buffer.readline().split()))
LR = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]
PQ = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(Q)]

LR.sort(reverse=True)
idx = argsort(PQ, reverse=True)
PQ.sort(reverse=True)

lri = 0
bit = BinaryIndexedTree(size=N + 1)
ans = [0] * Q
for i, (p, q) in enumerate(PQ):
    while lri < len(LR) and LR[lri][0] >= p:
        l, r = LR[lri]
        bit.add(r, 1)
        lri += 1
    ans[idx[i]] = bit.sum(q + 1)
print(*ans, sep='\n')

Submission status: Accepted

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

def main():
    N,M,Q = map(int,input().split())
    go = [[0 for _ in range(N)] for i in range(N)]
    for _ in range(M):
        L,R = map(int,input().split())
        go[L-1][R-1] += 1
        
    qu = []
    for _ in range(Q):
        p,q = map(int,input().split())
        qu.append((p,q))
        
    num = [[0 for _ in range(N)] for _ in range(N)]
    _num = [[0 for _ in range(N)] for _ in range(N+1)]
    for i in range(N):
        num[i][0] = go[i][0]
    for i in range(N):
        for j in range(N-1):
            num[i][j+1] = num[i][j] + go[i][j+1]

    for i in range(N):
        for j in range(N):
            _num[j+1][i] = _num[j][i] + num[j][i]
            
    for i in range(Q):
        p,q = qu[i]
        ans = _num[q][q-1] - _num[p-1][q-1]
        print(ans)
    
if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#a[i][j]
def da_generate(h,w,a):
    da = [[0]*w for j 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

#da_calc(p,q,x,y):(p,q)~(x,y)の長方形の和
def da_calc(p,q,x,y,da):
    if p > x or q > y:
        return 0
    if p == 0 and 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[p-1][y]-da[x][q-1]+da[p-1][q-1]

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

da = da_generate(n, n, lrl)

for _ in range(q):
   p,q = map(int,input().split())
   p -= 1
   q -= 1
   print(da_calc(p,p,q,q,da))

Submission status: Accepted

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

T = [[0 for _ in range(N + 2)] for _ in range(N + 2)]
for L, R in LR:
  T[L][R] += 1
#print("T:", T)

S = [[0 for _ in range(N + 2)] for _ in range(N + 2)]
for i in range(N + 2):
  for j in range(N + 2):
    S[i][j] = S[i][j - 1] + T[i][j]
for j in range(N + 2):
  for i in range(N + 2):
    S[i][j] += S[i - 1][j]
#print("S:", S)

for P, Q in PQ:
  print(S[Q][Q] - S[P - 1][Q] + S[Q][P - 1] - S[P - 1][P - 1])

Submission status: Accepted

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

# 累積和
for i in range(n):
    np.add.accumulate(train[i], out=train[i])
np.add.accumulate(train, out=train)
train=train.tolist()

ans = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    a = train[y][y]
    if x != 0:
        a -= train[x-1][y]
    ans.append(a)

print(*ans, sep="\n")

Submission status: Accepted

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

# 累積和
for i in range(n):
    np.add.accumulate(train[i], out=train[i])
np.add.accumulate(train, out=train)

ans = []
for _ in range(q):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    a = train[y][y]
    if x != 0:
        a -= train[x-1][y]
    ans.append(a)

print(*ans, sep="\n")

Submission status: Accepted

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

Submission status: Accepted

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(0, 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[n-1][q[i]] - count[p[i]-1][q[i]]
    else:
        tmp = count[n-1][q[i]]
    print(tmp)

Submission status: Accepted

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: Accepted

Solution code:
from itertools import accumulate

N, M, Q, *I = map(int, open(0).read().split())
LR, PQ = I[:2 * M], I[2 * M:]

M = [[0] * (N + 1) for _ in range(N + 1)]
for l, r in zip(*[iter(LR)] * 2):
    M[l][r] += 1

A = [list(accumulate(reversed(a)))[::-1] for a in zip(*[accumulate(m) for m in M])]

for p, q in zip(*[iter(PQ)] * 2):
    print(A[q][p])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, Q = MAP()

# 2次元累積和
# acc[i][j] := 都市iで区間開始前で都市jで区間終了後である列車の数
acc = list2d(N, N, 0)
for i in range(M):
    l, r = MAP()
    l -= 1; r -= 1
    acc[l][r] += 1
# 区間開始前かどうかを持つ1次元目は後ろから累積和する
for j in range(N):
    for i in range(N-2, -1, -1):
        acc[i][j] += acc[i+1][j]
for i in range(N):
    acc[i] = list(accumulate(acc[i]))

ans = [''] * Q
for i in range(Q):
    p, q = MAP()
    p -= 1; q -= 1
    ans[i] = str(acc[p][q])
print('\n'.join(ans))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

import sys
from itertools import accumulate

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 18
MOD = 10 ** 9 + 7

N, M, Q = MAP()

# 2次元累積和
# acc[i][j] := 都市iで区間開始前で都市jで区間終了後である列車の数
acc = list2d(N, N, 0)
for i in range(M):
    l, r = MAP()
    l -= 1; r -= 1
    acc[l][r] += 1
# 区間開始前かどうかを持つ1次元目は後ろから累積和する
for j in range(N):
    for i in range(N-2, -1, -1):
        acc[i][j] += acc[i+1][j]
for i in range(N):
    acc[i] = list(accumulate(acc[i]))

for i in range(Q):
    p, q = MAP()
    p -= 1; q -= 1
    print(acc[p][q])

Submission status: Accepted

Solution code:
n,m,q = map(int,input().split())
query = [[0 for j in range(501)] for i in range(501)]

for h in range(m):
    k,l = map(int,input().split())
    query[k][l] += 1

#リストを累積和にする
for i in range(501):
    for j in range(501):
        if j == 0:
            continue
        query[i][j] = query[i][j] + query[i][j-1]
for i in range(501):
    for j in range(501):
        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-1][l]
        B = query[l][k-1]
        C = query[k-1][k-1]
    print(query[l][l] - A - B + C)

Submission status: Accepted

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


n, m, q = map(int, input().split())
DP = [[0]*n for _ in range(n)]

for i in range(m):
    start, end = map(int, input().split())
    DP[start-1][end-1] += 1

for y in range(n):
    for x in range(y, n-1):
        DP[y][x+1] += DP[y][x]

for x in range(n):
    for y in range(x, 0, -1):
        DP[y-1][x] += DP[y][x]

for i in range(q):
    left, right = map(int, input().split())
    print(DP[left-1][right-1])

Submission status: Accepted

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


n, m, q = map(int, input().split())
DP = [[0]*n for _ in range(n)]

for i in range(m):
    start, end = map(int, input().split())
    DP[start-1][end-1] += 1

for y in range(n):
    for x in range(y, n-1):
        DP[y][x+1] += DP[y][x]

for x in range(n):
    for y in range(x, 0, -1):
        DP[y-1][x] += DP[y][x]

for i in range(q):
    left, right = map(int, input().split())
    print(DP[left-1][right-1])

Submission status: Accepted

Solution code:
import numpy as np

def solve(N, M, Q, L, R, p, q):
    A = np.zeros((N+1, N+1), dtype=int)
    for i in range(M):
        A[L[i], R[i]] += 1
    S = np.zeros((N+1, N+1), dtype=int)
    S[0,0] = A[0,0]
    for i in range(1, N+1):
        S[i,:] = S[i-1,:] + A[i,:]
    for j in range(1, N+1):
        S[:,j] += S[:,j-1]
    res = []
    for i in range(Q):
        x1, x2 = p[i]-1, q[i]
        a = S[x2,x2]
        b = S[x1,x2]
        c = S[x2,x1]
        d = S[x1,x1]
        res.append(a - b - c + d)
    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: Accepted

Solution code:
from collections import Counter,defaultdict,deque
import sys
from itertools import permutations, combinations
from heapq import heappop, heappush
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
    
def inp(): # n=1
    return int(input())
def inpm(): # x=1,y=2
    return map(int,input().split())
def inpl(): # a=[1,2,3,4,5,...,n]
    return list(map(int, input().split()))
def inpls(): # a=['1','2','3',...,'n']
    return list(input().split())
def inplm(n): # x=[] 複数行
    return list(int(input()) for _ in range(n))
def inpll(n): # [[1,1,1,1],[2,2,2,2],[3,3,3,3]]
    return sorted([list(map(int, input().split())) for _ in range(n)])


def main():
    n,m,Q = inpm()
    ans = [[0 for _ in range(n)] for _ in range(n)]
    for i in range(m):
        l,r = inpm()
        r-=1
        ans[r][0]+=1
        if l != n:
            ans[r][l] -= 1
    for i in range(n):
        for j in range(1,n):
            ans[i][j] += ans[i][j-1]
    for i in range(n):
        for j in range(1,n):
            ans[j][i] += ans[j-1][i]
    for _ in range(Q):
        p,q = inpm()
        print(ans[q-1][p-1])

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

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

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

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


if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

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]
  
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: Accepted

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]+pos[p-1][p-1])

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
n, m, q = [int(i) for i in sys.stdin.readline().split()]
graph = [[0 for i in range(n+1)] for j in range(n+1)]
for j in range(m):
    l, r = [int(i) for i in sys.stdin.readline().split()]
    graph[l][r] += 1
accum_ls = [[0 for i in range(n+1)] for j in range(n+1)]
for i in range(1,n+1):
    for j, k in enumerate(accumulate(graph[i])):
        accum_ls[i][j] = k
for j in range(q):
    p, _q = [int(i) for i in sys.stdin.readline().split()]
    res = 0
    for k in range(p, _q+1):
        res += accum_ls[k][_q] - accum_ls[k][p-1]
    print(res)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
g=[[0 for i in range(n+1)] for j in range(n+1)]
for i in range(m):
    a,b=map(int,input().split())
    #a-=1
    #b-=1
    g[a][b]+=1
    
for i in range(n):
    for j in range(n+1):
        g[i+1][j]+=g[i][j]
for i in range(n+1):
    for j in range(n):
        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]-g[a][b]-g[b][a])
#print(g)

Submission status: Accepted

Solution code:
import numpy as np
import sys
input = sys.stdin.readline

N,M,Q = map(int,input().split())
lis = np.zeros((N,N))
for i in range(M):
    L,R = map(int,input().split())
    lis[N-L,R-1] += 1
#二次元累積和
np.cumsum(lis,axis=0,out=lis)
np.cumsum(lis,axis=1,out=lis)
for _ in range(Q):
    p,q = map(int,input().split())
    print(int(lis[N-p,q-1]))

Submission status: Accepted

Solution code:
import numpy as np
N,M,Q = map(int,input().split())
lis = np.zeros((N,N))
for i in range(M):
    L,R = map(int,input().split())
    lis[N-L,R-1] += 1
#二次元累積和
np.cumsum(lis,axis=0,out=lis)
np.cumsum(lis,axis=1,out=lis)
for _ in range(Q):
    p,q = map(int,input().split())
    print(int(lis[N-p,q-1]))

Submission status: Accepted

Solution code:
import numpy as np
N,M,Q = map(int,input().split())
lis = np.zeros((N,N))
for i in range(M):
    L,R = map(int,input().split())
    lis[L-1,R-1] += 1
#二次元累積和
for i in range(N-2,-1,-1):
    lis[i] += lis[i+1]
for j in range(1,N):
    lis[:,j] += lis[:,j-1]

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

Submission status: Accepted

Solution code:
import numpy as np

N,M,Q = [int(i) for i in input().split()]
T = [[0]*(N+1)]*(N+1)
T=np.array(T)

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

np.cumsum(T, axis=0, out=T)
np.cumsum(T, axis=1, out=T)
data = T.tolist()

for _ in range(Q):
    ql, qr = [int(i) for i in input().split()]
    answer = data[qr][qr] - data[qr][ql-1] +  data[ql-1][ql-1] - data[ql-1][qr]
    print(answer)

Submission status: Accepted

Solution code:
import collections
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)]
dp = [[0]*(N+1) for i in range(N+1)]

for L, R in LR:
    dp[L][R] += 1
for i in reversed(range(1, N)):
    for j in range(1, N+1):
        dp[i][j] += dp[i+1][j]

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


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

Submission status: Accepted

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

Submission status: Accepted

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


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):
    matrix = [[0]*(N+1) for _ in range(N+1)]

    for i in range(M):
        matrix[L[i]][R[i]] += 1

    ruisekiwa = [[0]*(N+1) for _ in range(N+1)]
    for i in range(N):
        for j in range(N):
            ruisekiwa[i+1][j+1] = ruisekiwa[i][j+1] + ruisekiwa[i+1][j] - ruisekiwa[i][j] + matrix[i+1][j+1]
    for j in range(Q):
        qq = q[j]
        pp = p[j]
        answer = ruisekiwa[qq][qq] - ruisekiwa[qq][pp-1] - ruisekiwa[pp-1][qq] + ruisekiwa[pp-1][pp-1]

        print(answer)

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int
    L = [int()] * (M)  # type: "List[int]"
    R = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        L[i] = int(next(tokens))
        R[i] = int(next(tokens))
    p = [int()] * (Q)  # type: "List[int]"
    q = [int()] * (Q)  # type: "List[int]"
    for i in range(Q):
        p[i] = int(next(tokens))
        q[i] = int(next(tokens))
    solve(N, M, Q, L, R, p, q)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n,m,q = inpl()
lr = [inpl() for i in range(m)]
st = [inpl() for i in range(q)]
cnt = [[0 for j in range(n)] for i in range(n)]

for i in lr:
    a,b = i
    cnt[a-1][b-1] += 1
for i in range(n):
    for j in range(i,n-1):
        cnt[i][j+1] += cnt[i][j]
# pprint.pprint(cnt)
for i in st:
    cc = 0
    a,b = i
    for _ in range(a-1,b):
        cc += cnt[_][b-1]
    print(cc)

Submission status: Accepted

Solution code:
import numpy as np

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

data = np.array(data)
np.cumsum(data, axis=0, out=data)
np.cumsum(data, axis=1, out=data)
data = data.tolist()
#print(data)
for i in range(Q):
    p, q = map(int, input().split())
    p -= 1
    x = data[q][q]
    x -= data[p][q] + data[q][p]
    x += data[p][p]
    print(x)

Submission status: Accepted

Solution code:
import numpy as np

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

LR = np.zeros(shape=(N + 1, N + 1), dtype=np.int32)
L, R = np.array([input().split() for _ in range(M)], dtype=np.int32).T
np.add.at(LR, (L, R), 1)

np.cumsum(LR, axis=0, out=LR)
np.cumsum(LR, axis=1, out=LR)

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

print(*ans, sep='\n')