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:
def JOI14_B():
    N = I()
    A = [I()for _ in range(N)]
    A.extend(A)
    dp = [[0]*(N*2+1) for _ in range(N*2+1)]

    for j in range(N):
        for i in range(N*2-j):
            if (N-j)%2==1:
                dp[i][i+j] = max(dp[i+1][i+j]+A[i],dp[i][i+j-1]+A[i+j])
            else:
                if A[i]>A[i+j]:
                    dp[i][i+j] = dp[i+1][i+j]
                else:
                    dp[i][i+j] = dp[i][i+j-1]
    ans = 0
    for i in range(N):
        ans = max(ans,dp[i][i+N-1])
    print(ans)
    #print(dp)
    return

def square869120Contest1_G():
    def held_karp(dists,TL):
        # Copyright (c) 2016 Carl Ekerot
        """
        Implementation of Held-Karp, an algorithm that solves the Traveling
        Salesman Problem using dynamic programming with memoization.
        Parameters:
            dists: distance matrix
        Returns:
            A tuple, (cost, path).
        """
        n = len(dists)

        # Maps each subset of the nodes to the cost to reach that subset, as well
        # as what node it passed before reaching this subset.
        # Node subsets are represented as set bits.
        C = {}
        dp = defaultdict(int)

        # Set transition cost from initial state
        for k in range(1, n):
            C[(1 << k, k)] = (dists[0][k], 0)
            dp[(1 << k, k)] = 1

        # Iterate subsets of increasing length and store intermediate results
        # in classic dynamic programming manner
        for subset_size in range(2, n):
            for subset in itertools.combinations(range(1, n), subset_size):
                # Set bits for all nodes in this subset
                bits = 0
                for bit in subset:
                    bits |= 1 << bit
                shortest_length = inf
                # Find the lowest cost to get to this subset
                for k in subset:
                    prev = bits & ~(1 << k)

                    res = []
                    for m in subset:
                        if not (prev, m) in C:
                            continue
                        if m == 0 or m == k:
                            continue
                        if C[(prev, m)][0] + dists[m][k]>TL[m][k]:
                            continue
                        res.append((C[(prev, m)][0] + dists[m][k], m))
                        if shortest_length>C[(prev, m)][0] + dists[m][k]:
                            shortest_length = C[(prev, m)][0] + dists[m][k]
                    if not res:
                        continue
                    C[(bits, k)] = min(res)
                    for d,m in res:
                        if shortest_length!=d:
                            continue
                        dp[(bits, k)] += dp[(prev,m)]

        # We're interested in all bits but the least significant (the start state)
        bits = (2 ** n - 1) - 1

        # Calculate optimal cost
        res = []
        shortest_length = inf
        for k in range(1, n):
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            res.append((C[(bits, k)][0] + dists[k][0], k))
            if shortest_length > C[(bits, k)][0] + dists[k][0]:
                shortest_length = C[(bits, k)][0] + dists[k][0]
        if not res:
            return False
        opt, parent = min(res)
        way = 0
        for d, k in res:
            if not (bits, k) in C:
                continue
            if C[(bits, k)][0] + dists[k][0] > TL[k][0]:
                continue
            if shortest_length < d:
                continue
            way += dp[(bits,k)]

        # Backtrack to find full path
        path = []
        for i in range(n - 1):
            path.append(parent)
            new_bits = bits & ~(1 << parent)
            _, parent = C[(bits, parent)]
            bits = new_bits

        # Add implicit start state
        path.append(0)

        return shortest_length, list(reversed(path)), way

    N, M = LI()
    dist = [[inf]*N for _ in range(N)]
    TL = [[0]*N for _ in range(N)]
    for _ in range(M):
        s, t, d, time = LI()
        s -= 1; t -= 1
        dist[s][t] = dist[t][s] = d
        TL[s][t] = TL[t][s] = time
    ans = held_karp(dist,TL)
    if (not ans) or ans[2]==0:
        print("IMPOSSIBLE")
        return
    print(ans[0],ans[2])
    return

def JOI13_D():
    def solve(yday,leader,next):
        a = [0]*3
        for i in range(3):
            if next&(1<<i)==(1<<i):
                a[i] = 1
        rep = 0
        if a[leader]==0:
            return rep
        for i in range(3):
            if yday&(1<<i)==(1<<i):
                if a[i]==1:
                    rep = 1
        return rep
    N = I()
    S = SI()
    member = {"J":0,"O":1,"I":2}
    dp = [[0]*8 for _ in range(N+1)]
    dp[0][1] = 1
    for i in range(N):
        leader = member[S[i]]
        for j in range(8):
            for k in range(8):
                dp[i+1][j] += (dp[i][k]*solve(k,leader,j))
    ans = sum(dp[-1])%10007
    #print(dp)
    print(ans)
    return

