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:
# coding: utf-8
# Your code here!

N, M, Q = map(int, input().split(" "))
L = []
R = []
p = []
q = []

for i in range(M):
    _L, _R = map(int, input().split(" "))
    L.append(_L)
    R.append(_R)
    
for i in range(Q):
    _p, _q = map(int, input().split(" "))
    p.append(_p)
    q.append(_q)
    
def buildSumTable(N, L, R):
    ret = [[0 for i in range(N+1)] for i in range(N+1)]
    for i in range(M):
        ret[L[i]][R[i]] += 1
    for i in range(1, N+1):
        for j in range(1, N+1):
            ret[i][j] += ret[i-1][j]
            ret[i][j] += ret[i][j-1]
            ret[i][j] -= ret[i-1][j-1]
    return ret

def getSumRange(table, p, q):
    return table[q][q] - table[q][p-1] - table[p-1][q] + table[p-1][p-1] 

sumTable = buildSumTable(N, L, R)

for i in range(Q):
    ans = getSumRange(sumTable, p[i], q[i])
    print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,datetime
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inpl(): return list(map(int, input().split()))
def inpl_s(): return list(input().split())

N,M,Q = inpl()
kukan = []

for i in range(M):#加算
	l,r = inpl()
	kukan.append([r,-1,l])


for i in range(Q):#クエリ
	p,q = inpl()
	kukan.append([q,i,p])

kukan.sort()

bit = [0]*(N+1)
ans = [0]*Q

def BIT_add(a,w):
	global bit
	x = a
	while x <= N:
		bit[x] += w
		x += x & -x

def BIT_sum(a):
	global bit
	tmp = 0
	x = a
	while x > 0:
		tmp += bit[x]
		x -= x & -x
	return tmp

for t,flag,s in kukan:
	if flag == -1: #加算
		BIT_add(s,1)
	else:#クエリ
		ans[flag] = BIT_sum(t)-BIT_sum(s-1)

for a in ans:
	print(a)

Submission status: Accepted

Solution code:
from itertools import accumulate
def a():
    return map(int,input().split())
n,m,q=a()
s=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
    x,y=a()
    s[n-x][y-1]+=1
def f(s):
    for i in range(len(s)):
        s[i]=list(accumulate(s[i]))
f(s)
s=list(zip(*s))
f(s)
for i in range(q):
    x,y=a()
    print(s[y-1][n-x])

Submission status: Accepted

