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:
N, M, Q = map(int, input().split())

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

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

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

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

Submission status: Accepted

Solution code:
N, M, Q = list(map(int,input().split()))
L = []
R = []
for i in range(M):
    in1, in2 = map(int,input().split())
    L.append(in1 - 1)
    R.append(in2 - 1)
p = []
q = []
for i in range(Q):
    in1, in2 = map(int,input().split())
    p.append(in1 - 1)
    q.append(in2 - 1)
    
a = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    a[L[i]][R[i]] += 1
    
#da[i][j]:(0,0)~(i,j)の長方形の和
def da_gen(a):
    w = len(a[0])
    h = len(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(da, p, q, x, y):
    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]

ret = da_gen(a)
for i in range(Q):
    ans = da_calc(ret, p[i], p[i], q[i], q[i])
    print(ans)

Submission status: Accepted

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

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


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)

queries = []
for _ in range(Q):
    p, q = map(int, input().split())
    # 0-index
    queries.append([p, q])


# s[l][r] := (0, 0), (l, r) の領域に含まれる列車の数
# s[l][r] = s[l-1][r] + s[l][r-1] - s[l-1][r-1] + a[l][r]

s = [[0 for r in range(N+1)] for l in range(N+1)]
for i in range(M):
    s[L[i]][R[i]] += 1

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

for l, r in queries:
    ans = s[r][r] - s[l-1][r] - s[r][l-1] + s[l-1][l-1]
    print(ans)

Submission status: Accepted

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

    for _ in range(M):
        l,r = map(int,input().split())
        cnt[l][r] += 1
    
    acc = []
    for i in range(N+1):
        acc.append(list(accumulate(cnt[i])))
    
    answers = []
    for _ in range(Q):
        p, q = map(int,input().split())
        ans = 0
        for l in range(p, q+1):
            ans += acc[l][q] - acc[l][p-1]
    
        answers.append(ans)

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

if __name__ == '__main__':
    solve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M, Q = map(int, input().split())
T = []
for i in range(M):
    L, R = map(int, input().split())
    T.append([L, R, 0])
for i in range(Q):
    L, R = map(int, input().split())
    T.append([L, R, 1, i])

Ans = [0]*Q
d = defaultdict(int)
T = sorted(T, key=lambda x: (x[1], x[2]))
for i in range(len(T)):
    result = 0
    if T[i][2] == 0:
        d[T[i][0]] += 1
    else:
        for j in range(T[i][0], T[i][1]+1):
            result += d[j]
        Ans[T[i][3]] = result

for i in Ans:
    print(i)

Submission status: Accepted

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(reverse=True)

lst = [[]]

j = N - 1
for i in range(M):
    if lr[i][0] - 1 < j:
        lst[-1].sort()
        while lr[i][0] - 1 < j:
            lst.append(lst[-1][:])
            j -= 1
    lst[-1].append(lr[i][-1]-1)
lst[-1].sort()
lst.reverse()

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

Submission status: Accepted

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

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

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

ans = []
for _ in range(Q):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    num = 0
    for k in range(p, q+1):
        knum = X[k][q] - X[k][p-1] if p>=1 else X[k][q]
        num += knum
    ans.append(num)

print('\n'.join(map(str, ans)))

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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

    R = [[0] * (n + 1) for _ in range(n + 1)]
    for h in range(n):
        for w in range(n):
            R[h + 1][w + 1] = R[h][w + 1] + R[h + 1][w] - R[h][w] + cnt[h][w]

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


if __name__ == '__main__':
    resolve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:

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

#iを始点とする列車。のなかでjを終点とする列車の数をもつ配列
ruiseki = [[0]*(N+1) for i in range(N+1)]

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

#累積和をとります
for i in range(0,N+1,1):
    for j in range(1,N+1,1):
        ruiseki[i][j] = ruiseki[i][j]+ruiseki[i][j-1]

ans = []

#クエリ処理
for q in range(Q):
    l,r = map(int,input().split())

    #始点がl-rにあるものすべての列車のなかで終点がl-rにあるもの
    tmpans = 0
    for i in range(l,r+1,1):
        tmpans += ruiseki[i][r]
    ans.append(tmpans)

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

Submission status: Accepted

Solution code:
# 累積和
# PyPy なら通る
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

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

