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

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


###############################################################################


def main():
    n, m, q = intin()
    lrlist = intinl(m)
    qlist = intinl(q)

    tsum = defaultdict(lambda: defaultdict(int))
    for l, r in lrlist:
        tsum[l][r] += 1

    ans = defaultdict(lambda: defaultdict(int))
    for span in range(0, n):
        for i in range(1, n + 1):
            if i + span > n:
                continue
            if span == 0:
                ans[i][i] = tsum[i][i]
                continue
            ans[i][i+span] = ans[i][i+span-1] + ans[i+1][i+span] - ans[i+1][i+span-1] + tsum[i][i+span]

    for p, q in qlist:
        print(ans[p][q])


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

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

for _ in range(M):
    p, q = map(int, input().rstrip().split(' '))
    count[p][q] += 1

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

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

Submission status: Accepted

Solution code:
import sys
stdin = sys.stdin

sys.setrecursionlimit(10 ** 7)

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()
field = [[0]*(n+1) for _ in range(n+1)]

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

field = cum_2d(field)

for _ in range(q):
    pi, qi = li()
    print(field[qi][qi] - field[qi][pi-1] - field[pi-1][qi] + field[pi-1][pi-1])

Submission status: Accepted

Solution code:
n,m,Q=map(int,input().split())
LR=[]
ans=[]
for i in range(n):
    sub_list=[]
    for j in range(n):
        sub_list.append(0)
    LR.append(sub_list)
    ans.append(sub_list)
for i in range(m):
    l,r=map(int,input().split())
    LR[l-1][r-1]=LR[l-1][r-1]+1
for i in range(n)[::-1]:
    Sum=0
    for j in range(i,n):
        if i==j:
            ans[i][j]=LR[i][j]
            Sum=LR[i][j]
        else:
            Sum=Sum+LR[i][j]
            ans[i][j]=Sum+ans[i+1][j]
for i in range(Q):
    p,q=map(int,input().split())
    print(ans[p-1][q-1])

Submission status: Accepted

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

Submission status: Accepted

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

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

li2 = [[0 for _ in range(n)] for _ in range(n)]
li3 = [[0 for _ in range(n)] for _ in range(n)]

for i in range(n):
    for j in range(n):
        if j == 0:
            li2[i][j] = li[i][j]
        else:
            li2[i][j] = li2[i][j-1] + li[i][j]

for i in range(n):
    for j in range(n):
        if i == 0:
            li3[i][j] = li2[i][j]
        else:
            li3[i][j] = li3[i-1][j] + li2[i][j]

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

Submission status: Accepted

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

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

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

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
def f(nc, nt, nq):
    dp = [[0] * (nc + 1) for _ in range(nc + 1)]
    for _ in range(nt):
        l, r = map(int, input().split())
        dp[l][r] += 1
    for i in range(1, nc + 1):
        dpi = dp[i]
        s = dpi[0]
        for j in range(1, nc + 1):
            dpi[j] = s = dpi[j] + s
    for j in range(1, nc + 1):
        s = dp[0][j]
        for i in range(1, nc + 1):
            dp[i][j] = s = dp[i][j] + s
    for _ in range(nq):
        l, r = map(int, input().split())
        print(dp[r][r] - dp[l - 1][r] - dp[r][l - 1] + dp[l - 1][l - 1])


nc, nt, nq = map(int, input().split())
f(nc, nt, nq)

Submission status: Accepted

Solution code:
def f(nc, nt, nq):
    dp = [[0] * (nc + 1) for _ in range(nc + 1)]
    for _ in range(nt):
        l,r=map(int, input().split())
        dp[l][r] += 1
    q = [list(map(int, input().split())) for _ in range(nq)]
    for i in range(1, nc + 1):
        dpi = dp[i]
        s = dpi[0]
        for j in range(1, nc + 1):
            dpi[j] = s = dpi[j] + s
    for j in range(1, nc + 1):
        s = dp[0][j]
        for i in range(1, nc + 1):
            dp[i][j] = s = dp[i][j] + s
    for l, r in q:
        print(dp[r][r] - dp[l - 1][r] - dp[r][l - 1] + dp[l - 1][l - 1])