Solution code:
from itertools import accumulate
n,m,q=map(int,input().split())
s=[[0 for i in range(n)] for j in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    s[n-x][y-1]+=1
def f(s):
    for i in range(len(s)):
        s[i]=list(accumulate(s[i]))
f(s)
s=list(zip(*s))
f(s)
for i in range(q):
    x,y=map(int,input().split())
    print(s[y-1][n-x])

Submission status: Accepted

Solution code:
def run(n, m, qq, l, r, p, q):
    cnt = {}
    sum = {}
    ret = []
    for i in range(n+1):
        for j in range(n+1):
            cnt[i, j] = 0
            sum[i, j] = 0
    for i in range(m):
        cnt[(l[i], r[i])] += 1
    for i in range(1, n+1):
        for j in range(1, n+1):
            sum[i, j] = cnt[i, j] + sum[i-1, j] + sum[i, j-1] - sum[i-1, j-1]
    for i in range(qq):
        ret.append(sum[q[i], q[i]] - sum[p[i]-1, q[i]] - sum[q[i], p[i]-1] + sum[p[i]-1, p[i]-1])
    return ret


def read_line():
    n, m, qq = map(int, input().split())
    l = []
    r = []
    for i in range(m):
        tl, tr = map(int, input().split())
        l.append(tl)
        r.append(tr)
    p = []
    q = []
    for i in range(qq):
        tp, tq = map(int, input().split())
        p.append(tp)
        q.append(tq)
    return (n, m, qq, l, r, p, q)


def main():
    n, m, qq, l, r, p, q = read_line()
    ret = run(n, m, qq, l, r, p, q)
    for i in range(len(ret)):
        print(ret[i])


if __name__ == '__main__':
    main()

Submission status: Accepted

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

# (N + 1) * (N + 1) の２次元の表を作成
# N + 1 にしておくのは、後ほど q - 1を参照するときにエラーを出さないため
x = [[0 for i in range(N + 1)] for j in range(N + 1)]

# M本ある各電車の情報を表に整理
for _ in range(M):
    l, r = map(int, input().split())
    x[l][r] += 1

# 2次元の累積和計算で表をアップデート
for i in range(1, N + 1):
    for j in range(1, N + 1):
        x[i][j] += x[i - 1][j] + x[i][j - 1] - x[i - 1][j - 1]

# 累積計算
for _ in range(Q):
    p, q = map(int, input().split())
    ans = x[q][q] - x[q][p - 1] - x[p - 1][q] + x[p - 1][p - 1]
    print(ans)

Submission status: Accepted

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

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

for i in range(1, N+1): #R方向への累積和
    for j in range(1, N+2):
        LR[i][j] += LR[i][j-1]
for i in range(N-1, -1, -1): #L方向への累積和
    for j in range(1, N+2):
        LR[i][j] += LR[i+1][j]

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

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

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

class Ruiwa():
    def __init__(self, a):
        self.H = h = len(a)
        self.W = w = len(a[0])
        self.R = r = a
        for i in range(h):
            for j in range(1,w):
                r[i][j] += r[i][j-1]

        for i in range(1,h):
            for j in range(w):
                r[i][j] += r[i-1][j]

    def search(self, x1, y1, x2, y2):
        if x1 > x2 or y1 > y2:
            return 0

        r = self.R
        rr = r[y2][x2]
        if x1 > 0 and y1 > 0:
            return rr - r[y1-1][x2] - r[y2][x1-1] + r[y1-1][x1-1]
        if x1 > 0:
            rr -= r[y2][x1-1]
        if y1 > 0:
            rr -= r[y1-1][x2]

        return rr

def main():
    n,m,q = LI()
    lr = [LI_() for _ in range(m)]
    pq = [LI_() for _ in range(q)]

    a = [[0]*n for _ in range(n)]

    for l,r in lr:
        a[l][r] += 1

    rui = Ruiwa(a)
    rr = []
    for p,q in pq:
        rr.append(rui.search(p,p,q,q))

    return '\n'.join(map(str, rr))




print(main())

Submission status: Accepted

Solution code:
a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])
ll = list()
rr = list()

for _ in range(m):
    a = input().split()
    ll.append(int(a[0]))
    rr.append(int(a[1]))

p = list()
q = list()

for _ in range(qq):
    a = input().split()
    p.append(int(a[0]))
    q.append(int(a[1]))

c = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    c[ll[i] - 1][rr[i] - 1] += 1

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

for i in range(qq):
    r = 0

    if 0 < q[i]:
        r += c[q[i] - 1][q[i] - 1]

    if 0 < q[i] and 1 < p[i]:
        r -= c[q[i] - 1][p[i] - 2] + c[p[i] - 2][q[i] - 1]

    if 1 < p[i]:
        r += c[p[i] - 2][p[i] - 2]

    print(r)

Submission status: Accepted

Solution code:
a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])

x = [[0] * n for _ in range(n)]

for _ in range(m):
    a = input().split()
    x[int(a[0]) - 1][int(a[1]) - 1] += 1

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

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

for _ in range(qq):
    r = 0
    a = input().split()
    p = int(a[0])
    q = int(a[1])

    if 0 < q:
        r += x[q - 1][q - 1]

    if 0 < q and 1 < p:
        r -= x[q - 1][p - 2] + x[p - 2][q - 1]

    if 1 < p:
        r += x[p - 2][p - 2]

    print(r)

Submission status: Accepted

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

n,m,q = map(int, sdin().split())

lr = []
for i in range(m):
    l,r = map(int, sdin().split())
    lr.append(tuple([l, r]))
        
pq = []
for _ in range(q):
    p,q = map(int, sdin().split())
    pq.append(tuple([p, q]))
    
# n×nフィールドを用意して各列車のl,r点をプロット
field = [[0 for _ in range(n+1)] for _ in range(n+1)]
for l, r in lr:
    field[l][r] += 1
    
# fieldのx方向の累積和を取る
field_cum = [list(accumulate(field[i])) for i in range(n+1)]    

# field_cumのy方向の累積和をとる
for r in range(1,n+1):
    for l in range(n+1):
        field_cum[r][l] += field_cum[r-1][l]

        
# 各クエリに対し、長方形内部にあるものの個数を求める
for p,q in pq:
    print(field_cum[q][q] - field_cum[p-1][q] - field_cum[q][p-1] + field_cum[p-1][p-1])