result = []
for _ in range(Q):
    p, q = map(int, input().split())
    result.append(sum(t[i][q] - t[i][i - 1] for i in range(p, q + 1)))
#print('\n'.join(str(v) for v in result))
print(*result, sep='\n')

Submission status: Accepted

Solution code:
# 累積和
# PyPy なら通る
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

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

result = []
for _ in range(Q):
    p, q = map(int, input().split())
    result.append(sum(t[i][q] - t[i][i - 1] for i in range(p, q + 1)))
print('\n'.join(str(v) for v in result))
#print(*result, sep='\n')

Submission status: Accepted

Solution code:
# 累積和(2次元)
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

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

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

result = []
for _ in range(Q):
    p, q = map(int, input().split())
    result.append(t[q][q] + t[p - 1][p - 1] - t[p - 1][q] - t[q][p - 1])
#print('\n'.join(str(v) for v in result))
print(*result, sep='\n')

Submission status: Accepted

Solution code:
# 累積和(2次元)
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

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

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

result = []
for _ in range(Q):
    p, q = map(int, input().split())
    result.append(t[q][q] + t[p - 1][p - 1] - t[p - 1][q] - t[q][p - 1])
print('\n'.join(str(v) for v in result))
#print(*result, sep='\n')

Submission status: Accepted

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

Submission status: Accepted

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

#G[i][j]=(i,j)なる列車の本数
G=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    l,r=map(int,input().split())
    G[l][r]+=1



#S[i][j]=(i以下,j以下)なる列車の本数(i<=j)
S=[[0]*(n+1) for i in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        S[i][j]=S[i-1][j]+S[i][j-1]-S[i-1][j-1]+G[i][j]





for i in range(q):
    s,f=map(int,input().split())
    print(S[f][f]-S[s-1][f]-S[f][s-1]+S[s-1][s-1])

Submission status: Accepted

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

x = np.array([[0]*(N+1) for _ in range(N+1)])

for L, R in LR:
	x[L][R] += 1

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

for p, q in pq:
	print(x[q][q] - x[q][p-1] - x[p-1][q] + x[p-1][p-1])

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
import numpy as np
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

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

x = np.zeros((N+1, N+1), dtype=np.int64)
for L, R in LR:
    x[L, R] += 1
x = x.cumsum(axis=0).cumsum(axis=1)

for p, q in pq:
    print(x[q][q]-x[q][p-1]-x[p-1][q]+x[p-1][p-1])

Submission status: Accepted

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

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

for L, R in LR:
	x[L][R] += 1

for l in range(N+1):
	x[l] = list(accumulate(x[l]))

for l in range(1, N+1):
	for r in range(N+1):
		x[l][r] += x[l-1][r]
		
for p, q in pq:
	print(x[q][q] - x[q][p-1] - x[p-1][q] + x[p-1][p-1])

Submission status: Accepted

Solution code:
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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

LR = [[0]*(N+1) for i in range(N+1)]
for i in range(M):
    Ltmp,Rtmp = list(map(int,input().split()))
    LR[Ltmp][Rtmp] += 1

LRc = [[0]*(N+1) for i in range(N+1)]
for i in range(1,N+1):
    for j in range(1,N+1):
        LRc[i][j] = LRc[i-1][j]+LRc[i][j-1]-LRc[i-1][j-1]+LR[i][j]

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

Submission status: Accepted

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+1):
  for j in range(N):
    X[i][j+1] += X[i][j]
for i in range(N+1):
  for j in range(N):
    X[j+1][i] += X[j][i]
for i in range(Q):
  p, q = map(int, input().split())
  print(X[q][q] - X[p-1][q])

Submission status: Accepted

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

#############
# Libraries #
#############

import sys
input = sys.stdin.readline

import math
#from math import gcd
import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache

#############
# Constants #
#############

MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"

#############
# Functions #
#############

######INPUT######
def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]

######OUTPUT######
def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()

#####Shorten#####
def DD(arg): return defaultdict(arg)

#####Inverse#####
def inv(n): return pow(n, MOD-2, MOD)

######Combination######
kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret

######Factorization######
def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr

#####MakeDivisors######
def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors

#####MakePrimes######
def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum

#####GCD#####
def gcd(a, b):
    while b: a, b = b, a % b
    return a

#####LCM#####
def lcm(a, b):
    return a * b // gcd (a, b)

#####BitCount#####
def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count

