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: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

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


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

Submission status: Runtime Error

Solution code:
2 3 1
1 1
1 2
2 2
1 2

Submission status: Runtime Error

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

for j in range(N):
    for i in range(N-1,0,-1):
        num[i-1][j] += num[i][j]
for i in range(N):
    for j in range(N-1):
        num[i][j+1] += num[i][j]
pq = [list(map(int,input().split())) for i in range(M)]
for p,q in pq:
    print(num[p-1][q-1])

Submission status: Runtime Error

Solution code:
n,m,q = [int(i) for i in input().split()]
lr = [[int(x)-1 for x in input().split()] for i in range(m)]
pq = [[int(x)-1 for x in input().split()] for i in range(q)]
m = [[0]*500 for _ in range(500)]
for l,r in lr:
    m[0][r]+=1
    m[l+1][r]-=1
for i in range(500):
    for j in range(1,500):
        m[j][i]+=m[j-1][i]
for i in range(500):
    for j in range(1,500):
        m[i][j]+=m[i][j-1]
for p,q in pq:
    print(m[p][q])

Submission status: Runtime Error

Solution code:
import numpy as np
n, m, qnum = map(int,input().split())
trains = np.zeros((n,n))
query = []
for _ in range(n):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    trains[l, r] += 1
for _ in range(qnum):
    p, q = map(int, input().split())
    p -= 1
    q -= 1
    tmp = trains[p:q+1, p:q+1]
    print(int(tmp.sum()))

Submission status: Runtime Error

Solution code:
import sys
import numpy as np

I = np.array(sys.stdin.read().split(), dtype=np.int64)
n, m, q = I[:3]
l, r = I[3:3+m*2].reshape(-1, 2).T
p, q = I[3+m*2:].reshape(-1, 2).T

def main():
    res = np.zeros((n+2, n+2), dtype=np.int64)

    np.add.at(res, (np.full(m, 1), r), 1)
    np.add.at(res, (l+1, r), -1)
    np.add.at(res, (np.full(m, 1), np.full(m, n+1)), -1)
    np.add.at(res, (l+1, np.full(m, n+1)), 1)
    res = np.cumsum(res, axis=0)
    res = np.cumsum(res, axis=1)
    
    ans = res[p, q]
    return ans

if __name__ == '__main__':
    ans = main()
    print(*ans, sep='\n')

Submission status: Runtime Error

Solution code:
import numpy as np
n,m,q = map(int,input().split())
list_lr = [list(map(int,input().split())) for i in range(m)]
list_pq = [list(map(int,input().split())) for i in range(q)]

query = np.zeros((500,500),dtype=int)

for k,l in list_lr:
    query[k][l] += 1

def search(l,r):
    ans = 0
    for i in range(l,r+1):
        for j in range(l,r+1):
            ans += query[i][j]
    return ans

for k,m in list_pq:
    print(search(k,m))

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
n,m,q=map(int, input().split())  
a=[list(map(int, input().split())) for i in range(m)]
b=[list(map(int, input().split())) for i in range(q)]

x=[[0]*(501) for i in range(501)]
x=np.array
for i in range(m):
    x[a[i][0],a[i][1]]+=1



for i in range(501):
    x[i] = list(itertools.accumulate(x[i]))
  
for i in range(501):
    x[:,i] = list(itertools.accumulate(x[:,i]))