Submission status: Accepted

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

n,m,q = map(int, sdin().split())

lr = []
for i in range(m):
    l,r = map(int, sdin().split())
    lr.append(tuple([l-1, r-1]))
        
pq = []
for _ in range(q):
    p,q = map(int, sdin().split())
    pq.append(tuple([p-1, q-1]))

    
# n×nフィールドを用意して各列車のl,r点をプロット
field = [[0 for _ in range(n)] for _ in range(n)]
for l, r in lr:
    field[l][r] += 1
    
# fieldのx方向の累積和を取る
field_cum = [list(accumulate(field[i])) for i in range(n)]    

# field_cumのy方向の累積和をとる
for r in range(1,n):
    for l in range(n):
        field_cum[r][l] += field_cum[r-1][l]

        
# 各クエリに対し、長方形内部にあるものの個数を求める
for p,q in pq:
    if p > 0:
        print(field_cum[q][q] - field_cum[p-1][q] - field_cum[q][p-1] + field_cum[p-1][p-1])
    else:
        print(field_cum[q][q])

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


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


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


class RectangleSum():
    def __init__(self, N, M):
        self.N = N
        self.M = M
        self.s = [[0] * (M+1) for _ in range(N+1)]

    def add(self, i, j, v):
        self.s[i+1][j+1] += v

    def build(self):
        for i in range(self.N+1):
            for j in range(self.M):
                self.s[i][j+1] += self.s[i][j]

        for i in range(self.N):
            for j in range(self.M+1):
                self.s[i+1][j] += self.s[i][j]

    def sum(self, i, j, h, w):
        ret = self.s[i][j]
        ret += self.s[i+h][j+w]
        ret -= self.s[i+h][j]
        ret -= self.s[i][j+w]

        return ret


@mt
def slv(N, M, Q, LR, PQ):
    rs = RectangleSum(N+1, N+1)
    for l, r in LR:
        rs.add(l, r, 1)

    rs.build()

    for p, q in PQ:
        print(rs.sum(p, p, q-p+1, q-p+1))


def main():
    N, M, Q = read_int_n()
    LR = [read_int_n() for _ in range(M)]
    PQ = [read_int_n() for _ in range(Q)]
    slv(N, M, Q, LR, PQ)


if __name__ == '__main__':
    main()

Submission status: Accepted

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

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

from itertools import accumulate

t = [list(accumulate(row)) for row in x]
s = [list(accumulate(row)) for row in zip(*t)]

for p, q in PQ:
    result = s[q][q] -s[q][p-1] - s[p-1][q] + s[p-1][p-1]
    print(result)

Submission status: Accepted

Solution code:
import itertools

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

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

acc_lr = []
for l in lr:
    acc_lr.append([0] + list(itertools.accumulate(l)))

for _ in range(q):
    l,r = map(int,input().split())
    ans = 0
    for ls in acc_lr[l-1:r]:
        ans += ls[r] - ls[l-1]
    print(ans)

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

Submission status: Accepted

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

x = [[0 for j in range(N + 1)] for i in range(N + 1)]

for _ 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):
        x[i][j] += x[i][j - 1]

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

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

Submission status: Accepted

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

from collections import defaultdict
from itertools import accumulate

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

for l, r in LR:
    C[1][r] += 1
    C[l + 1][r] -= 1

#print(C)

T = [list(accumulate(row)) for row in C]
T = [list(accumulate(row)) for row in zip(*T)]

#print(T)

for p, q in PQ:
    print(T[q][p])

Submission status: Accepted

Solution code:
def d_atcoder_express_2(N, M, Q, Train, Query):
    x = [[0] * (N + 1) for _ in range(N + 1)]
    for l, r in Train:
        x[l][r] += 1
    # 2次元累積和
    for r in range(1, N + 1):
        for c in range(1, N + 1):
            x[r][c] += x[r - 1][c] + x[r][c - 1] - x[r - 1][c - 1]

    tmp = []
    for p, q in Query:
        # 包除原理的
        tmp.append(str(x[q][q] - x[p - 1][q] - x[q][p - 1] + x[p - 1][p - 1]))
    ans = '\n'.join(tmp)
    return ans

N, M, Q = [int(i) for i in input().split()]
Train = [[int(i) for i in input().split()] for j in range(M)]
Query = [[int(i) for i in input().split()] for j in range(Q)]
print(d_atcoder_express_2(N, M, Q, Train, Query))