def JOI16_D():
    N, M = LI()
    A = [(I()-1)for _ in range(N)]
    imos = [[0] * (N + 1) for _ in range(M)]
    for i in range(M):
        for j in range(N):
            imos[i][j + 1] += imos[i][j] + (A[j] != i)
    loop = 2**M
    dp = [inf]*loop
    dp[0] = 0
    cnt = Counter(A)
    L = [0]*loop
    #print(imos)
    for i in range(loop):
        for j in range(M):
            if i&(1<<j)==(1<<j):
                continue
            next = i|(1<<j)
            if L[next]==0:
                L[next] = L[i]+cnt[j]
            cur = imos[j][L[next]] - imos[j][L[i]]
            if dp[next]>dp[i] + cur:
                dp[next] = dp[i] + cur
    ans = dp[-1]
    #print(L)
    print(ans)
    return

def ABC6_D():
    N = I()
    C = [I() for _ in range(N)]
    LIS = [C[0]]
    for i in range(N):
        if C[i] > LIS[-1]:
            LIS.append(C[i])
        else:
            LIS[bisect.bisect_left(LIS, C[i])] = C[i]
    print(N - len(LIS))
    return

def ABC134_E():
    N = I()
    A = [I()for _ in range(N)]
    que = deque()
    que.append(A[0])
    L = 1
    for i in range(1,N):
        cur = bisect.bisect_left(que,A[i])
        #print(que,cur,L)
        if cur==0:
            que.appendleft(A[i])
            L += 1
        else:
            que[cur-1] = A[i]

    #print(que)
    ans = len(que)
    print(ans)

    return

def JOI7_F():
    def dijkstra_2(edge_adj, node, start):
        # node<=2000くらい
        # edge_adj[node][to] = [cost]
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    V = [[inf]*N for _ in range(N)]
    ans = []
    for _ in range(K):
        A = LI()
        s = A[1]-1
        t = A[2]-1
        if A[0]==1:
            if V[s][t] <= A[3]:
                continue
            V[s][t] = A[3]
            V[t][s] = A[3]
        else:
            dist = dijkstra_2(V,N,s)
            ans.append(dist[t])
    for v in ans:
        if v==inf:
            print(-1)
            continue
        print(v)
    return

def JOI15_E():
    def bfs(n, E, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [inf] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        que = deque()
        for e in E:
            e -=1
            W[e] = 0
            que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] > nowW + 1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    class Dijkstra(object):
        """
        construct: O(ElogV)
        """

        def __init__(self, edges, start=0):
            """
            :param list of list of list of int edges:
            :param int start=0:
            """
            self.__dist = [inf] * len(edges)
            self.__dist[start] = 0
            self.__calculate(edges, start)

        @property
        def dist(self):
            return self.__dist

        def __calculate(self, edges, start):
            Q = [(0, start)]  # (dist,vertex)
            while (Q):
                dist, v = heapq.heappop(Q)
                if self.dist[v] < dist: continue  # 候補として挙がったd,vだが、他に短いのがある
                for u, cost in edges[v]:
                    if self.dist[u] > self.dist[v] + cost:
                        self.__dist[u] = self.dist[v] + cost
                        heapq.heappush(Q, (self.dist[u], u))
    N, M, K, S = LI()
    P, Q = LI()
    C = [I()for _ in range(K)]
    V = [[]for _ in range(N)]
    for _ in range(M):
        s, t = LI()
        s -= 1
        t -= 1
        V[s].append(t)
        V[t].append(s)
    L = bfs(N,C,V)
    #print(L)
    cost = [[]for _ in range(N)]
    for i in range(N):
        for v in V[i]:
            if L[v]==0:
                continue
            elif L[v]<=S:
                cost[i].append((v,Q))
            else:
                cost[i].append((v,P))
    di = Dijkstra(cost)
    ans = di.dist
    #print(cost)
    if L[-1]<=S:
        print(ans[N-1]-Q)
    else:
        print(ans[N-1]-P)
    return

