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:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) # 1-indexed

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

n, m, Q = map(int, input().split())
X = []
A = []
for i in range(m):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    A.append(l)
    A.append(r)
    X.append((l, r, 0, i))
for i in range(Q):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    A.append(p)
    A.append(q)
    X.append((p, q, 1, i))
X.sort(key=lambda x: (x[1], x[2]))

A = list(set(A))
A.sort()
d = {}
for i, a in enumerate(A):
    d[a] = i

bit = BIT(550)
ans = [-1]*Q
for l, r, t, i in X:
    l, r = d[l], d[r]
    if t == 0:
        bit.add(l, 1)
    else:
        ans[i] = bit.sum(l, r+1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
class BIT:
    def __init__(self, n):
        self.n = n
        self.bit = [0]*(self.n+1) # 1-indexed

    def init(self, init_val):
        for i, v in enumerate(init_val):
            self.add(i, v)

    def add(self, i, x):
        # i: 0-indexed
        i += 1 # to 1-indexed
        while i <= self.n:
            self.bit[i] += x
            i += (i & -i)

    def sum(self, i, j):
        # return sum of [i, j)
        # i, j: 0-indexed
        return self._sum(j) - self._sum(i)

    def _sum(self, i):
        # return sum of [0, i)
        # i: 0-indexed
        res = 0
        while i > 0:
            res += self.bit[i]
            i -= i & (-i)
        return res

import sys
import io, os
input = sys.stdin.buffer.readline
#input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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, 0, i))
for i in range(Q):
    p, q = map(int, input().split())
    p, q = p-1, q-1
    X.append((p, q, 1, i))
X.sort(key=lambda x: (x[1], x[2]))
bit = BIT(550)
ans = [-1]*Q
for l, r, t, i in X:
    if t == 0:
        bit.add(l, 1)
    else:
        ans[i] = bit.sum(l, r+1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
import io, os
#input = sys.stdin.buffer.readline
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline

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

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+1][j] + s[i][j+1] - s[i][j] + C[i][j]

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

Submission status: Accepted

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

def main():
    n, m, q = map(int, input().split())

    # Two-dimensional Cumulative Sum
    cs = [[0] * (n+1) for _ in range(n+1)]

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

    for l in range(1, n+1):
        for r in range(1, n+1):
            cs[l][r] += cs[l][r-1]
        for r in range(1, n+1):
            cs[l][r] += cs[l-1][r]

    ans = [-1] * q
    for lap in range(q):
        l, r = map(int, input().split())
        ans[lap] = cs[n][r] - cs[l-1][r]

    for i in ans:
        print(i)

main()

Submission status: Accepted

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

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

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

from sys import stdin
input = stdin.buffer.readline

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

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

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

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

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

    for i in ans:
        print(i)

main()

Submission status: Accepted

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

for i in range(m):
  x,y=map(int,input().split())
  a[x-1][y-1]+=1
  
for j in range(n):
  for k in range(1,n):
    a[j][k]=a[j][k]+a[j][k-1]
    
for l in range(q):
  ans=0
  L,R=map(int,input().split())
  for g in range(L-1,R):
    ans+=a[g][R-1]
  print(ans)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
#D - AtCoder Express 2
#2次元累積和
import sys 
from itertools import accumulate 
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N,M,Q = map(int,readline().split())
data = [[0]*(N+1) for _ in range(N+1)]
#入力
for _ in range(M):
    l,r = map(int,readline().split())
    data[l][r] += 1
    
#累積和
for i in range(N+1):
    for j in range(N):
        data[i][j+1] += data[i][j]
        
#入力    
for _ in range(Q):
    p,q = map(int,readline().split())
    ans = 0
    for i in range(p,q+1):
        ans += (data[i][q] - data[i][p-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)]
arr = [[0 for _ in range(n+1)] for _ in range(n+1)]
for l,r in lr:
    arr[l][r]+=1
rui = [[0 for _ in range(n+1)] for _ in range(n+1)]

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

for p,q in pq:
    cnt = rui[q][q] - rui[p-1][q] - rui[q][p-1] + rui[p-1][p-1]
    print(cnt)

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)]
arr = [[0 for _ in range(n)] for _ in range(n)]
for l,r in lr:
    arr[l-1][r-1]+=1