Submission status: Accepted

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

x = [[0 for j in range(N + 1)] for i in range(N + 1)]

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

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

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

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

Submission status: Accepted

Solution code:
from copy import deepcopy

N, M, Q = [int(elem) for elem in input().split(' ')]
lines = [[int(elem) for elem in input().split(' ')] for _ in range(M)]
queries = [[int(elem) for elem in input().split(' ')] for _ in range(Q)]


def cuml_1d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1

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

    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        num_lines = 0
        for l in range(p, max(q + 1, N)):
            if p == 0:
                num_lines += cuml_coords[l][q]
            else:
                num_lines += cuml_coords[l][q] - cuml_coords[l][p - 1]
        print(num_lines)

#cuml_1d(N, lines, queries)


def cuml_2d(N, lines, queries):
    coords = [[0] * N for _ in range(N)]
    for l, r in lines:
        coords[l - 1][r - 1] += 1
    cuml_l = deepcopy(coords)
    for r in range(N):
        for l in range(1, N):
            cuml_l[l][r] = cuml_l[l - 1][r] + coords[l][r]
    cuml_2d = deepcopy(cuml_l)
    for l in range(N):
        for r in range(1, N):
            cuml_2d[l][r] = cuml_2d[l][r - 1] + cuml_l[l][r]
    
    for query in queries:
        p, q = query[0] - 1, query[1] - 1
        if p != 0:
            num_lines = cuml_2d[q][q] - cuml_2d[q][p-1] - cuml_2d[p-1][q] + cuml_2d[p-1][p-1]
        else:
            num_lines = cuml_2d[q][q]
        print(num_lines)

cuml_2d(N, lines, queries)

Submission status: Accepted

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

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

for y in range(1,n+1):
  for x in range(1,n+1):
    d[y][x]+=(d[y][x-1]+d[y-1][x]-d[y-1][x-1])

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

Submission status: Accepted

Solution code:
n,m,q = map(int, input().split())
l = [list(map(int, input().split())) for _ in range(m)]
p = [list(map(int, input().split()))+ [i] for i in range(q)]
l.extend(p)
l = sorted(l,key= lambda x:x[1])
ka = [0] * n
ans = []
for i in l:
  if len(i) == 2:
    ka[i[0]-1] += 1
  else:
    ans.append([i[2],sum(ka[i[0]-1:i[1]])])
ans = sorted(ans)
for i in range(len(ans)):
  print(ans[i][1])

Submission status: Accepted

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

l=[]
r=[]
for j in range(m):
    l_tmp, r_tmp = list(map(int, input().split()))
    l.append(l_tmp)
    r.append(r_tmp)

p=[]
q=[]
for k in range(Q):
    p_tmp, q_tmp = list(map(int, input().split()))
    p.append(p_tmp)
    q.append(q_tmp)
    
su = [[0 for _ in range(n+1)] for __ in range(n+1)]

def sumTable(L, R):
    for i in range(m):
        su[L[i]][R[i]] += 1
    
    for i in range(1,n+1):
        for j in range(1, n+1):
            su[i][j] += su[i-1][j]
            su[i][j] += su[i][j-1]
            su[i][j] -= su[i-1][j-1]

def getSum(ll,rr):
    ans = su[rr][rr] - su[rr][ll-1] -su[ll-1][rr] + su[ll-1][ll-1]
    return ans
  
sumTable(l,r)

import copy
ss = copy.copy(su)

for qi in range(Q):
    su = copy.copy(ss)
    print(getSum(p[qi], q[qi]))

Submission status: Accepted

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

# 二次元累積和をとる
LR_sum = [[0] * (N+1) for _ in range(N+1)]
LR_sum[1][1] = LR[1][1]
## 初期化
for i in range(1, N+1):
    LR_sum[1][i] = LR_sum[1][i-1] + LR[1][i]
    LR_sum[i][1] = LR_sum[i-1][1] + LR[i][1]
## 累積和をとる
for i in range(2, N+1):
    for j in range(2, N+1):
        LR_sum[i][j] = LR_sum[i-1][j] + LR_sum[i][j-1] - LR_sum[i-1][j-1] + LR[i][j]

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

Submission status: Accepted

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

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):
        x[i][j] += x[i - 1][j] + x[i][j - 1] - x[i - 1][j - 1]