def JOI13_E():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [inf] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == inf:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W

    def dijkstra_2(edge_adj, node, start):
        # node<=2000くらい
        # edge_adj[node][to] = [cost]
        dist = [inf] * node
        used = [False] * node
        dist[start] = 0
        while True:
            v = -1
            for i in range(node):
                if not used[i] and (v == -1 or dist[v] > dist[i]):
                    v = i
            if v == -1:
                break
            used[v] = True
            for i in range(node):
                if dist[i] > dist[v] + edge_adj[v][i]:
                    dist[i] = dist[v] + edge_adj[v][i]
        return dist
    N, K = LI()
    C = [[]for _ in range(N)]
    V = [[]for _ in range(N)]
    for i in range(N):
        C[i] = LI()
    for i in range(K):
        a, b = LI()
        a -= 1
        b -= 1
        V[a].append(b)
        V[b].append(a)
    costV = [[inf]*N for _ in range(N)]
    for i in range(N):
        L = bfs(N,i,V)
        c = C[i][0]; l = C[i][1]
        for j in range(N):
            if i==j:
                continue
            if L[j]<=l:
                costV[i][j] = c
    dist = dijkstra_2(costV,N,0)
    ans = dist[N-1]
    #print(costV)
    print(ans)
    return

def ABC12_D():
    def warshall_floyd(n, d):
        # d[i][j]: iからjへの最短距離
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    N, M = LI()
    V = [[inf]*N for _ in range(N)]
    for i in range(N):
        V[i][i] = 0
    for _ in range(M):
        a, b, t = LI()
        a -= 1
        b -= 1
        V[a][b] = t
        V[b][a] = t
    L = warshall_floyd(N,V)
    #print(L)
    ans = inf
    for i in range(N):
        cur = max(L[i])
        ans = min(ans,cur)
    print(ans)
    return

def ABC79_D():
    def warshall_floyd(n, d):
        # d[i][j]: iからjへの最短距離
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    H, W = LI()
    C = [LI()for _ in range(10)]
    A = [LI()for _ in range(H)]
    L = warshall_floyd(10,C)
    #print(L)
    ans = 0
    for a in A:
        for i in a:
            if i>=0:
                ans += L[i][1]
    print(ans)
    return

def JOIgassyuku10_3():
    N, M, K = LI()
    V = [[]for _ in range(N)]
    for _ in range(M):
        a, b, c = LI()
        a -= 1
        b -= 1
        V[a].append((b,c))
        V[b].append((a,c))


    return

def ABC74_D():
    def warshall_floyd(n, d):
        # d[i][j]: iからjへの最短距離
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j])
        return d
    N = I()
    A = [LI() for _ in range(N)]
    dist = warshall_floyd(N,copy.deepcopy(A))
    shortest_path = 0
    for i in range(N):
        for j in range(N):
            if i==j:
                continue
            if dist[i][j]<A[i][j]:
                print(-1)
                return
            if dist[i][j]>A[i][j]:
                continue
            flag = True
            for k in range(N):
                if i==k or j==k:
                    continue
                judge = (dist[i][k]+dist[k][j])-dist[i][j]
                if judge==0:
                    flag = False
            if flag:
                shortest_path += A[i][j]
    ans = shortest_path//2
    print(ans)
    return

def ABC65_D():
    class Kruskal_UnionFind():
        # 無向グラフであるという前提に注意
        def __init__(self, N):
            self.edges = []
            self.rank = [0] * N
            self.par = [i for i in range(N)]
            self.counter = [1] * N

        def add(self, u, v, d):
            """
            u = from, v = to, d = cost
            """
            self.edges.append([u, v, d])

        def find(self, x):
            if self.par[x] == x:
                return x
            else:
                self.par[x] = self.find(self.par[x])
                return self.par[x]

        def unite(self, x, y):
            x = self.find(x)
            y = self.find(y)
            if x != y:
                z = self.counter[x] + self.counter[y]
                self.counter[x], self.counter[y] = z, z
            if self.rank[x] < self.rank[y]:
                self.par[x] = y
            else:
                self.par[y] = x
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1

        def size(self, x):
            x = self.find(x)
            return self.counter[x]

        def same(self, x, y):
            return self.find(x) == self.find(y)

        def Kruskal(self):
            """
            return: 最小全域木のコストの和
            """
            edges = sorted(self.edges, key=lambda x: x[2])  # costでself.edgesをソートする
            res = 0
            for e in edges:
                if not self.same(e[0], e[1]):
                    self.unite(e[0], e[1])
                    res += e[2]
            return res
    N = I()
    X = []
    for i in range(N):
        a, b = LI()
        X.append((a,b))
    P = defaultdict(set)
    for i,x in enumerate(X):
        P[x] = i
    graph = Kruskal_UnionFind(N + 1)

    X.sort(key=lambda x:x[0])
    for i in range(N-1):
        if X[i+1][0]-X[i][0]>abs(X[i+1][1]-X[i][1]):
            continue
        r = X[i+1][0]-X[i][0]
        graph.add(P[X[i]], P[X[i+1]], r)

    X.sort(key=lambda x:x[1])
    for i in range(N-1):
        if X[i+1][1]-X[i][1]>abs(X[i+1][0]-X[i][0]):
            continue
        r = X[i+1][1]-X[i][1]
        graph.add(P[X[i]], P[X[i+1]], r)

    ans = graph.Kruskal()
    print(ans)
    return