nc, nt, nq = map(int, input().split())
f(nc, nt, nq)

Submission status: Accepted

Solution code:
import numpy as np


def f(nc, nt, nq):
    t = [list(map(int, input().split())) for _ in range(nt)]
    q = [list(map(int, input().split())) for _ in range(nq)]
    dp = np.zeros((nc + 1, nc + 1), dtype="i8")
    for l, r in t:
        dp[l][r] += 1
    dp = np.cumsum(np.cumsum(dp, axis=0), axis=1)
    for l, r in q:
        print(dp[r][r] - dp[l - 1][r] - dp[r][l - 1] + dp[l - 1][l - 1])


nc, nt, nq = map(int, input().split())
f(nc, nt, nq)

Submission status: Accepted

Solution code:
def f(nc, nt, nq):
    t = [list(map(int, input().split())) for _ in range(nt)]
    q = [list(map(int, input().split())) for _ in range(nq)]
    dp = [[0] * (nc + 1) for _ in range(nc + 1)]
    for l, r in t:
        dp[l][r] += 1
    for i in range(1, nc + 1):
        dpi = dp[i]
        s = dpi[0]
        for j in range(1, nc + 1):
            dpi[j] = s = dpi[j] + s
    for j in range(1, nc + 1):
        s = dp[0][j]
        for i in range(1, nc + 1):
            dp[i][j] = s = dp[i][j] + s
    for l, r in q:
        print(dp[r][r] - dp[l - 1][r] - dp[r][l - 1] + dp[l - 1][l - 1])


nc, nt, nq = map(int, input().split())
f(nc, nt, nq)

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

a=[[0]*(n+1) for i in range(n+1)]
for i in range(m):
    a[lr[i][0]][lr[i][1]]+=1
for i in range(1,n+1):
    for j in range(1,n+1):
        a[i][j]+=a[i-1][j]
for i in range(1,n+1):
    for j in range(1,n+1):
        a[i][j]+=a[i][j-1]
for i in range(q):
    print(a[pq[i][1]][pq[i][1]]-a[pq[i][0]-1][pq[i][1]])

Submission status: Accepted

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

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

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

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

Submission status: Accepted

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


def solve(N: int, M: int, Q: int, L: "List[int]", R: "List[int]", p: "List[int]", q: "List[int]"):

    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    Q = int(next(tokens))  # type: int

    C = [[0] * (N) for _ in range(N)] # C[l][r]: L = l, R = rを満たす列車の本数
    for i in range(M):
        L = int(next(tokens)) - 1
        R = int(next(tokens)) - 1
        C[L][R] += 1

    T1 = [[0] * (N) for _ in range(N)] # T1[l][r]: L = l, R <= rを満たす列車の本数
    for l in range(N):
        for r in range(N):
            if l > r:
                continue
            if l == r:
                T1[l][r] = C[l][r]
            else:
                T1[l][r] = T1[l][r-1] + C[l][r]

    T2 = [[0] * (N) for _ in range(N)] # T2[l][r]: L >= l, R <= rを満たす列車の本数
    for r in range(N):
        for l in range(N-1, -1, -1):
            if l > r:
                continue
            if l == r:
                T2[l][r] = T1[l][r]
            else:
                T2[l][r] = T2[l+1][r] + T1[l][r]

    for i in range(Q):
        p = int(next(tokens))-1
        q = int(next(tokens))-1
        print(T2[p][q])

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
N, M, Q = [int(_) for _ in input().split()]
Query = []
for _ in range(M):
    Query += [[int(_) for _ in input().split()] + [0, _]]
for _ in range(Q):
    p, q = [int(_) for _ in input().split()]
    Query += [[p, q + 1, 1, _]]
Query.sort(key=lambda xs: 2 * xs[1] - xs[2])
ans = [0] * Q