for i in range(Q):
    p, q = map(int, input().split())

    ans = x[N][q] - x[p - 1][q]
    print(ans)

Submission status: Accepted

Solution code:
a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])

x = [[0] * n for _ in range(n)]

for _ in range(m):
    a = input().split()
    x[int(a[0]) - 1][int(a[1]) - 1] += 1

c = list()

for i in range(n):
    c.append(list())
    for j in range(n):
        a = x[i][j]

        if 0 < j:
            a += c[i][j - 1]

        c[i].append(a)

z = list()

for i in range(n):
    z.append(list())
    for j in range(n):
        a = c[i][j]

        if 0 < i:
            a += z[i - 1][j]

        z[i].append(a)

for _ in range(qq):
    r = 0
    a = input().split()
    p = int(a[0])
    q = int(a[1])

    if 0 < q:
        r += z[q - 1][q - 1]

    if 0 < q and 1 < p:
        r -= z[q - 1][p - 2] + z[p - 2][q - 1]

    if 1 < p:
        r += z[p - 2][p - 2]

    print(r)

Submission status: Accepted

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

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):
        x[i][j] += x[i - 1][j] + x[i][j - 1] - x[i - 1][j - 1]

for i in range(Q):
    p, q = map(int, input().split())

    ans = x[N][q] - x[p - 1][q]
    print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(500000)

def memoize(f):
    table = {}

    def func(*args):
        if not args in table:
            table[args] = f(*args)
        return table[args]
    return func


@memoize
def memo(a, b):
    if a == b:
        return e[a].count(a)
    elif b - a == 1:
        return memo(b, b) + memo(a, a) + e[a].count(b)
    else:
        return memo(a+1, b)+memo(a, b-1) + e[a].count(b) - memo(a+1, b-1)


n, m, q = map(int, input().split())
e = []
for i in range(n+1):
    e.append([])
for i in range(m):
    x, y = map(int, input().split())
    e[x].append(y)
for i in range(q):
    x, y = map(int, input().split())
    print(memo(x, y))

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate
N, M, Q = [int(i) for i in input().strip().split(' ')]

flag  = False
counter = M

d = []
d2 = []
for i in range(N):
    d.append([0] * N)
for i in range(N):
    d2.append([0] * N)


for line in sys.stdin:
    L, R = [int(i) for i in line.strip().split(' ')]
    if not flag:
        d[L-1][R-1] += 1
#        for i in range(L):
#            for j in range(N - R + 1):
#                d[i][R + j - 1] += 1
        counter -= 1
        if counter == 0:
#            print(d)
            for i in range(N):
                d[i] = d[i][::-1]
#            print(d)
            for i in range(N):
                if i == 0:
                    d[N-1] = list(accumulate(d[N-1][::-1]))[::-1]
                else:
                    for j in range(N):
                        if j == 0:
                            temp = d[N-1-i][N-1-j]
                        else:
                            temp += d[N-1-i][N-1-j]
                        d[N-1-i][N-1-j] = d[N-i][N-1-j] + temp
#            print(d)
#            for x in d:
#                print(x)
            flag = True
    else:
        print(d[L-1][N-R])

Submission status: Accepted

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


Query=[]
answer=[[0]*N for i in range(N)]
for i in range(M):
  L,R=map(int,input().split())
  answer[N-L][R-1]+=1

for i in range(1,N):
  answer[0][i]+=answer[0][i-1]
  answer[i][0]+=answer[i-1][0]
  
for i in range(1,N):
  for j in range(1,N):
    answer[i][j]+=answer[i-1][j]
    answer[i][j]+=answer[i][j-1]
    answer[i][j]-=answer[i-1][j-1]
for i in range(Q):
  p,q=map(int,input().split())
  print(answer[N-p][q-1])
'''
for i in range(Q):
  answer=0
  Query=list(map(int,input().split()))
  for j in range(M):
    if train[j][0]>=Query[0] and train[j][1]<=Query[1]:
      answer+=1
  print(answer)
'''

Submission status: Accepted

Solution code:
import numpy as np

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

a = np.zeros((N+1, N+1), dtype=np.int)

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

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

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

Submission status: Accepted

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

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

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

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

for i in range(q):
    count = 0
    (l, r) = map(int, input().split(" "))
    print(ns[r][r] - ns[l - 1][r])

Submission status: Accepted