#####ChangeBase#####
def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]

#####IntLog#####
def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count

#############
# Main Code #
#############

N,M,Q = IL()
dic = [DD(int) for i in range(N+1)]
for _ in range(M):
  l,r = IL()
  dic[l][r] += 1

ACC = [[0] for i in range(N+1)]
for i in range(N+1):
  for j in range(N):
    ACC[i].append(ACC[i][-1] + dic[i][j+1])
for i in range(N):
  for j in range(N+1):
    ACC[i+1][j] += ACC[i][j]
for _ in range(Q):
  p,q = IL()
  print(ACC[q][q]-ACC[q][p-1]-ACC[p-1][q]+ACC[p-1][p-1])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():
    
    # https://atcoder.jp/contests/abc005/tasks/abc005_4
    # https://qiita.com/drken/items/56a6b68edef8fc605821#4-%E4%BA%8C%E6%AC%A1%E5%85%83%E7%B4%AF%E7%A9%8D%E5%92%8C
    # https://upura.hatenablog.com/entry/2019/04/01/212701
    N,M,Q=map(int,input().split())
    D=[[0]*N for _ in range(N)]
    for i in range(M):
        l,r=map(int,input().split())
        l-=1
        r-=1
        D[l][r]+=1

    
    # 2次元累積和
    # S[x][y]:= [0:x] * [0:y]の長方形区間の和
    S = [[0] * (N + 1) for _ in range(N + 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] + D[i][j]
    
    for i in range(Q):
        p,q=map(int,input().split())
        x1,y1=p-1,p-1
        x2,y2=q,q
        ans=S[x2][y2] - S[x1][y2] - S[x2][y1] + S[x1][y1]
        print(ans)
    
    
    
    
resolve()

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_)]
from collections import defaultdict
dmap=defaultdict(int)
smap=defaultdict(int)
ssmap=defaultdict(int)
for l,r in lr:
  if (l,r) in dmap:
    dmap[(l,r)]+=1
  else:
    dmap[(l,r)]=1
for i in range(1,n+1):
  tmp=0
  for j in range(i,n+1):
    if (i,j) in dmap:
      tmp+=dmap[(i,j)]
    smap[(i,j)]=tmp
for i in range(1,n+1):
  tmp=0
  for j in range(1,i+1):
    tmp+=smap[(j,i)]
    ssmap[(j,i)]=tmp

for p,q in pq:
  ans=ssmap[(q,q)]-ssmap[(p-1,q)]
  print(ans)

Submission status: Accepted

Solution code:
import sys

def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり
def S(): return sys.stdin.readline().rstrip()

N,M,Q = map(int,S().split())
A = [[0]*(N+2) for _ in range(N+2)]
# A[i][j] = [i,j]に完全に含まれる列車の本数

for i in range(M):
    L,R = LI()
    A[0][R] += 1
    A[L+1][R] -= 1

from itertools import accumulate

# 二重累積和

for i in range(N+2):
    A[i] = list(accumulate(A[i]))

for i in range(N+2):
    for j in range(N+2):
        if i == 0 or j == 0:
            continue
        else:
            A[i][j] += A[i-1][j]

for i in range(Q):
    p,q = LI()
    print(A[p][q])

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
T = [tuple(map(int, input().split())) for i in range(M)]
queries = [tuple(map(int, input().split())) for i in range(Q)]

plot = [[0] * (N + 1) for i in range(N + 1)]
accum = [[0] * (N + 1) for i in range(N + 1)]
for Li, Ri in T:
    plot[Li][Ri] += 1
for i in range(1, N + 1):
    for j in range(1, N + 1):
        accum[i][j] = accum[i][j - 1] + accum[i - 1][j] \
            - accum[i - 1][j - 1] + plot[i][j]

for pi, qi in queries:
    print(accum[qi][qi] - accum[pi - 1][qi])

Submission status: Accepted

Solution code:

def resolve():
    n, m, q = map(int, input().split())
    rosen = [[0] * n for _ in range(n)]
    for i in range(m):
        l, r = map(int, input().split())
        l -= 1
        r -= 1
        rosen[l][r] += 1
    cum = [[0] * (n+1) for _ in range((n+1))]

    for i in range(n):
        if i == 0:
            cum[0][0] = rosen[0][0]
            for j in range(1, n):
                cum[0][j] = cum[0][j-1] + rosen[0][j]
        else:
            cum[i][0] = cum[i-1][0] + rosen[i][0]
            for j in range(1,n):
                cum[i][j] = cum[i-1][j] + cum[i][j-1] - cum[i-1][j-1] + rosen[i][j]
    for i in range(q):
        p, q = map(int, input().split())
        p -= 1
        q -= 1
        if p == 0:
            print(cum[q][q])
        else:
            print(cum[q][q]-cum[p-1][q]-cum[q][p-1]+cum[p-1][p-1])
resolve()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

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

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

Submission status: Accepted

Solution code:
n,m,q=map(int,input().split())
grid=[]
for i in range(n+1):
  grid.append([])
  for j in range(n+1):
    grid[-1].append(0)
grid2=[]
for i in range(n+1):
  grid2.append([])
  for j in range(n+1):
    grid2[-1].append(0)
for i in range(m):
  l,r=map(int,input().split())
  grid[r][l]+=1
for sumxy in range(0,2*n+1):
  if sumxy>n:
    r=sumxy-n
  else:
    r=0
  for x in range(r,min(sumxy+1,n+1)):
    y=sumxy-x
    grid2[x][y]=grid2[x-1][y]+grid2[x][y-1]-grid2[x-1][y-1]+grid[x][y]
for i in range(q):
  p1,q1=map(int,input().split())
  print(grid2[q1][n]-grid2[q1][p1-1])

Submission status: Accepted

Solution code:
N,M,Q = map(int,input().split())
A = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L,R = map(int,input().split())
    A[L][R] += 1
dp = [[0 for _ in range(N+1)] for _ in range(N+1)]
dp[N][N] = A[N][N]
for i in range(N-1,0,-1):
    for j in range(i,N+1):
        dp[i][j] = A[i][j]
        if j>i:
            dp[i][j] += dp[i+1][j]+dp[i][j-1]-dp[i+1][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())
L,R=0,0
A=[[0]*(N+1) for i in range(N+1)]
for i in range(M):
  L,R=map(int,input().split())
  A[L][R]+=1
B=[[0]*(N+1) for i in range(N+1)]
for i in range(N):
  for j in range(N):
    B[i+1][j+1]=B[i+1][j]+B[i][j+1]-B[i][j]+A[i+1][j+1]
for i in range(Q):
  L,R=map(int,input().split())
  print(B[N][R]-B[L-1][R])

Submission status: Accepted

Solution code:
class Cumsum2d(object):
    def __init__(self, a):
        self.a = a
        self.h = len(a)
        self.w = len(a[0])
        self._cumsum = [[0 for _ in range(self.w + 1)] for _ in range(self.h + 1)]
        self._preprocess()

    def _preprocess(self):
        for i in range(1, self.h + 1):
            for j in range(1, self.w + 1):
                self._cumsum[i][j] = (
                    self.a[i - 1][j - 1]
                    + self._cumsum[i][j - 1]
                    + self._cumsum[i - 1][j]
                    - self._cumsum[i - 1][j - 1]
                )

    def query(self, h1, h2, w1, w2):
        return (
            self._cumsum[h2][w2]
            - self._cumsum[h1][w2]
            - self._cumsum[h2][w1]
            + self._cumsum[h1][w1]
        )


if __name__ == "__main__":
    N, M, Q = [int(x) for x in input().split(" ")]
    # L = [0 for _ in range(N + 2)]
    count = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
    for _ in range(M):
        l, r = [int(x) for x in input().split(" ")]
        count[l][r] += 1

    cumsum = Cumsum2d(count)
    for _ in range(Q):
        p, q = [int(x) for x in input().split(" ")]
        print(cumsum.query(p, q + 1, p, q + 1))

Submission status: Accepted

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

Solution code:
n, m, q = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(m)]
pq = [list(map(int, input().split())) for i in range(q)]
li = [[0] * (n + 1) for i in range(n + 1)]
for i in lr:
    l, r = i[0], i[1]
    li[l][r] += 1
for i in range(1, n + 1):
    for j in range(1, n + 1):
        li[i][j] += li[i - 1][j] + li[i][j - 1] - li[i - 1][j - 1]
for i in pq:
    p, q = i[0], i[1]
    print(li[q][q] - li[p - 1][q] - li[q][p - 1] + li[p - 1][p - 1])