def ABC84_D():
    def is_prime(n):
        if n == 1: return False
        for k in range(2, int(math.sqrt(n)) + 1):
            if n % k == 0:
                return False
        return True

    def like_2017(x):
        if is_prime(x) and is_prime(x//2+1):
            return True
        return False

    Q = I()
    maxX = 10**5
    imos = [0]*(maxX+1)
    for i in range(maxX+1):
        if like_2017(i) and i!=2:
            imos[i] = imos[i-1] + 1
        else:
            imos[i] = imos[i - 1]
    L = [LI()for _ in range(Q)]
    ans = []
    for l,r in L:
        cur = imos[r]-imos[l-1]
        ans.append(cur)
    for v in ans:
        print(v)
    return

def square869120Contest1_E():
    N, Q = LI()
    A = LI()
    C = LI()
    C.append(1)
    L = [0]*N
    for i in range(1,N):
        L[i] = pow(A[i-1],A[i],mod) + L[i-1]
    #print(L)
    ans = 0
    now = 0
    for i in range(Q+1):
        next = C[i]-1
        cur = abs(L[next]-L[now])
        ans += cur
        ans %= mod
        now = next
        #print(ans)
    print(ans)
    return

def ABC34_C():
    # rが小さい時
    def cmb(n, r, mod):
        cur = 1
        for i in range(r):
            cur *= (n-i)
            cur %= mod
        for i in range(r):
            cur *= pow(i+1,mod-2,mod)
            cur %= mod
        return cur

    W, H = LI()
    r = W+H-2; l = H-1
    ans = cmb(r,l,mod)
    print(ans)
    return

def ABC145_D():
    def cmb(n, r, mod):
        cur = 1
        for i in range(r):
            cur *= (n-i)
            cur %= mod
        for i in range(r):
            cur *= pow(i+1,mod-2,mod)
            cur %= mod
        return cur

    X, Y = LI()
    if (X+Y)%3!=0:
        print(0)
        return
    r = (X+Y)//3; l = X-(X+Y)//3
    if l<0:
        print(0)
        return
    ans = cmb(r,l,mod)
    print(ans)
    return

def ABC21_D():
    def cmb(n, r, mod):
        cur = 1
        for i in range(r):
            cur *= (n-i)
            cur %= mod
        for i in range(r):
            cur *= pow(i+1,mod-2,mod)
            cur %= mod
        return cur

    N = I()
    K = I()
    r = N+K-1; l = K
    ans = cmb(r,l,mod)
    print(ans)
    return

def ABC149_F():
    # 子の数のカウント
    def dfs(n,s,edges,children):
        cur = 1
        children[s] = 0
        for i in edges[s]:
            if children[i]!=-1:
                continue
            children[i] = True
            now,children = dfs(n,i,edges,children)
            cur += now
        children[s] = cur
        return cur,children
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -= 1; b -= 1
        V[a].append(b)
        V[b].append(a)
    children = [-1]*N
    C = dfs(N,0,V,children)[1]
    #print(C)

    # 頂点数の期待値計算
    inv = pow(2, mod - 2, mod)
    ans = 1
    p = [pow(inv, i, mod) for i in range(N)]
    for i in range(1,N):
        c = C[i]
        d = N-c
        cur = (1-p[c])*(1-p[d])
        ans += cur
        ans %= mod
    ans -= N * inv
    # 全部白なら+１がない
    ans -= pow(inv,N,mod)

    ans += mod
    ans %= mod
    print(ans)
    return

def NIKKEI2019_A():
    N = I()
    A = LI()
    S = [0]*(N+1)
    for i in range(N):
        S[i+1] = A[i]+S[i]
    ans = []
    for k in range(1,N+1):
        cur = 0
        for i in range(N-k+1):
            now = S[i+k]-S[i]
            if cur<now:
                cur = now
        ans.append(cur)
    for v in ans:
        print(v)
    return

def JOI10_A():
    N, M = LI()
    L = [I()for _ in range(N-1)]
    A = [I()for _ in range(M)]
    S = [0]*N
    for i in range(N-1):
        S[i+1] = S[i] + L[i]
    #print(S)
    ans = 0
    now = 0
    for i in range(M):
        #print(now)
        ans += abs(S[A[i]+now] - S[now])
        now += A[i]
    print(ans%100000)
    return

"""
7 5 
2 
1 
1 
3 
2 
1 
2
-1 
3 
2
-3
"""

def JOI11_1():
    N, M = LI()
    K = I()
    F = [SI()for _ in range(N)]
    A = [LI()for _ in range(K)]
    CJ = [[0]*(M+1) for _ in range(N+1)]
    CO = [[0]*(M+1) for _ in range(N+1)]
    CI = [[0]*(M+1) for _ in range(N+1)]
    for i in range(N):
        nowj = 0
        nowo = 0
        nowi = 0
        for j in range(M):
            if F[i][j]=="J":
                nowj += 1
            CJ[i+1][j+1] = CJ[i][j+1] + nowj
            if F[i][j]=="O":
                nowo += 1
            CO[i+1][j+1] = CO[i][j+1] + nowo
            if F[i][j]=="I":
                nowi += 1
            CI[i+1][j+1] = CI[i][j+1] + nowi
    ans = []
    for a,b,c,d in A:
        curj = CJ[c][d]-CJ[c][b-1]-CJ[a-1][d]+CJ[a-1][b-1]
        curo = CO[c][d]-CO[c][b-1]-CO[a-1][d]+CO[a-1][b-1]
        curi = CI[c][d]-CI[c][b-1]-CI[a-1][d]+CI[a-1][b-1]
        ans.append((curj,curo,curi))

    for v in ans:
        print(" ".join(map(str,v)))
    return

"""
4 7 
4 
JIOJOIJ 
IOJOIJO 
JOIJOOI 
OOJJIJO 
3 5 4 7 
2 2 3 6 
2 2 2 2 
1 1 4 7

"""
def ABC106_D():
    N, M, Q = LI()
    A = [[0]*(N) for _ in range(N)]
    S = [[0]*(N+1) for _ in range(N+1)]
    for _ in range(M):
        l, r = LI()
        A[l-1][r-1] += 1
    for i in range(N):
        now = 0
        for j in range(N):
            now += A[i][j]
            S[i+1][j+1] = S[i][j+1]+now
    ans = []
    for _ in range(Q):
        p, q = LI()
        cur = S[q][q] - S[p-1][q] - S[q][p-1] + S[p-1][p-1]
        ans.append(cur)
    for v in ans:
        print(v)
    return


import sys,copy,bisect,itertools,heapq,math,random
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque

def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = 10**(-12)
alphabet = [chr(ord('a') + i) for i in range(26)]

sys.setrecursionlimit(10**6)

if __name__ == '__main__':
    ABC106_D()
"""

"""

Submission status: Accepted

Solution code:
import numpy as np
N, M, Q, *X = map(int, open(0).read().split())
sheet = [[0]*N for i in range(N)]
for l, r in zip(*[iter(X[:2*M])]*2):
  sheet[N-l][r-1] += 1

sheet = np.cumsum(np.cumsum(sheet,axis=1),axis=0)
for p,q in zip(*[iter(X[2*M:])]*2):
  print(sheet[N-p][q-1])

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

N, M, Q = map(int, input().split())
count = [[0] * (N+1) for _ in range(N+1)]
for _ in range(M):
    L, R = map(lambda x: int(x)-1, input().split())
    count[0][R] += 1
    count[L+1][R] -= 1
for i in range(N+1):
    count[i] = list(accumulate(count[i]))
for i in range(1, N+1):
    for j in range(N+1):
        count[i][j] += count[i-1][j]
for _ in range(Q):
    p, q = map(lambda x: int(x)-1, input().split())
    print(count[p][q])

Submission status: Accepted

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

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

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

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())
ans = [[0] * (n+2) for _ in range(n+2)]
lr = [list(map(int, input().split())) for _ in range(m)]
for l, r in lr:
    ans[0][r] += 1
    ans[0][-1] -= 1
    ans[l+1][-1] -= 1
    ans[l+1][r] -= 1

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

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

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

