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 = [int(_) for _ in input().split()]
LR = [[int(_) for _ in input().split()] for _ in range(M)]
PQ = [[int(_) for _ in input().split()] for _ in range(Q)]

cumsum = [[0] * (N+2) for _ in range(N+1)]
for lr in LR:
    cumsum[lr[0]][lr[0]] += 1
    if lr[1] < N:
        cumsum[lr[0]][lr[1]+1] -= 1
for i in range(N+1):
    for j in range(i, N):
        cumsum[i][j+1] += cumsum[i][j]
for pq in PQ:
    print(sum([cumsum[i][i]-cumsum[i][pq[1]+1]
               for i in range(pq[0], pq[1]+1)]))

Submission status: Accepted

Solution code:
class Train:
    def __init__(self, left, right):
        self.left = left
        self.right = right


class Question:
    def __init__(self, p, q):
        self.p = p
        self.q = q


N, M, Q = map(int, input().split())
trains = []
questions = []
for _ in range(M):
    left, right = map(int, input().split())
    trains.append(Train(left, right))
for _ in range(Q):
    p, q = map(int, input().split())
    questions.append(Question(p, q))

m = {}
cm = {}
for i in range(N+1):
    for j in range(N+1):
        m.setdefault(i, {})
        m[i][j] = 0
        cm.setdefault(i, {})
        cm[i][j] = 0

for train in trains:
    m[train.left][train.right] += 1

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

for i in range(1, N+1):
    for j in range(1, N+1):
        cm[i][j] += cm[i-1][j]
for question in questions:
    print(cm[question.q][question.q] + cm[question.p-1][question.p-1] -
          cm[question.p-1][question.q]-cm[question.q][question.p-1])

Submission status: Accepted

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

imos = [[0]*(N+1) for i in range(N+1)]
for l,r in src:
    imos[l][r] += 1

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

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

Submission status: Accepted

Solution code:
N, M, Q = [int(v) for v in input().split()]
p = []
q = []
c = [[0] * (N+1) for i in range(N+1)]

for i in range(M):
    l, r = [int(v) for v in input().split()]
    c[l][r] += 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):
    a, b = [int(v) for v in input().split()]
    p.append(a)
    q.append(b)

for l, r in zip(p, q):
    ans = c[r][r] + c[l-1][l-1] - c[l-1][r] - c[r][l-1]
    print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int,input().split())
Train=[[int(i) for i in input().split()] for i in range(M)]
Map=[[0]*(N+1) for i in range(N+1)]
for i in Train:
  x,y=i[0],i[1]
  Map[y][x]+=1
for a in range(1,N+1):
  for b in range(1,N+1):
    if b<=N-1:
      Map[a][b+1]=Map[a][b]+Map[a][b+1]
    if a>=2:
      Map[a][b]=Map[a-1][b]+Map[a][b]
for i in range(Q):
  p,q=map(int,input().split())
  print(Map[q][q]-Map[q][p-1]-Map[p-1][q]+Map[p-1][p-1])

Submission status: Accepted

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

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

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

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

for i in range(q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    if l == 0:
        print(imos[r][r])
    else:
        print(imos[r][r] - imos[l - 1][r] - imos[r][l - 1] + imos[l - 1][l - 1])

Submission status: Accepted

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

imos = [[0]*(N+1) for i in range(N+1)]
for l,r in src:
    imos[l][r] += 1
for i in range(N+1):
    for j in range(N):
        imos[i][j+1] += imos[i][j]
for i in range(N):
    for j in range(N+1):
        imos[i+1][j] += imos[i][j]

ans = []
for p,q in qs:
    ans.append(imos[q][q] - imos[q][p-1] - imos[p-1][q] + imos[p-1][p-1])
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    # 横方向に累積和
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    # 縦方向に累積和
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field


n,m,q = li()
grid = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    l,r = li()
    grid[l][r] += 1
    
grid = cum_2d(grid)


for _ in range(q):
    p,q = li()
    print(grid[q][q] - grid[q][p-1] - grid[p-1][q] + grid[p-1][p-1])

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5)

def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    # 横方向に累積和
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    # 縦方向に累積和
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field

n,m,q = li()
grid = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    l,r = li()
    grid[l][r] += 1
    
grid = cum_2d(grid)

for _ in range(q):
    p,q = li()
    print(grid[q][q] + grid[p-1][p-1] - grid[q][p-1] - grid[p-1][q])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np

ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()


N, M, Q = ds_in()

section = np.zeros((N, N), dtype=int)
for _ in range(M):
    p, q = ds_in()
    section[N-p, q-1] += 1

cumlist = np.cumsum(np.cumsum(section, axis=0), axis=1)