class SegmentTree():
    """
        Parameters
        ----------
        array : list
            to construct segment tree from
        m : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
    """

    def __init__(self, array, m, e, size):
        self.m = m
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = dat = [e] * n + array + [e] * (2 * size - 2 * n)
        self.build()

    def build(self):
        dat, n, m = self.dat, self.n, self.m
        for i in range(n - 1, 0, -1):
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):
        """
        set value at position p (0-indexed)
        """
        m, n, dat = self.m, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = m(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):
        """
        result on interval [l, r) (0-indexed)
        """
        m, e, n, dat = self.m, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = m(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = m(res, dat[r])
            l >>= 1
            r >>= 1
        return res


e = 0
size = N + 2
ST = SegmentTree([0] * (N + 2), m=lambda x, y: x + y, e=e, size=size)
for l, r, t, i in Query:
    if t:
        ans[i] = ST.query(l, r)
    else:
        ST.modify(l, ST.query(l, l + 1) + 1)
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
N, M, Q = [int(_) for _ in input().split()]
Query = []
for _ in range(M):
    Query += [[int(_) for _ in input().split()] + [0, _]]
for _ in range(Q):
    p, q = [int(_) for _ in input().split()]
    Query += [[p, q + 1, 1, _]]
Query.sort(key=lambda xs: 2 * xs[1] - xs[2])
ans = [0] * Q


class SegmentTree():
    def __init__(self, array, m, e, size):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        m : func
            binary operation of the monoid
        e : 
            identity element of the monoid
        size : int
            limit for array size
        """
        self.m = m
        self.e = e
        self.size = size
        self.n = n = len(array)
        self.dat = dat = [e] * n + array + [e] * (2 * size - 2 * n)
        self.build()

    def build(self):
        dat, n, m = self.dat, self.n, self.m
        for i in range(n - 1, 0, -1):
            dat[i] = m(dat[i << 1], dat[i << 1 | 1])

    def modify(self, p, v):
        """
        set value at position p (0-indexed)
        """
        m, n, dat = self.m, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            dat[p >> 1] = m(dat[p], dat[p ^ 1])
            p >>= 1

    def query(self, l, r):
        """
        result on interval [l, r) (0-indexed)
        """
        m, e, n, dat = self.m, self.e, self.n, self.dat
        res = e
        l += n
        r += n
        while l < r:
            if l & 1:
                res = m(res, dat[l])
                l += 1
            if r & 1:
                r -= 1
                res = m(res, dat[r])
            l >>= 1
            r >>= 1
        return res


e = 0
size = N + 2
ST = SegmentTree([0] * (N + 2), m=lambda x, y: x + y, e=e, size=size)
for l, r, t, i in Query:
    if t:
        ans[i] = ST.query(l, r)
    else:
        ST.modify(l, ST.query(l, l + 1) + 1)
print(*ans, sep='\n')

Submission status: Accepted

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

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

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

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

for output in outputs:
    print(output)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

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

li = [[0 for i in range(510)] for j in range(510)]

for i in range(M):
    L,R = map(int, input().split(' '))
    li[L][R] = li[L][R]+1
    
for i in range(N+1):
    for j in range(1, N+1):
        li[i][j] = li[i][j] + li[i][j-1]
        
for i in range(1,N+1):
    for j in range(N+1):
        li[i][j] = li[i][j] + li[i-1][j]
    
for i in range(Q):
    p,q = map(int,input().split(' '))
    print(li[q][q]-li[p-1][q]-li[q][p-1]+li[p-1][p-1])

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 + 2)]
for l, r in LR:
    cumsum[l][r + 1] += 1
for i in range(1, N + 2):
    for j in range(1, N + 2):
        cumsum[i][j] += cumsum[i][j - 1]
for j in range(1, N + 2):
    for i in range(1, N + 2):
        cumsum[i][j] += cumsum[i - 1][j]
for p, q in PQ:
    print(cumsum[q][q + 1] - cumsum[p - 1][q + 1])

Submission status: Accepted

Solution code:
N,M,Q=map(int, input().split())
ma1=[[0]*501 for i in range(501)]
ma=[[0]*501 for i in range(501)]
inpath=[[int(j) for j in input().split()] for i in range(M)]
inQ=[[int(j) for j in input().split()] for i in range(Q)]

for i, j in inpath:
    ma1[i][j] += 1

for i in range(1, 501):
    for j in range(1, 501):
        ma[i][j] = ma[i][j-1] + ma1[i][j]
 

for fr, to in inQ:
    cnt = 0
    # print("from: {} to: {}".format(fr, to))
    for j in range(fr, to+1):
        cnt += (ma[j][to] - ma[j][j-1])
    print(cnt)

Submission status: Accepted

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

ans=[[0 for _ in range(N+2)] for _ in range(N+2)]

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

for h in range(N+2):
	for w in range(1, N+2):
		ans[h][w] += ans[h][w-1]

for w in range(N+2):
	for h in range(1, N+2):
		ans[h][w] += ans[h-1][w]

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

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

acc = [[0 for i in range(N+1)] for i in range(N+1)]  # acc[i][j] = i以下からスタートしてj以下で終了する電車の数
coordinate = [[0 for i in range(N)] for i in range(N)]
for l, r in LR:
    l -= 1
    r -= 1
    coordinate[l][r] += 1

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

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

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from itertools import product

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
cum_sum2 = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i, j in product(range(1, N+1), repeat=2):
    cum_sum2[i][j] += table[i][j] + cum_sum2[i-1][j] + cum_sum2[i][j-1] - cum_sum2[i-1][j-1]
for _ in range(Q):
    p, q = map(int, input().split())
    ans = cum_sum2[q][q] - cum_sum2[p-1][q] - cum_sum2[q][p-1] + cum_sum2[p-1][p-1]
    print(ans)

Submission status: Accepted

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

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

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


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

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

Submission status: Accepted

Solution code:
from itertools import accumulate


def solve(string):
    n, m, q, *lrpq = map(int, string.split())
    lr, pq = lrpq[:2 * m], lrpq[2 * m:]
    t = [[0] * (n + 1) for _ in range(n + 1)]
    for l, r in zip(lr[::2], lr[1::2]):
        t[l][r] += 1
    t = [list(accumulate(t_)) for t_ in zip(*(accumulate(_t) for _t in t))]
    ans = [
        str(t[q][q] - t[p - 1][q] - t[q][p - 1] + t[p - 1][p - 1])
        for p, q in zip(pq[::2], pq[1::2])
    ]
    return "\n".join(ans)


if __name__ == '__main__':
    n, m, q = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, q) + '\n'.join([input() for _ in range(m + q)])))

Submission status: Accepted

Solution code:
def solve(string):
    n, m, q, *lrpq = map(int, string.split())
    lr, pq = lrpq[:2 * m], lrpq[2 * m:]
    t = [[0] * (n + 1) for _ in range(n + 1)]
    for l, r in zip(lr[::2], lr[1::2]):
        t[l][r] += 1
    for i in range(n + 1):
        for j in range(n + 1):
            if j > 0:
                t[i][j] += t[i][j - 1]
    for i in range(n + 1):
        for j in range(n + 1):
            if i > 0:
                t[i][j] += t[i - 1][j]

    ans = [
        str(t[q][q] - t[p - 1][q] - t[q][p - 1] + t[p - 1][p - 1])
        for p, q in zip(pq[::2], pq[1::2])
    ]
    return "\n".join(ans)


if __name__ == '__main__':
    n, m, q = map(int, input().split())
    print(solve('{} {} {}\n'.format(n, m, q) + '\n'.join([input() for _ in range(m + q)])))

Submission status: Accepted

Solution code:
from itertools import accumulate

N,M,Q=map(int,input().split())
table=[[0]*(N+1) for _ in range(N+1)]
for i in range(M):
    l,r=map(int,input().split())
    table[l][r]+=1
dp=[[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    dp[i+1]=list(accumulate(table[i+1]))
for i in range(Q):
    p,q=map(int,input().split())
    sum=0
    for k in range(p,q+1):
      sum+=dp[k][q]-dp[k][p-1]
    print(sum)

Submission status: Accepted

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

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


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


for i in range(q):
  a, b = map(int, input().split())
  print(List2[a - 1][b - 1])

Submission status: Accepted

Solution code:
n, m, Q = map(int, input().split())
List=[[0]*n for i in range(n)]
for i in range(m):
    l, r = map(int, input().split())
    List[n-l][r-1]+=1
for i in range(n):
    tmp=0
    for j in range(n):
        tmp+=List[i][j]
        List[i][j]=tmp
for i in range(n):
    tmp=0
    for j in range(n):
        tmp+=List[j][i]
        List[j][i]=tmp
pq=[list(map(int, input().split())) for i in range(Q)]
for pqi in pq:
    print(List[n-pqi[0]][pqi[1]-1])

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

data = []

for i in range(M):
    l,r = map(int, input().split())
    data.append((0,l-1,r-1,0))
for i in range(Q):
    l,r = map(int, input().split())
    data.append((1,l-1,r-1,i))

data.sort()
data.sort(key=lambda x:x[2])

n0 = 2**(N-1).bit_length()
segdata = [0]*(2*n0-1)

def add(k):
    k += n0-1
    segdata[k] += 1
    while k > 0:
        k = (k-1)//2
        segdata[k] += 1

def getsum(a,b,k=0,l=0,r=n0):
    if r <= a or b <= l:
        return 0
    if a <= l and r <= b:
        return segdata[k]
    vl = getsum(a,b,2*k+1,l,(l+r)//2)
    vr = getsum(a,b,2*k+2,(l+r)//2, r)
    return vr + vl

ans = []

for q, a, b,i in data:
    if q:
        ans.append((i, getsum(a,b+1)))
    else:
        add(a)

ans.sort()
for i, j in ans:
    print(j)

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
# D - AtCoder Express 2
# https://atcoder.jp/contests/abc106/tasks/abc106_d

import sys

s2nn = lambda s: [int(c) for c in s.split(' ')]
ss2nn = lambda ss: [int(s) for s in list(ss)]
ss2nnn = lambda ss: [s2nn(s) for s in list(ss)]
i2s = lambda: sys.stdin.readline().rstrip()
i2n = lambda: int(i2s())
i2nn = lambda: s2nn(i2s())
ii2ss = lambda n: [sys.stdin.readline() for _ in range(n)]
ii2nnn = lambda n: ss2nnn(ii2ss(n))

# N 個の都市
# M 本の列車
# Q 個の興味
def main_lte(N, M, Q, LRm, PQq):
    for p, q in PQq:
        ans = 0
        for l, r in LRm:
            if p <= l and r <= q:
                ans += 1
        print(ans)

def main_lte2(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            for j in range(i, q+1):
                ans += table[i][j]
        print(ans)

def main_lte3(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    # 累積輪
    table2 = [[0] * (N+1) for _ in range(N+1)]
    for i in range(1, N+1):
        for j in range(1, N+1):
            table2[i][j] = table2[i][j-1] + table[i][j]
    for p, q in PQq:
        ans = 0
        for i in range(p, q+1):
            ans += table2[i][q] - table2[i][p-1]
        print(ans)

def main(N, M, Q, LRm, PQq):
    table = [[0] * (N+1) for _ in range(N+1)]
    for l, r in LRm:
        table[l][r] += 1
    # 二次元累積輪
    for i in range(1, N+1):
        for j in range(1, N+1):
            table[i][j] += table[i][j-1]
    for i in range(1, N+1):
        for j in range(1, N+1):
            table[i][j] += table[i-1][j]
    for p, q in PQq:
        ans = table[q][q] + table[p-1][p-1] - table[p-1][q] - table[q][p-1]
        print(ans)

N, M, Q = i2nn()
LRm = ii2nnn(M)
PQq = ii2nnn(Q)
main(N, M, Q, LRm, PQq)

Submission status: Accepted

Solution code:
import numpy as np

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

# trains[L][r]: L から r まで行く電車の本数 (1 <= L <= r <= N)
trains = [[0 for _ in range(N + 1)] for _ in range(N + 1)]
for m in range(M):
    L, r = map(int, input().split())
    trains[L][r] += 1

cumsum = np.cumsum(trains, axis=0).cumsum(axis=1)


def solve(L, r):
    # 二次元累積和
    # 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
    return cumsum[r][r] - cumsum[r][L - 1] - cumsum[L - 1][r] + cumsum[L - 1][L - 1]


for q in range(Q):
    print(solve(*map(int, input().split())))