Submission status: Accepted

Solution code:
import sys
import itertools
input = sys.stdin.readline
sys.setrecursionlimit(100000)


def read_values():
    return map(int, input().split())


def read_index():
    return map(lambda x: x - 1, map(int, input().split()))


def read_list():
    return list(read_values())


def read_lists(N):
    return [read_list() for n in range(N)]


def functional(N, mod):
    F = [1] * (N + 1)
    for i in range(N):
        F[i + 1] = (i + 1) * F[i] % mod
    return F


def main():
    N, M, Q = read_values()
    S = [[0 for _ in range(N + 1)] for __ in range(N + 1)]
    
    for _ in range(M):
        l, r = read_values()
        S[l][r] += 1

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

    res = [0] * Q
    for i in range(Q):
        p, q = read_values()
        res[i] = str(S[q][q] - S[p - 1][q] - S[q][p - 1] + S[p - 1][p - 1])
    print("\n".join(res))


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Acc2D:
    def __init__(self, src):
        self.acc2d = self._build(src)

    def _build(self, src):
        h, w = len(src), len(src[0])
        ret = [[0] * w for _ in range(h)]
        for r in range(h):
            for c in range(w):
                ret[r][c] = src[r][c]
                if r > 0:
                    ret[r][c] += ret[r - 1][c]
                if c > 0:
                    ret[r][c] += ret[r][c - 1]
                if r > 0 and c > 0:
                    ret[r][c] -= ret[r - 1][c - 1]
        return ret

    def get(self, r1, c1, r2, c2):
        """[(r1,c1),(r2,c2)]"""
        acc2d = self.acc2d
        ret = acc2d[r2][c2]
        if r1 > 0:
            ret -= acc2d[r1 - 1][c2]
        if c1 > 0:
            ret -= acc2d[r2][c1 - 1]
        if r1 > 0 and c1 > 0:
            ret += acc2d[r1 - 1][c1 - 1]

        return ret