query = []
for _ in range(Q):
    query.append(ds_in())

for q in query:
    print(cumlist[N-q[0], q[1]-1])

Submission status: Accepted

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

N, M, Q = [int(elem) for elem in fin().split()]
trains = [[int(elem) - 1 for elem in fin().split()] for _ in range(M)]
queries = [[int(elem) - 1 for elem in fin().split()] for _ in range(Q)]

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

cuml_1D = [[0] * N for _ in range(N)]
# vertical
for j in range(N):
    cuml_sum = 0
    for i in reversed(range(j + 1)):
        cuml_sum += map_2D[i][j]
        cuml_1D[i][j] = cuml_sum

cuml_2D = [[0] * N for _ in range(N)]
# horizontal
for i in range(N):
    cuml_sum = 0
    for j in range(N):
        cuml_sum += cuml_1D[i][j]
        cuml_2D[i][j] = cuml_sum

for p, q in queries:
    print(cuml_2D[p][q])

Submission status: Accepted

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

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

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

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

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

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

Submission status: Accepted

Solution code:
from itertools import accumulate

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

Station=[[0 for x in range(N+2)] for y in range(N+2)]

for i in range(M):
  s,t=map(int,input().split())
  Station[1][t]+=1
  Station[s+1][t]-=1
  Station[1][N+1]+=1
  Station[s+1][N+1]-=1

ST1 = [list(accumulate(l)) for l in zip(*Station)]
ST2 = [list(accumulate(l)) for l in zip(*ST1)]
  
for i in range(Q):
  l,r=map(int,input().split())
  print(ST2[l][r])

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(1,N+1):
    for j in range(1,N+1):
        table[i][j] += table[i-1][j] + table[i][j-1] - table[i-1][j-1]
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())

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

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

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

memo=[[-1]*(n+1) for _ in range(n+1)]

for i in range(q):
    P,Q=map(int,input().split())
    if(memo[P][Q]!=-1):
        print(memo[P][Q])
        continue
    tmp=0
    for j in range(Q,P-1,-1):
        tmp+=mylist[j][Q]
        memo[j][Q]=tmp
    print(tmp)

Submission status: Accepted

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


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        for x, y in points:
            self.G[x][y] += 1

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(N, N)
R2D.load(X)
R2D.calc()

for q in range(Q):
    p, q = map(int, input().split())
    p, q = p - 1, q - 1
    print(R2D.get(p, p, q, q))

Submission status: Accepted

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

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

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

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

m()

Submission status: Accepted

Solution code:
# setting
from itertools import accumulate

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

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

for i in range(n-2, -1, -1):
    for j, acc in enumerate(accumulate(LR[i])):
        LR[i][j] = acc  + (0 if j == 0 else LR[i+1][j-1])

res = list()
for i in range(q):
    p,q = map(int, input().split())
    res.append(LR[p-1][q-p])

for r in res:
    print(r)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]

N,M,Q = inpl()
LR = [inpl() for i in range(M)]
pq = [inpl() for i in range(Q)]

H = [[0]*N for i in range(N)]
S = [[0]*N for i in range(N)]

for i in range(M):
    H[LR[i][0]-1][LR[i][1]-1] += 1

S[0][0] = H[0][0]
for i in range(N):
    for j in range(N-1):
        S[i][j+1] = S[i][j] + H[i][j+1]

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

for i in range(Q):
    if pq[i][1] == 1:
        print(S[0][0])
    elif pq[i][0] == 1:
        print(S[pq[i][1]-1][pq[i][1]-1])
    else:
        ans = S[pq[i][1]-1][pq[i][1]-1] - S[pq[i][1]-1][pq[i][0]-2] - S[pq[i][0]-2][pq[i][1]-1] + S[pq[i][0]-2][pq[i][0]-2]
        print(ans)

Submission status: Accepted

Solution code:
import itertools
import numpy as np

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

for _ in range(M):
    L,R=list(map(int,input().split()))
    trains[N-L][R-1]+=1
trains=np.array(trains)
for i in range(N):
    trains[i]=np.array(list(itertools.accumulate(trains[i])))
for i in range(N):
    trains[:,i]=np.array(list(itertools.accumulate(trains[:,i])))

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

Submission status: Accepted

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