rui = [[0 for _ in range(n)] for _ in range(n)]

rui[0][0] = arr[0][0]

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

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

for p,q in pq:
    p-=1
    q-=1
    cnt = rui[q][q]
    if p!=0:
        cnt-=rui[p-1][q]
        cnt-=rui[q][p-1]
        cnt+=rui[p-1][p-1]

    print(cnt)

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

acc = [[0] * (n + 1) for _ in range(n + 1)]
for l, r in lr:
    acc[l][r] += 1
for i in range(n):
    for j in range(n):
        tmp = acc[i][j + 1] + acc[i + 1][j] - acc[i][j]
        acc[i + 1][j + 1] += tmp

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

Submission status: Accepted

Solution code:
from copy import deepcopy

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

cnt = [[0] * (n + 1) for _ in range(n + 1)]
for l, r in lr:
    cnt[l][r] += 1

acc = deepcopy(cnt)
for i in range(n):
    for j in range(n):
        tmp = acc[i][j + 1] + acc[i + 1][j] - acc[i][j]
        acc[i + 1][j + 1] += tmp

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

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

cnt = [[0] * (n + 1) for _ in range(n + 1)]
for l, r in lr:
    cnt[l][r] += 1

acc = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(n):
        tmp = acc[i][j + 1] + acc[i + 1][j] - acc[i][j]
        acc[i + 1][j + 1] = tmp + cnt[i + 1][j + 1]

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

Submission status: Accepted

Solution code:
from numpy import *
N,M,Q = map(int,input().split())
G = zeros((N,N),int)

for m in range(M):
  l,r = map(int,input().split())
  G[N-l][r-1]+=1
  
G = cumsum(cumsum(G,axis=0),axis=1)

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

Submission status: Accepted

Solution code:
import itertools

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

LR=[[0]*(n+1) for i in range(n+1)]

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

for i in range(n):
  LR[i]=list(itertools.accumulate(LR[i]))


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

  print(ans)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
"""
区間ごとに前処理しておけばよい
"""
#memo[i][j] => iから出発し、jまでのどこかで終点する電車の数
N,M,Q = map(int,input().split())
memo = [[0]*(N+1) for _ in range(N+1)]
for _ in range(M):
    l,r = map(int,input().split())
    for j in range(r,N+1):
        memo[l][j] += 1

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

Submission status: Accepted

Solution code:
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(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):
  q,p=map(int,input().split())
  print(a[p][p]-a[p][q-1]-a[q-1][p]+a[q-1][q-1])

Submission status: Accepted

Solution code:
"""ABC106D AtCoder Express2 diff:1306
"""

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

for _ in range(Q):
    p, q = map(int, input().split())
    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 numpy as np
N, M, Q = map(int, input().split()) # N個の都市、M本の列車、Q個のクエリ
grid = np.zeros((N+1, N+1), dtype=np.int64)
query = []
for _ in range(M):
    L, R = map(int, input().split())
    grid[L, R] += 1
cum_grid = grid.cumsum(axis=0).cumsum(axis=1)

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

for ans in ans_list:
    print(ans)

Submission status: Accepted

Solution code:


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


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


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

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

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

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


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
N, M, Q = map(int, input().split())
C = [[0]*N for _ in range(N)]
for _ in range(M):
    L, R = map(int, input().split())
    C[L-1][R-1] += 1
S = [[0]*(N+1) for _ in range(N+1)]
for r in range(N):
    for l in reversed(range(N)):
        S[l][r] = S[l+1][r] + C[l][r]
D = [[0]*(N+1) for _ in range(N+1)]
for l in range(N):
    for r in range(N):
        D[l][r] = D[l][r-1] + S[l][r]
for _ in range(Q):
    p, q = map(int, input().split())
    print(D[p-1][q-1])

Submission status: Accepted

Solution code:
def cum2D(a, H, W):
    cum = [[0]*(W+1) for _ in range(H+1)]
    for i in range(H):
        for j in range(W):
            cum[i+1][j+1] = cum[i][j+1] + cum[i+1][j] - cum[i][j] + a[i+1][j+1]
    return cum
    