def main():
    import sys

    input = sys.stdin.readline

    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

    acc2d = Acc2D(table)

    for _ in range(Q):
        p, q = map(int, input().split())
        res = acc2d.get(p, p, q, q)
        print(res)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
import itertools

MOD = 10 ** 9 + 7
INF = 10 ** 18 + 7
input = lambda: sys.stdin.readline().strip()
N, M, Q = map(int, input().split())
sum_list = [[0 for _ in range(N)] for _ in range(N)]
for i in range(M):
    L, R = map(int, input().split())
    sum_list[L - 1][R - 1] += 1
for i in range(N):
    sum_list[i] = list(itertools.accumulate(sum_list[i]))
    sum_list[i].append(0)
for i in range(Q):
    p, q = map(int, input().split())
    ans = 0
    for l in range(p - 1, q):
        ans += sum_list[l][q - 1] - sum_list[l][l - 1]
    print(ans)

Submission status: Accepted

Solution code:
N,M,Q=map(int, input().split())
 
#C[i][j]= i==LかつR<=jなる列車の総数(1-indexed)
C=[[0 for _ in range(N+1)] for __ in range(N+1)]
 
for _ in range(M):
    l,r=map(int, input().split())
    C[l][r]+=1
#print(C)
for i in range(N+1):
    for j in range(1,N+1):
        C[i][j]+=C[i][j-1]
 
for _ in range(Q):
    p,q=map(int, input().split())
    ans=0
    for i in range(p,q+1):
        ans+=C[i][q]-C[i][i-1]
    print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

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

S = [[0] * (N + 1) for _ in range(N + 1)]
for l in range(N+1):
    for r in range(1, N+1):
        S[l][r] = LR[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())
    ans = S[q][q] - S[p-1][q] - S[q][p-1] + S[p-1][p-1]
    print(ans)

Submission status: Accepted

Solution code:



if __name__ == '__main__':
    N,M,Q=list(map(int,input().split()))
    C=[[0 for _ in range(N+1)] for _ in range(N+1)]
    for i in range(1,M+1):
        l,r=list(map(int,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 q in range(Q):
        l, r = list(map(int, input().split()))
        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())
points = [[0] * n for _ in range(n)]
for _ in range(m):
    li, ri = map(int, input().split())
    li -= 1
    ri -= 1
    points[li][ri] += 1

cumsum = [[0] * (n + 1) for _ in range(n + 1)]
for i in range(n):
    for j in range(n):
        cumsum[i + 1][j + 1] = cumsum[i][j + 1] + cumsum[i + 1][j] \
                             - cumsum[i][j] + points[i][j]

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