class Ruisekiwa2D:
    def __init__(self, h, w):
        self.H = h
        self.W = w
        self.G = [[0] * w for _ in range(h)]

    def load(self, points):
        # 問題によってイメージしやすいよう書き換えてください
        # load終了時にcalcが呼ばれることに注意してください
        for x, y in points:
            self.G[x][y] += 1

        self.calc()

    def load_imos(self, points):
        # pointsは[[左上h, 左上w, 右下h, 右下w], ...]であること
        for i1, j1, i2, j2 in points:
            self.G[i1][j1] += 1  # 左上
            if j2 + 1 < self.W:  # 右上
                self.G[i1][j2+1] -= 1
            if i2 + 1 < self.H:
                self.G[i2+1][j1] -= 1  # 左下
            if j2 + 1 < self.W and i2 + 1 < self.H:  # 右下
                self.G[i2+1][j2+1] += 1

        self.calc()

    def calc(self):
        for y in range(self.W):
            for x in range(1, self.H):
                self.G[x][y] += self.G[x-1][y]

        for y in range(1, self.W):
            for x in range(self.H):
                self.G[x][y] += self.G[x][y-1]

    def get(self, i1, j1, i2, j2):
        if i1 > i2 or j1 > j2 or i1 < 0 or j1 < 0 or i2 < 0 or j2 < 0:
            return 0
        elif i1 > 0 and j1 > 0:
            return self.G[i2][j2] - self.G[i1-1][j2] - self.G[i2][j1-1] + self.G[i1-1][j1-1]
        elif i1 <= 0 < j1:
            return self.G[i2][j2] - self.G[i2][j1-1]
        elif j1 <= 0 < i1:
            return self.G[i2][j2] - self.G[i1 - 1][j2]
        else:
            return self.G[i2][j2]


R2D = Ruisekiwa2D(N, N)
I = []
for i in range(M):
    l, r = map(int, input().split())
    l, r = l -1, r- 1
    I.append((l, r))
R2D.load(I)

for i in range(Q):
    p, q = map(lambda x: int(x) - 1, input().split())
    print(R2D.get(p, p, q, q))

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def cum_2d(field:list):
    row = len(field)
    col = len(field[0])
    
    # 横方向に累積和
    for r in range(row):
        for c in range(col-1):
            field[r][c+1] += field[r][c]
    
    # 縦方向に累積和
    for c in range(col):
        for r in range(row-1):
            field[r+1][c] += field[r][c]
            
    return field
            

n,m,q = li()
train = []
query = []

field = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    train.append(tuple(li()))
    
for _ in range(q):
    query.append(tuple(li()))
    
for ts, tt in train:
    field[ts][tt] += 1
    
field = cum_2d(field)
        