Solution code:
N, M, Q = map(int, raw_input().split())
L = []
R = []
for i in range(M):
	_l, _r = map(int, raw_input().split())
	L.append(_l)
	R.append(_r)

p = []
q = []
for i in range(Q):
	_p, _q = map(int, raw_input().split())
	p.append(_p)
	q.append(_q)


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

for i in range(M):
	start_end_mat[L[i]][R[i]] += 1

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

for i in range(Q):
	res = start_end_mat[N][q[i]]
	res -= start_end_mat[p[i] - 1][q[i]]
	print(res)

Submission status: Accepted

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

import bisect
import array


def solve():
    n, m, q = map(int, input().split())
    nl = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for e in [input().split() for _ in range(m)]:
        l, r = int(e[0]), int(e[1])
        nl[l][r] += 1
    table = [array.array("i", [0] * (n + 2)) for j in range(n + 2)]
    ran = array.array("i", range(n + 1))
    for i in ran:
        for j in ran:
            table[i][j + 1] = table[i][j] + nl[i][j]

    for i, e in enumerate([input().split() for _ in range(q)]):
        l, r = int(e[0]), int(e[1])
        ans = 0
        for j in range(l, r + 1):
            ans += table[j][r + 1] - table[j][l]
        print(ans)


if __name__ == "__main__":
    solve()

Submission status: Accepted

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

N_LR = [[0 for i in range(N+1)] for j in range(N+1)]

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

#S_LR = [[0 for i in range(N+1)] for j in range(N+1)]
for i in range(1,N+1):
  for j in range(1,N+1):
    N_LR[i][j] += N_LR[i-1][j] + N_LR[i][j-1] - N_LR[i-1][j-1]

for i in range(Q):
  x,y = map(int, input().split() )
  ans = N_LR[y][y] - N_LR[x-1][y] - N_LR[y][x-1] + N_LR[x-1][x-1]
  print(ans)

Submission status: Accepted

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

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

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

for l,m in ans:
    print(table[m][m]-table[l-1][m]-table[m][l-1]+table[l-1][l-1])

Submission status: Accepted

Solution code:
import numpy as np
n, m, q = [int(item) for item in input().split(" ")]
# n, m, q = [int(item) for item in lines[0].split(" ")]

end = np.zeros((m,2),dtype=int)
query = np.zeros((q,2),dtype=int)
for i in range(m):
    end[i] = [int(item) for item in input().split(" ")]
#     end[i] = [int(item) for item in lines[1+i].split(" ")]

for i in range(q):
    query[i] = [int(item) for item in input().split(" ")]
#     query[i] = [int(item) for item in lines[1+m+i].split(" ")]

a = np.zeros((n,n), dtype=int)
np.add.at(a, [end[:,0]-1,end[:,1]-1], 1)
b = np.cumsum(a[::-1,:], axis=0)[::-1,:]
c = np.cumsum(b, axis=1)
for item in query:
    print(c[item[0]-1, item[1]-1])
    # print(np.sum(a[(item[0]-1):, :item[1]]))

Submission status: Accepted

Solution code:
N, M, Q = map(int,input().split())
m =  [[0 for y in range(N+1)] for x in range(N+1)]
m2 =  [[0 for y in range(N+1)] for x in range(N+1)]
m3 =[[0 for y in range(N+1)] for x in range(N+1)]

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

for j in range(1, N+1):
    s=0
    for i in range(1, N+1):
        s+=m[i][j]
        m2[i][j]=s

for i in range(1, N+1):
    s=0
    for j in range(i, N+1):
        s+=m2[j][j]-m2[i-1][j]
        m3[i][j]=s

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

Submission status: Accepted

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

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


class CumSum2d(object):
    def __init__(self, H, W):
        self.H, self.W = H, W
        self.tiles = [[0] * W for _ in range(H)]

    def add(self, x, y, c=1):
        self.tiles[y][x] += c

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

    def get(self, sx, sy, tx, ty):
        assert sx <= tx and sy <= ty
        cnt = self.tiles[ty][tx]
        if sx > 0:
            cnt -= self.tiles[ty][sx - 1]
        if sy > 0:
            cnt -= self.tiles[sy - 1][tx]
        if sx > 0 and sy > 0:
            cnt += self.tiles[sy - 1][sx - 1]
        return cnt


cs = CumSum2d(N, N)
for i in range(M):
    l, r = map(int, input().split())
    cs.add(l - 1, r - 1)
cs.build()

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