for i in range(q):
    print(x[b[i][1],b[i][1]]-x[b[i][1],b[i][0]-1]-x[b[i][0-1,b[i][1]]+x[b[i][0-1,b[i][0-1])

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np

n,m,q=map(int, input().split())  
a=[list(map(int, input().split())) for i in range(m)]
b=[list(map(int, input().split())) for i in range(q)]

x=np.zeros(501, 501)

for i in range(m):
    x[a[i][0]][a[i][1]]+=1

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

for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2,v2]
    a2=x[v2,v1-1]
    a3=x[v1-1,v2]
    a4=x[v1-1,v1-1]
    print(a1-a2-a3+a4)

Submission status: Runtime Error

Solution code:
import itertools

n,m,q=map(int, input().split())  
a=[list(map(int, input().split())) for i in range(m)]
b=[list(map(int, input().split())) for i in range(q)]

x=[[0]*(501) for i in range(501)]

for i in range(m):
    x[a[i][0]][a[i][1]]+=1



for i in range(501):
    x[i] = list(itertools.accumulate(x[i]))
  

for i in range(501):
    x[:,i] = list(itertools.accumulate(x[:,i]))



for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2,v2]
    a2=x[v2,v1-1]
    a3=x[v1-1,v2]
    a4=x[v1-1,v1-1]
    print(a1-a2-a3+a4)

Submission status: Runtime Error

Solution code:
import itertools
import numpy as np
n,m,q=map(int, input().split())  
a=[list(map(int, input().split())) for i in range(m)]
b=[list(map(int, input().split())) for i in range(q)]

x=[[0]*(501) for i in range(501)]

for i in range(m):
    x[a[i][0]][a[i][1]]+=1



for i in range(501):
    x[i] = list(itertools.accumulate(x[i]))
  
x=np.array(x)
for i in range(501):
    x[:,i] = list(itertools.accumulate(x[:,i]))



for i in range(q):
    v1=b[i][0]
    v2=b[i][1]
    
    a1=x[v2,v2]
    a2=x[v2-1,v1-1]
    a3=x[v1-1,v2-1]
    a4=x[v1-1,v1-1]
    print(a1-a2-a3+a4)

Submission status: Runtime Error

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

print(x)
x = itertools.accumulate(x)
x=list(x)
print(x)

for i in range(q):
    print(x[b[i][1]]-x[b[i][0]])

Submission status: Runtime Error

Solution code:
# D - AtCoder Express 2

import numpy as np
import sys

N, M, Q = map(int, input().split())
LRpq = np.array(sys.stdin.buffer.read().split(), np.int64)
L = LRpq[:2*M:2]
R = LRpq[1:2*M:2]
p = LRpq[2*M::2]
q = LRpq[2*M+1::2]
    
train = np.zeros((N+1, N+1))
np.add.at(train, (L,R), 1)

np.cumsum(train, axis = 0, out = train)
np.cumsum(train, axis = 1, out = train)
    
ans = train[q,q] - train[p-1,q] - train[q,p-1] + train[p-1,p-1]
for i in range(Q):
    print(int(ans[i]))

Submission status: Runtime Error

Solution code:
# D - AtCoder Express 2

import bisect, copy

N, M, Q = map(int, input().split())
LRidx = [list(map(int, input().split())) + [i] for i in range(M)]
p, q = [], []
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p.append(tmp_p)
    q.append(tmp_q)

# l,rはそれぞれ高々500通りなので、l,rの値に対して探索結果をメモしておく
LRidx = sorted(LRidx, key = lambda x: x[0])
tmp_L = [LRidx[idx][0] for idx in range(M)]
l_memo = [[-1] for _ in range(N+1)]
l_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if l_memo[p[i]][0] == -1:
        b_idx = bisect.bisect_left(tmp_L, p[i])
        try:
            tmp = [LRidx[j][2] for j in range(bisect.bisect_left(tmp_L, p[i]), M)]
            l_ok_idx[i] = copy.deepcopy(tmp)
            l_memo[p[i]] = copy.deepcopy(tmp)
        except:
            pass
    else:
        l_ok_idx[i] = copy.deepcopy(l_memo[p[i]])
    
LRidx = sorted(LRidx, key = lambda x: x[1])
tmp_R = [LRidx[idx][1] for idx in range(M)]
r_memo = [[-1] for _ in range(N+1)]
r_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if r_memo[q[i]][0] == -1:
        b_idx = bisect.bisect_right(tmp_R, q[i])
        tmp = [LRidx[j][2] for j in range(b_idx)]
        r_ok_idx[i] = copy.deepcopy(tmp)
        r_memo[q[i]] = copy.deepcopy(tmp)
    else:
        r_ok_idx[i] = copy.deepcopy(r_memo[q[i]])
    
for i in range(Q):
    print(len(set(l_ok_idx[i]) & set(r_ok_idx[i])))

Submission status: Runtime Error

Solution code:
# D - AtCoder Express 2

import bisect, copy

N, M, Q = map(int, input().split())
LRidx = [list(map(int, input().split())) + [i] for i in range(M)]
p, q = [], []
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p.append(tmp_p)
    q.append(tmp_q)

# l,rはそれぞれ高々500通りなので、l,rの値に対して探索結果をメモしておく
LRidx = sorted(LRidx, key = lambda x: x[0])
tmp_L = [LRidx[idx][0] for idx in range(M)]
l_memo = [[-1] for _ in range(N+1)]
l_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if l_memo[p[i]][0] == -1:
        b_idx = bisect.bisect_left(tmp_L, p[i])
        try:
            tmp = []
            for j in range(bisect.bisect_left(tmp_L, p[i]), M):
                tmp.append(LRidx[j][2])
            l_ok_idx[i] = copy.deepcopy(tmp)
            l_memo[p[i]] = copy.deepcopy(tmp)
        except:
            pass
    else:
        l_ok_idx[i] = copy.deepcopy(l_memo[p[i]])
    
LRidx = sorted(LRidx, key = lambda x: x[1])
tmp_R = [LRidx[idx][1] for idx in range(M)]
r_memo = [[-1] for _ in range(N+1)]
r_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    if r_memo[q[i]][0] == -1:
        b_idx = bisect.bisect_right(tmp_R, q[i])
        tmp = []
        for j in range(b_idx):
            tmp.append(LRidx[j][2])
        r_ok_idx[i] = copy.deepcopy(tmp)
        r_memo[q[i]] = copy.deepcopy(tmp)
    else:
        r_ok_idx[i] = copy.deepcopy(r_memo[q[i]])
    
for i in range(Q):
    print(len(set(l_ok_idx[i]) & set(r_ok_idx[i])))

Submission status: Runtime Error

Solution code:
# D - AtCoder Express 2

import bisect, copy

N, M, Q = map(int, input().split())
LRidx = [list(map(int, input().split())) + [i] for i in range(M)]
p, q = [], []
for _ in range(Q):
    tmp_p, tmp_q = map(int, input().split())
    p.append(tmp_p)
    q.append(tmp_q)

# 探索結果をメモしておく
LRidx = sorted(LRidx, key = lambda x: x[0])
tmp_L = [LRidx[idx][0] for idx in range(M)]
l_memo = [[-1] for _ in range(M+1)]
l_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    b_idx = bisect.bisect_left(tmp_L, p[i])
    if l_memo[b_idx][0] == -1:
        try:
            tmp = []
            for j in range(bisect.bisect_left(tmp_L, p[i]), M):
                tmp.append(LRidx[j][2])
            l_ok_idx[i] = copy.deepcopy(tmp)
            l_memo[b_idx] = copy.deepcopy(tmp)
        except:
            pass
    else:
        l_ok_idx[i] = copy.deepcopy(l_memo[b_idx])
    
LRidx = sorted(LRidx, key = lambda x: x[1])
tmp_R = [LRidx[idx][1] for idx in range(M)]
r_memo = [[-1] for _ in range(M+1)]
r_ok_idx = [[] for _ in range(Q)]
for i in range(Q):
    b_idx = bisect.bisect_right(tmp_R, q[i])
    if r_memo[b_idx][0] == -1:
        tmp = []
        for j in range(b_idx):
            tmp.append(LRidx[j][2])
        r_ok_idx[i] = copy.deepcopy(tmp)
        r_memo[b_idx] = copy.deepcopy(tmp)
    else:
        r_ok_idx[i] = copy.deepcopy(r_memo[b_idx])
    
for i in range(Q):
    print(len(set(l_ok_idx[i]) & set(r_ok_idx[i])))

Submission status: Runtime Error

Solution code:
import numpy as np
import sys
buf = sys.stdin.buffer

N, M, Q = map(int, buf.readline().split())
city = np.zeros((N + 1, N + 1), dtype='int32')
L, R = np.array(buf.read((N + 2) * M).split(), dtype='int32').reshape(M, 2).T
p, q = np.array(buf.read((N + 2) * Q).split(), dtype='int32').reshape(Q, 2).T

np.add.at(city, (L, R), 1)
np.cumsum(city, axis=0, out=city)
np.cumsum(city, axis=1, out=city)

p -= 1
answer = city[q, q] - city[p, q] - city[q, p] + city[p, p]
print('\n'.join(answer.astype(str)))

Submission status: Runtime Error

Solution code:
import numpy as np
n,m,q=map(int,input().split())
book=[[0]*(n+1) for _ in range(n+1)]
for _ in range(m):
    r,l=map(int,input().split())
    book[r][l] +=1

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

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

#print(np.array(book))

for x,y in [map(int,input().split()) for i in range(q)]:
    print(book[y][y]-book[y][x-1]-book[x-1][y]+book[x][x])

Submission status: Runtime Error

Solution code:
import numpy as np
N, M, Q = map(int, input().split())
 
#input
lst = [[0] * (N + 1) for _ in range(N + 1)]
for _ in range(M):
    L, R = map(int, input().split())
    lst[R][L] += 1
 
lst = np.array(lst)
# print (lst)
 
#2次元累積和
for i in range(1, N + 1):
    lst[:,i] += lst[:, i - 1]
for j in range(1, N + 1):
    lst[j,:] += lst[j - 1, :]
 
 
#output
for _ in range(Q):
    p, q = map(int, input().split())
    print (lst[q, q] - lst[p-1, q] - lst[q, p-1] + lst[p-1, p-1])

Submission status: Runtime Error

Solution code:
n, m, x = map(int, input().split())
trainlist = {}
for i in range(m):
    a, b = map(str, input().split())
    k = "".join([a.zfill(2), "-", b.zfill(2)])
    if k in trainlist:
        trainlist[k] = trainlist[k] + 1
    else:
        trainlist[k] = 1
        
for i in range(x):
    s, t = map(int, input().split())
    ans = 0
    for w in trainlist:
        if s <= int(w[0])*10+int(w[1]) and int(w[3])*10+int(w[4]) <= t:
            ans += trainlist[w]
    print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
from collections import defaultdict as dd
N, M, Q = map(int, input().split())

X = np.zeros((N, N))
D = np.zeros((N, N+1))

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

Submission status: Runtime Error

Solution code:
from functools import lru_cache
from operator import itemgetter

n, m, q = map(int, input().split())
lrlr = [list(map(int, input().split())) for _ in range(m)]
pqpq = [list(map(int, input().split())) for _ in range(q)]

lrlr.sort(key=itemgetter(1))
lrlr.sort(key=itemgetter(0))

def mysect_right(a, x, n, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if x < a[mid][n]: hi = mid
        else: lo = mid+1
    return lo

def mysect_left(a, x, n, lo=0, hi=None):
    if hi is None:
        hi = len(a)
    while lo < hi:
        mid = (lo+hi)//2
        if a[mid][n] < x: lo = mid+1
        else: hi = mid
    return lo

@lru_cache(n**2)
def train(l, r) :
    il_right = mysect_right(lrlr, l, 0)
    il_left = mysect_left(lrlr, l, 0)
    ir_right = mysect_right(lrlr, r, 1, lo=il_left, hi=il_right)
    ir_left = mysect_left(lrlr, l, 1, lo=il_left, hi=il_right)
    if l == r : return ir_right - ir_left
    return ir_right - ir_left + train(l+1, r)

for p, q in pqpq :
    print(train(p, q))

Submission status: Runtime Error

Solution code:
import math
import copy
from operator import mul
from functools import reduce
from collections import defaultdict
from collections import Counter
from collections import deque
# 直積 A={a, b, c}, B={d, e}:のとき，A×B={(a,d),(a,e),(b,d),(b,e),(c,d),(c,e)}: product(A, B)
from itertools import product
# 階乗 P!: permutations(seq), 順列 {}_len(seq) P_n: permutations(seq, n)
from itertools import permutations
# 組み合わせ {}_len(seq) C_n: combinations(seq, n)
from itertools import combinations
# 一次元累積和
from itertools import accumulate
from bisect import bisect_left, bisect_right

import re
# import numpy as np
# from scipy.misc import comb

def inside(y, x, H, W):
    return 0 <= y < H and 0 <= x < W

# 四方向: 右, 下, 左, 上
dy = [0, -1, 0, 1]
dx = [1, 0, -1, 0]
 
def i_inpl(): return int(input())
def l_inpl(): return list(map(int, input().split()))
def line_inpl(x): return [i_inpl() for _ in range(x)]

INF = int(1e18)
MOD = int(1e9)+7 # 10^9 + 7

# W行H列, x[W][H]
def create_grid(W, H, value = 0):
    return [[ value for _ in range(H)] for _ in range(W)]

########
N, H = l_inpl()
a, b = [], []

for _ in range(N):
    ai, bi = l_inpl()
    a.append(ai)
    b.append(bi)

a.sort()
b.sort()
max_a = max(a)

ans = 0
for bi in b[bisect_right(b, max_a):]:
    H -= bi
    ans += 1
    if H <= 0:
        break

if H > 0:
    ans += math.ceil(H / max_a)

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np
n, m, q = map(int, input().split())
kukan = np.zeros((N+1, N+1))
for _ in range(m):
    l, r = map(int, input().split())
    kukan[r][l] += 1

# まず終点の側から考える
# iまでに終わる線分の数はi-1までの累積和
for i in range(1, n+1):
    kukan[i] += kukan[i-1]
# 次に始点の側から考える
# i以降に始まる線分の数はi-1までの総和
for i in range(1, n+1):
    kukan[:, i] += kukan[i-1]

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

Submission status: Runtime Error

Solution code:
n, m, q = map(int, input().split())
m_list = [list(map(int, input().split())) for _ in range(m)]
q_list = [list(map(int, input().split())) for _ in range(q)]
s_list = [set() for _ in range(n)]
e_list = [set() for _ in range(n)]
for i, m in enumerate(m_list):
  s_list[m[0]-1].add(i)
  e_list[m[1]-1].add(i)
  
for i in range(1,n):
  s_list[-i] = s_list[-i].union(s_list[-i+1])
  e_list[i] = e_list[i].union(e_list[i-1])

s_list[0] = s_list[0].union(s_list[1])

for q in q_list:
  s_set = s_list[q[0]-1]
  e_set = e_list[q[1]-1]
  print(len(s_set & e_set))

Submission status: Runtime Error

Solution code:
n, m, q = map(int, input().split())
m_list = [list(map(int, input().split())) for _ in range(m)]
q_list = [list(map(int, input().split())) for _ in range(q)]
s_list = [set() for _ in range(len(m_list))]
e_list = [set() for _ in range(len(q_list))]
for i, m in enumerate(m_list):
  s_list[m[0]-1].add(i)
  e_list[m[1]-1].add(i)

for q in q_list:
  s_set = set()
  e_set = set()
  for s in s_list[q[0]-1:]:
    s_set = s_set.union(s)
  for e in e_list[:q[1]]:
    e_set = e_set.union(e)
  print(len(s_set & e_set))

Submission status: Runtime Error

Solution code:
N,M,Q=map(int,input().split())
A=[]
for i in range(M+Q):
    L,R=map(int,input().split())
    A.append([L,R])
#print(A)
B = [[0 for i in range(500)] for j in range(500)]

for i in range(M):
    B[A[i][0]][A[i][1]] +=1
#print(*B,sep='\n')
C = [[0 for i in range(500)] for j in range(500)]
for i in range(500):
    for k in range(500):
        if k==0:
            C[i][k] = B[i][k]
        else:
            C[i][k] += C[i][k-1]+B[i][k]
#print('\n')
#print(*C,sep='\n')
for i in range(M,M+Q):
    total=0
    for k in range(500):
        if A[i][0]<=k<=A[i][1]:
            total+=C[k][A[i][1]]-C[k][A[i][0]-1]
    print(total)

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())

a = list(map(int, input().split()))

y = np.zeros((n, 1), dtype=np.int)

for i, wa in enumerate(a):
    y[i][0] = wa

A = np.zeros(n)

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

A[n-1][n-1] = 1
A[n-1][0] = 1

S = np.linalg.solve(A,y)*2

for i in range(n-1):
    print(int(S[i][0]), end=" ")
print(int(S[n-1][0]))

Submission status: Runtime Error

Solution code:
import numpy as np

n = int(input())

a = list(map(int, input().split()))

y = np.zeros((n, 1), dtype=np.int)

for i, wa in enumerate(a):
    y[i][0] = wa

A = np.zeros(n, dtype=np.int)

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

A[n-1][n-1] = 1
A[n-1][0] = 1

S = np.linalg.solve(A,y)*2

for i in range(n-1):
    print(int(S[i][0]), end=" ")
print(int(S[n-1][0]))

Submission status: Runtime Error

Solution code:
import copy

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

train_map = []
numbers = []

for i in range(n):
    train_map.append([])
    for j in range(n):
        train_map[i].append(0)

s = copy.deepcopy(train_map)

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

for i in range(n):
    tmp = 0
    for j in range(n):
        tmp += train_map[i][j]
        s[i][j] = tmp

for i in range(q):
    st, go = map(int, input().split())
    number = 0
    for j in range(st-1, go):
        #number += s[j][go-1]
    numbers.append(number)

for num in numbers:
    print(num)

Submission status: Runtime Error

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

trains = []
sections = []

for i in range(m):
    trains.append(tuple(map(int, input().split())))

#print(trains)

for i in range(q):
    sections.append(tuple(map(int, input().split())))

#print(sections)

trains = sorted(trains, key=lambda x: x[0])


for section in sections:
    number = 0
    flag = False
    for train in trains:
        if section[0] <= train[0]:
            if train[1] <= section[1]:
                number += 1
                #print('in')
            flag = True
        elif flag:
            #print('out')
            #continue

    print(number)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
 
def main():
	N, M, Q = map(int, input().split(" "))
	N_list = [[0 for _ in range(N)] for _ in range(N)]
	
	for _ in range(M):
		l, r = map(int, input().split(" "))
		l -= 1
		r -= 1
		N_list[l][r] += 1
		
	#print(N_list)
	
	for i in range(N):
		for j in range(N):
			if i == 0 and j == 0:
				continue
			if i == 0:
				N_list[i][j] = N_list[i][j] + N_list[i][j-1]
				continue
			if j == 0:
				N_list[i][j] = N_list[i][j] + N_list[i-1][j]
				continue
			N_list[i][j] = N_list[i][j] + N_list[i-1][j] + N_list[i][j-1] - N_list[i-1][j-1]
			
	#print(N_list)
		
	for _ in range(Q):
		p, q = map(int, input().split(" "))
		p -= 1
		q -= 1
		
		a = 0
		b = 0
		c = 0
		if p != 0:
			a = N_list[q][p-1]
			b = N_list[p-1][q]
			c = N_list[p-1][p-1]
		ans = N_list[q][q] - a - b + c
		print(ans)
		
	
if __name__ == "__main__":
	main()

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!
import numpy as np
 
N, M, Q = map(int, input().rstrip().split(' '))
 
memo = np.zeros((N, N)).astype(int)
 
for _ in range(M):
    p, q = map(int, input().rstrip().split(' '))
    memo[:p, q-1:] += 1
 
for i in range(Q):
    p, q = map(int, input().rstrip().split(' '))
    print(memo[p-1][q-1])

Submission status: Runtime Error

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

n, m, q = map(int, input().split())
qa = []
ma = [[0 for i in range(n + 1)] for _ in range(m + 1)]
for i in range(m):
    x, y = map(int, input().split())
    ma[x][y] += 1
for i in range(1,n + 1):
    for j in range(1, n + 1):
        ma[i][j] = ma[i][j] + ma[i][j - 1]
for i in range(1,n + 1):
    for j in range(1, n + 1):
        ma[j][i] = ma[j][i] + ma[j - 1][i]
for i in range(q):
    x, y = map(int ,input().split())
    print(ma[y][y] + ma[x - 1][x - 1] - ma[x - 1][y] - ma[y][x - 1])

Submission status: Runtime Error

Solution code:
# coding: UTF-8
import sys
#sys.setrecursionlimit(n)
import heapq
import re
import bisect
import random
import math
import itertools
from collections import defaultdict, deque
from copy import deepcopy
from decimal import *

n, m, q = map(int, input().split())
qa = []
ma = [[0 for i in range(n + 1)] for _ in range(m + 1)]
for i in range(m):
    x, y = map(int, input().split())
    ma[x][y] += 1
for i in range(1,m + 1):
    for j in range(1, n + 1):
        ma[i][j] = ma[i][j] + ma[i][j - 1]
for i in range(1,n + 1):
    for j in range(1, m + 1):
        ma[j][i] = ma[j][i] + ma[j - 1][i]
for i in range(q):
    x, y = map(int ,input().split())
    print(ma[y][y] + ma[x - 1][x - 1] - ma[x - 1][y] - ma[y][x - 1])

Submission status: Runtime Error

Solution code:
import sys
import os
f = open("C:/Users/kazuki/Documents/python/import.txt","r")
sys.stdin = f
# -*- coding: utf-8 -*-
import itertools
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from scipy.sparse.csgraph import floyd_warshall as wf
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from collections import Counter
inf = 10**10
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: Runtime Error

Solution code:
N, M, Q = map(int, input().split())
table = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    l, r = map(int, input().split())
    table[l][r] += 1
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: Runtime Error

Solution code:
mport bisect
from collections import defaultdict
N,M,Q = map(int,input().split())
lr = [tuple(map(int,input().split())) for i in range(M)]
pq = [tuple(map(int,input().split())) for i in range(Q)]
lr.sort()
l = [lr[i][0] for i in range(M)]
r = [lr[i][1] for i in range(M)]

l_I = {}
for p in range(1,N+1):
    l_I[p] = bisect.bisect_left(l,p)

r_d = {}
for i in range(1,N+1):
    r_d[i] = sorted(r[l_I[i]:])
ans = defaultdict(lambda:{})
for p in range(1,N+1):
    for q in range(p,N+1):
        ans[p][q] = bisect.bisect(r_d[p],q)
for i in range(Q):
    p,q = pq[i]
    print(ans[p][q])

Submission status: Runtime Error

Solution code:
import numpy as np

def main():
    N, M, Q = [int(n) for n in input().split()]
    imos = [[0] * N for _ in range(N)]
    for i in range(M):
        l, r = [int(i)-1 for i in input().split()]
        imos[l][r]+=1
    # print(imos)
    for h in range(N):
        for w in range(1, N):
            imos[h][w] += imos[h][w-1]
    for h in reversed(list(range(1, N))):
        for w in range(N):
            imos[h-1][w] += imos[h][w]
    # print(imos)
    ans = [0]*Q
    for q in range(Q):
        ql, qr = [int(i)-1 for i in input().split()]
        ans[q] = imos[ql][qr]
    for a in ans:
        print(a)



if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from operator import itemgetter
n,m,q = map(int,input().split())
LR = [[-1]+list(map(int,input().split())) for _ in range(m)]
PQ = [[_]+list(map(int,input().split())) for _ in range(q)]

Ans = [0]*501
section = LR + PQ
section.sort(key = itemgetter(2))

l = [0]*501
for x,y,z in section:
    if x == -1:
        l[y] += 1
    else:
        Ans[x] = sum(l[y:z+1])

for ans in Ans:
    if ans >= 1:
        print(ans)

Submission status: Runtime Error

Solution code:
n,m,q = map(int,input().split())
import numpy as np
LR = np.full((500,500),0)
Ans = []
for _ in range(m):
    x,y = map(int,input().split())
    LR[x][y] += 1

def portionsum(List,x,y):#List must be 2-demension,x>y
    re = 0
    for l in range(x,y+1):
        re += sum(List[l][x:y+1])
    return re

for i in range(q):
    p,q = map(int,input().split())
    Ans.append(portionsum(LR,p,q))
for _ in Ans:
    print(_)

Submission status: Runtime Error

Solution code:
n, m, q = map(int, input().split())
train = [tuple(map(int, input().split())) for _ in range(m)]
dp = [[0 for _ in range(n+1)] for _ in range(n+1)]
d = {}
for l in range(n):
    for r in range(l,n):
        d[(l+1,r+1)] = 0
for p, q in train:
    d[(p,q)] += 1
for l in range(1,n+1):
    dp[l][l] = d[(l,l)]
for w in range(1,n):
    for l in range(n-w):
        dp[l+1][l+w+1] = dp[l+1][l+w] + dp[l+2][l+w+1] - dp[l+2][l+w] + d[(l+1,l+w+1)]
for _ in range(q):
    l, r = map(int, input().split())
    print(dp[l][r])

Submission status: Runtime Error

Solution code:
n, m, q = map(int, input().split())
train = [tuple(map(int, input().split())) for _ in range(m)]
quest = [tuple(map(int, input().split())) for _ in range(q)]
dp = [[0 for _ in range(n)] for _ in range(n)]
d = {}
for l in range(n):
    for r in range(l,n):
        d[(l,r)] = 0
for p, q in train:
        d[(p,q)] += 1
for l in range(n):
    dp[l][l] = d[(l+1,l+1)]
for w in range(1,n):
    for l in range(n-w):
        dp[l][l+w] = dp[l][l+w-1] + d[(l,l+w)]
for l, r in quest:
    print(dp[l-1][r-1])