for qs,qt in query:
    print(field[qt][qt] - field[qt][qs-1] - field[qs-1][qt] + field[qs-1][qs-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n,m,q = li()
train = []
query = []

field = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    train.append(tuple(li()))
    
for _ in range(q):
    query.append(tuple(li()))
    
for ts, tt in train:
    field[ts][tt] += 1
    
for r in range(n+1):
    for c in range(n):
        field[r][c+1] += field[r][c]
        
for c in range(n+1):
    for r in range(n):
        field[r+1][c] += field[r][c]
        
for qs,qt in query:
    print(field[qt][qt] - field[qt][qs-1] - field[qs-1][qt] + field[qs-1][qs-1])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
n,m,q = map(int, input().split())

d = [[0 for _ in range(n+1)] for _ in range(n+1)]

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

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

# print(d)
for o in pq:
    print(d[o[0]][o[1]])

Submission status: Accepted

Solution code:
#
#	106 D - AtCoder Express 2
#

N, M, Q = [int(_) for _ in input().split()]
listN = [[0] * (N+1) for i in range(N+1)]
listNsum = [[0] * (N+1) for i in range(N+1)]

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

#累積和計算
for iIdx, iList in enumerate(listN):
	for jIdx, jList in enumerate(iList):
		if jIdx == 0:
			listNsum[iIdx][jIdx] = listN[iIdx][jIdx]
		else:
			listNsum[iIdx][jIdx] = listNsum[iIdx][jIdx-1] + listN[iIdx][jIdx]


retList = []
for i in range(Q):
	p, q = [int(_) for _ in input().split()]
	sumv = 0
	for j in range(p, q+1):
		sumv += listNsum[j][q] - listNsum[j][p-1]
	retList.append(sumv)

for i in retList:
	print(i)

Submission status: Accepted

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

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

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

for L in range(1, N + 1):
    for R in range(1, N + 1):
        T[L][R] += T[L - 1][R]
        T[L][R] += T[L][R - 1]
        T[L][R] -= T[L - 1][R - 1]

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

Submission status: Accepted

Solution code:
N, M, Q = [int(_) for _ in input().split()]

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

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

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

Submission status: Accepted

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

train_map = [[0] * (N + 1) for i in range(N + 1)]
for l, r in T:
    train_map[l][r] += 1

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


for p, q in Q:
    print(cumsum[q][q] - cumsum[p-1][q])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
n, m, q = map(int, input().split())
cities = [[0 for _ in range(n+1)] for _ in range(n+2)]
trains = [list(map(int, input().split())) for _ in range(m)]
quests = [list(map(int, input().split())) for _ in range(q)]

for train in trains:
    x, y = train[0], train[1]
    cities[x][y] += 1

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

for quest in quests:
    p, q = quest[0], quest[1]
    print(cities[p][q])

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
from bisect import bisect_left

def main():
	n, m, q = list(map(int, input().split()))
	trains = [list(map(int, input().split())) for _ in range(m)]
	queries = [list(map(int, input().split())) for _ in range(q)]
	
	xmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	cmt = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
	
	for train in trains:
		xmt[train[0]][train[1]] += 1

	for i in range(1, n + 1):
		for j in range(1, n + 1):
			cmt[i][j] = cmt[i][j - 1] + (cmt[i - 1][j] - cmt[i - 1][j - 1]) + xmt[i][j] 
	
	for query in queries:
		i, j = query
		ans = cmt[j][j] - cmt[i - 1][j] - cmt[j][i - 1] + cmt[i - 1][i - 1]
		print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

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

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

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

tmp = []
for i in range(q):
    p, q = map(int, input().split())
    tmp.append((p, q))

for p, q in tmp:
    print(ans[n-q][p-1])

Submission status: Accepted

Solution code:
def ary(r, c, val=False): return [[val for _ in range(c)] for _ in range(r)]
def nl(): return list(map(int, input().split()))

n, m, q = nl()
M = ary(n + 1, n + 1, 0)
for _ in range(m):
    l, r = nl()
    M[l][r] += 1

for L in range(1, n + 1):
    for R in range(1, n + 1):
        M[L][R] += M[L - 1][R]
        M[L][R] += M[L][R - 1]
        M[L][R] -= M[L - 1][R - 1]

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

Submission status: Accepted

Solution code:
from itertools import accumulate as acc
f = lambda: map(int,input().split())
n,m,q = f()
d = [[0 for _ in range(n)]for _ in range(n)]
for _ in range(m):
    l,r = f()
    d[l-1][r-1] += 1
P,Q = [],[]
for _ in range(q):
    a, b = f()
    P.append(a)
    Q.append(b)

for i in range(n):
    d[i] = list(acc(d[i]))
for i in range(n-2,-1,-1):
    for j in range(n):
        d[i][j] += d[i+1][j]
for i in range(q):
    print(d[P[i]-1][Q[i]-1])

Submission status: Accepted

Solution code:
f = lambda: map(int,input().split())
n,m,q = f()
d = [[0 for _ in range(n)]for _ in range(n)]
for _ in range(m):
    l,r = f()
    d[l-1][r-1] += 1
P,Q = [],[]
for _ in range(q):
    a, b = f()
    P.append(a)
    Q.append(b)

for i in range(n):
    for j in range(1,n):
        d[i][j] += d[i][j-1]
for i in range(n-2,-1,-1):
    for j in range(n):
        d[i][j] += d[i+1][j]
for i in range(q):
    print(d[P[i]-1][Q[i]-1])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import accumulate

n,m,q = li()
grid = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    l,r = li()
    grid[0][r] += 1
    if l+1 <= n:
        grid[l+1][r] -= 1
    
imos = [list(accumulate(grid[row])) for row in range(n+1)]
for row in range(n):
    for col in range(n+1):
        imos[row+1][col] += imos[row][col]
        
for _ in range(q):
    p,q = li()
    print(imos[p][q])

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

def li(): return [int(x) for x in stdin.readline().split()]
def li_(): return [int(x)-1 for x in stdin.readline().split()]
def lf(): return [float(x) for x in stdin.readline().split()]
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(ns())
def nf(): return float(ns())

from itertools import accumulate

n,m,q = li()
grid = [[0 for _ in range(n+1)] for _ in range(n+1)]

for _ in range(m):
    l,r = li()
    grid[l][r] += 1
    
grid_cum = [list(accumulate(grid[row])) for row in range(n+1)]
for row in range(n):
    for col in range(n+1):
        grid_cum[row+1][col] += grid_cum[row][col]
        
for _ in range(q):
    p,q = li()
    print(grid_cum[q][q] - grid_cum[p-1][q] - grid_cum[q][p-1] + grid_cum[p-1][p-1])

Submission status: Accepted

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

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

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


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

Submission status: Accepted

Solution code:
import numpy as np


def main():
    city_count, express_count, query_count = map(int, input().split())

    city_list = np.zeros((city_count + 1, city_count + 1), np.int_)

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

    city_list.cumsum(1, out=city_list)
    city_list.cumsum(0, out=city_list)

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


if __name__ == '__main__':
    main()