n, m, q = map(int, input().split())
trains = [tuple(map(int, input().split())) for _ in range(m)]  #;print(trains)
a = [[0]*(n+1) for j in range(n+1)]
for k in range(m):
    start, stop = trains[k]
    a[start][stop] += 1
cum = cum2D(a, n, n)          #;print2D(a, n+1) ;print() ;print2D(cum, n+1)

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

Submission status: Accepted

Solution code:
import sys
import math
import copy
from heapq import heappush, heappop, heapify
from functools import cmp_to_key
from bisect import bisect_left, bisect_right
from collections import defaultdict, deque, Counter
# sys.setrecursionlimit(1000000)

# input aliases
input = sys.stdin.readline
getS = lambda: input().strip()
getN = lambda: int(input())
getList = lambda: list(map(int, input().split()))
getZList = lambda: [int(x) - 1 for x in input().split()]

INF = float("inf")
MOD = 10**9 + 7
divide = lambda x: pow(x, MOD-2, MOD)

class BIT():
    # A1 ... AnのBIT(1-indexed)
    def __init__(self, n):
        self.n = n
        self.BIT = [0] * (n + 2)

    # A1 ~ Aiまでの和 O(logN)
    def query(self, idx):
        res_sum = 0
        while idx > 0:
            res_sum += self.BIT[idx]
            idx -= idx & (-idx)
        return res_sum

    # Ai += x O(logN)
    def update(self, idx, x):
        # print(idx)
        while idx <= self.n:
            # print(idx)
            self.BIT[idx] += x
            idx += idx & (-idx)
        return

    def show(self):
        print(self.BIT)


def solve():
    n,m,q = getList()
    bt = BIT(n+1)
    sya = [defaultdict(int) for i in range(n+1)]
    for i in range(m):
        a,b = getList()
        sya[a][b] += 1
        bt.update(b, 1)

    si = []
    for i in range(q):
        l, r = getList()
        si.append((l, r, i))

    si.sort()
    ans = [0 for i in range(q)]

    cur = 1
    for ss in si:
        l, r, id = ss
        while(l > cur):
            for kk, vv in sya[cur].items():
                bt.update(kk, -vv)
                n -= vv
            cur += 1
        ans[id] = bt.query(r)

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





def main():
    n = getN()
    for _ in range(n):
        solve()

    return
if __name__ == "__main__":
    # main()
    solve()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def cin():  return list(map(int,input().split()))

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

for _ in range(M):
    a, b = cin()
    v[a - 1][b - 1] += 1;

for i in range(Q):
    a, b = cin()
    p[i][0] = a - 1;
    p[i][1] = b - 1;
    
def d2_add(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

def d2_calc(da, x1, y1, x2, y2):
    if x1 > x2 or y1 > y2:  return 0
    if x1 == 0 and y1 == 0:  return da[x2][y2]
    if x1 == 0:  return da[x2][y2] - da[x2][y1 - 1]
    if y1 == 0:  return da[x2][y2] - da[x1 - 1][y2]
    return da[x2][y2] - da[x1 - 1][y2] - da[x2][y1 - 1] + da[x1 - 1][y1 - 1]

ret = d2_add(v)
for i in range(Q):
    ans = d2_calc(ret, p[i][0], p[i][0], p[i][1], p[i][1])
    print(ans)

Submission status: Accepted

Solution code:
def cin():  return list(map(int,input().split()))

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

for _ in range(M):
    a, b = cin()
    v[a - 1][b - 1] += 1;

for i in range(Q):
    a, b = cin()
    p[i][0] = a - 1;
    p[i][1] = b - 1;
    
def d2_add(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

def d2_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 = d2_add(v)
for i in range(Q):
    ans = d2_calc(ret, p[i][0], p[i][0], p[i][1], p[i][1])
    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
    
def d2_add(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

def d2_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 = d2_add(a)
for i in range(Q):
    ans = d2_calc(ret, p[i], p[i], q[i], q[i])
    print(ans)

Submission status: Accepted

Solution code:
import sys

import numba as nb
import numpy as np

input = sys.stdin.readline


@nb.njit("i8[:](i8,i8,i8,i8[:,:],i8[:,:])", cache=True)
def solve(N, M, Q, LR, pq):
    S = np.zeros(shape=(N + 1, N + 1), dtype=np.int64)
    for i in range(M):
        L, R = LR[i]
        S[L][R] += 1
    for i in range(N + 1):
        S[i] = np.cumsum(S[i])

    ans = np.zeros(shape=Q, dtype=np.int64)
    for i in range(Q):
        p, q = pq[i]
        for j in range(p, q + 1):
            ans[i] += S[j][q] - S[j][p - 1]

    return ans


def main():
    N, M, Q = map(int, input().split())
    LR = np.zeros(shape=(M, 2), dtype=np.int64)
    for i in range(M):
        LR[i] = input().split()
    pq = np.zeros(shape=(Q, 2), dtype=np.int64)
    for i in range(Q):
        pq[i] = input().split()

    ans = solve(N, M, Q, LR, pq)

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


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#和のセグ木にするときは以下の関数を定義する必要あり。
def segfunc(x,y):
  return x+y

class SegmentTree(object):
    def __init__(self, A, dot, unit):
        n = 1 << (len(A) - 1).bit_length()
        tree = [unit] * (2 * n)
        for i, v in enumerate(A):
            tree[i + n] = v
        for i in range(n - 1, 0, -1):
            tree[i] = dot(tree[i << 1], tree[i << 1 | 1])
        self._n = n
        self._tree = tree
        self._dot = dot
        self._unit = unit

    def __getitem__(self, i):
        return self._tree[i + self._n]

    def update(self, i, v):
        i += self._n
        self._tree[i] = v
        while i != 1:
            i >>= 1
            self._tree[i] = self._dot(self._tree[i << 1], self._tree[i << 1 | 1])

    def add(self, i, v):
        self.update(i, self[i] + v)

    def sum(self, l, r): #これで[l,r)から取り出す。
        l += self._n
        r += self._n
        l_val = r_val = self._unit
        while l < r:
            if l & 1:
                l_val = self._dot(l_val, self._tree[l])
                l += 1
            if r & 1:
                r -= 1
                r_val = self._dot(self._tree[r], r_val)
            l >>= 1
            r >>= 1
        return self._dot(l_val, r_val)


N,M,Q = map(int,input().split())
A = []
for i in range(M):
  a,b = map(int,input().split())
  A.append([a,b,-1]) #-1は鉄道
for i in range(Q):
  a,b = map(int,input().split())
  A.append([a,b,i]) #iはクエリのID。出力でIDの順に並べる
A.sort(key=lambda x : x[1]) #終点でソート
MAX = 510
Range = [0 for _ in range(MAX)]
Tree = SegmentTree(Range,segfunc,0)
#print(A)
ans = [-1 for _ in range(Q)]
for i in range(M+Q):
  a,b,ID = A[i]
  if ID == -1:
    Tree.add(a,1)
  else:
    temp = Tree.sum(a,b+1) #セグ木の取得は開区間なのでb+1
    ans[ID] = temp
#print(ans)
print(*ans,sep="\n")

Submission status: Accepted

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

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

com = [[0] * 502 for i in range(502)]

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

for i in range(502):
    for j in range(1,502):
        com[i][j] += com[i][j-1]

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

Submission status: Accepted

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

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

com = [[0] * 502 for i in range(502)]

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

for i in range(502):
    for j in range(1,502):
        com[i][j] += com[i][j-1]

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

Submission status: Accepted

Solution code:
from collections import defaultdict
N, M, Q = map(int, input().split())
l2r = defaultdict(int)
l2acc = [[0]*(N+1) for _ in range(N)]
r2acc = [[0]*(N+1) for _ in range(N)]
for _ in range(M):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    l2r[(l, r)] += 1
queries = []
for _ in range(Q):
    l, r = map(int, input().split())
    l, r = l-1, r-1
    queries.append((l, r))

for l in range(N):
    acc = 0
    for r in range(l, N):
        acc += l2r[(l, r)]
        l2acc[l][r] = acc

for r in range(N):
    acc = 0
    for l in range(r, -1, -1):
        acc += l2acc[l][r]
        r2acc[l][r] =acc

for l, r in queries:
    print(r2acc[l][r])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10010010)

def abc106_d():
    n, m, q = map(int, input().split())
    table = [[0]*(n+1) for _ in range(n+1)]
    for _ in range(m):
        l, r = map(int, input().split())
        table[l][r] += 1
    query = [tuple(map(int, input().split())) for _ in range(q)]

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

    def calc(l, r):
        nonlocal dp
        if l == 0 or r == 0: return 0
        if dp[l][r] != -1: return dp[l][r]
        res = calc(l-1, r) + calc(l, r-1) - calc(l-1, r-1) + table[l][r]
        dp[l][r] = res
        return res

    for p, q in query:
        ans = calc(q, q) - calc(q, p-1) - calc(p-1, q) + calc(p-1, p-1)
        print(ans)

if __name__ == '__main__':
    abc106_d()

Submission status: Accepted

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

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

C = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        C[i][j] = C[i-1][j] + C[i][j-1] + S[i][j] - C[i-1][j-1]

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

Submission status: Accepted

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


def main():
    n, m, q = map(int, input().split())
    counts = np.zeros((n+1, n+1), dtype=np.int32)
    for _ in range(m):
        from_, to = map(int, input().split())
        counts[:from_+1, to] += 1

    counts = np.cumsum(counts, axis=1)

    queries = np.array([list(map(int, input().split())) for _ in range(q)])
    ps = queries[:, 0]
    qs = queries[:, 1]
    res = counts[ps, qs]
    print(*res, sep="\n")


if __name__ == "__main__":
    main()

Submission status: Accepted

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

for m in range(M):
  L, R = map(int, input().split())
  S[L][R] += 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 i in range(Q):
  p, q = map(int, input().split())
  print(S[q][q] - S[p-1][q] - S[q][p-1] + S[p-1][p-1])

Submission status: Accepted

Solution code:
#区間の問題は累積和か尺取り法
#区間で条件を満たすものの個数→累積和
#区間の数、条件を満たす区間の最大値最小値→尺取り法
#今回は区間で条件を満たすものの総和→累積和
#二つの端点を同時に扱わなくてはならない
#列車の始まりが区間に含まれるかつ列車の終わりが区間に含まれて＋１である
#つまり二次元累積和を書けばいい
n,m,q=list(map(int,input().split()))
ruiseki=[[0 for i in range(n+1)] for i in range(n+1)]
for i in range(m):
  l,r=list(map(int,input().split()))
  ruiseki[l][r]=ruiseki[l][r]+1
#二次元累積和を計算する
for i in range(0,n+1):
  for j in range(1,n+1):
    ruiseki[i][j]=ruiseki[i][j]+ruiseki[i][j-1]
for i in range(1,n+1):
  for j in range(n+1):
    ruiseki[i][j]=ruiseki[i-1][j]+ruiseki[i][j]

#各クエリに対して累積和を計算
for i in range(q):
  p,q=list(map(int,input().split()))
  print(ruiseki[q][q]-ruiseki[p-1][q]-ruiseki[q][p-1]+ruiseki[p-1][p-1])

Submission status: Accepted

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

grid_acc[0][0] = grid[0][0]
for i in range(1, n):
    grid_acc[i][0] = grid_acc[i-1][0] + grid[i][0]
    grid_acc[0][i] = grid_acc[0][i-1] + grid[0][i]

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

for i in range(Q):
    p, q = [int(i) for i in input().split()]
    if p == 1:
        print(grid_acc[q-1][q-1])
    else:
        print(grid_acc[q-1][q-1] - grid_acc[p-2][q-1] - grid_acc[q-1][p-2] + grid_acc[p-2][p-2])

Submission status: Accepted

Solution code:
# 20-08-06再トライ
import sys
input = sys.stdin.readline
from itertools import accumulate

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

cum = [list(accumulate(train[i])) for i in range(N + 1)]
del train
cum = list(zip(*cum))
cum = [list(accumulate(cum[j])) for j in range(N + 1)]

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

Submission status: Accepted

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

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

train = [[0] * (N + 1) for i in range(N + 1)]

for i in range(M):
  L,R = map(int,readline().split())
  train[L][R] += 1
  
for i in range(N + 1):
  for j in range(1, N + 1):
    train[i][j] += train[i][j - 1]
    
for j in range(N + 1):
  for i in range(1, N + 1):
    train[i][j] += train[i - 1][j]

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