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:
# D
N, M, Q = map(int, input().split())
dat_mat = [[0]*N for _ in range(N)]

for _ in range(M):
    L, R = map(int, input().split())
    dat_mat[L-1][R-1] += 1
    
dat_mat_left = [[0]*N for _ in range(N)]
dat_mat_res = [[0]*N for _ in range(N)]
for L in range(N):
    c = 0
    for R in range(L, N):
        c += dat_mat[L][R]
        dat_mat_left[L][R] = c
        
for R in range(N-1, -1, -1):
    c = 0
    for L in range(R, -1, -1):
        c += dat_mat_left[L][R]
        dat_mat_res[L][R] = c
        
res_list = [0]*Q
for q in range(Q):
    L, R = map(int, input().split())
    res_list[q] = dat_mat_res[L-1][R-1]

for a in res_list:
    print(a)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
def inpl(): return map(int, input().split())
N, M, Q = inpl()

imos2d = [[0]*(N+2) for _ in range(N+2)]
S = [[0]*(N+2) for _ in range(N+2)]
S2 = [[0]*(N+2) for _ in range(N+2)]

for _ in range(M):
    L, R = inpl()
    imos2d[0][R] += 1
    imos2d[L+1][R] -= 1


for i in range(N+2):
    S[i][0] = imos2d[i][0]
    for j in range(N+1):
        S[i][j+1] = S[i][j] + imos2d[i][j+1]

S2[0] = [s for s in S[0]]
for i in range(N+1):
    for j in range(N+2):
        S2[i+1][j] = S2[i][j] + S[i+1][j]

for _ in range(Q):
    p, q = inpl()
    print(S2[p][q])

Submission status: Accepted

Solution code:
# coding:utf-8
n,m,qq=map(int,input().split())
dp = [[0 for i in range(n+5)] for j in range(n+5)]
for i in range(m):
    l,r=map(int,input().split())
    l-=1
    r-=1
    dp[l][r]+=1
for i in range(n):
    for j in range(n-1):
        dp[i][j+1]+=dp[i][j]
for j in range(n):
    for i in range(n-1,0,-1):
        dp[i-1][j]+=dp[i][j]
for i in range(qq):
    p,q=map(int,input().split())
    p-=1
    q-=1
    if q==n-1:
        print(dp[p][q])
    else :
     print(dp[p][q]-dp[q+1][q])

Submission status: Accepted

Solution code:
from itertools import accumulate

n, m, q = map(int, input().split())
rails = [[0] * n for _ in range(n)]
for _ in range(m):
    l, r = map(int, input().split())
    rails[l - 1][r - 1] += 1
rails = [list(accumulate(s)) for s in rails]
rails = [list(reversed(list(accumulate(reversed(s))))) for s in zip(*rails)]
buf = []
for _ in range(q):
    p, q = map(int, input().split())
    buf.append(rails[q - 1][p - 1])
print('\n'.join(map(str, buf)))

Submission status: Accepted

Solution code:
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict
from bisect import bisect

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N, M, Q = reads()

mat = [[0] * N for _ in range(N)]
for _ in range(M):
  l, r = reads()
  l, r = l-1, r-1
  mat[l][r] += 1

acc = [[0] * (N+1) for _ in range(N+1)]
for i in range(N):
  vec = [0] + list(accumulate(mat[i]))
  acc[i+1] = [acc[i][j] + vec[j] for j in range(N+1)]

for _ in range(Q):
  p, q = reads()
  p, q = p-1, q-1
  ans = acc[N][q+1] - acc[p][q+1]
  print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

N, M, Q = map(int, input().split())
D = [[0]*N for i in range(N)]
E = [[-1]*N for i in range(N)]

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

def dfs(l, r):
    if not l <= r:
        return 0
    if l == r:
        return D[l][r]
    if E[l][r] != -1:
        return E[l][r]
    E[l][r] = res = D[l][r] + dfs(l+1, r) + dfs(l, r-1) - dfs(l+1, r-1)
    return res

ans = []
for i in range(Q):
    p, q = map(int, input().split())
    ans.append(dfs(p-1, q-1))
print(*ans, sep='\n')

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)

N, M, Q = map(int, input().split())
D = [[0]*N for i in range(N)]
E = [[-1]*N for i in range(N)]

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

def dfs(l, r):
    if not l <= r:
        return 0
    if l == r:
        return D[l][r]
    if E[l][r] != -1:
        return E[l][r]
    E[l][r] = res = D[l][r] + dfs(l+1, r) + dfs(l, r-1) - dfs(l+1, r-1)
    return res

ans = []
for i in range(Q):
    p, q = map(int, input().split())
    ans.append(dfs(p-1, q-1))
print(*ans, sep='\n')

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

li = [0]*(N+1)
ans = [0]*Q
for t,flag,s in kukan:
	if flag == -1: #加算
		li[s] += 1
	else:#クエリ
		ans[flag] = sum(li[s:t+1])

for a in ans:
	print(a)

Submission status: Accepted

Solution code:
n,m,q=map(int,raw_input().split())
lrs=[map(int,raw_input().split()) for _ in range(m)]
a=[[0 for j in range(n)] for i in range(n)]
for l,r in lrs:a[l-1][r-1]+=1
cnt=[[0 for j in range(n)] for i in range(n)]
for y in range(n):
 v = 0
 for x in range(y,-1,-1):
  v+=a[x][y]
  cnt[x][y]=cnt[x][y-1]+v
for _ in range(q):
 l,r=map(int,raw_input().split())
 print cnt[l-1][r-1]

Submission status: Accepted

Solution code:
s=input().split()
n,m,q=int(s[0]),int(s[1]),int(s[2])
arr=[[0 for i in range(n+3)] for j in range(n+3)]
for i in range(m):
    s=input().split()
    l,r=int(s[0]),int(s[1])
    for j in range(l+1):
        arr[j][r]+=1
for i in range(q):
    s=input().split()
    p,q=int(s[0]),int(s[1])
    print(sum(arr[p][1:q+1]))

Submission status: Runtime Error

Solution code:
from sys import stdin
from sys import stdout

def getval():
    n,m,q = map(int,stdin.readline().split())
    rw = [[] for i in range(n)]
    for i in [0]*m:
        l,r = map(int,stdin.readline().split())
        rw[r-1].append(l-1)
    for i in range(n):
        rw[i].sort()
    qu = [list(map(int,stdin.readline().split())) for i in range(q)]
    return n,m,q,rw,qu

def main(n,m,q,rw,qu):
    def mybs(arr,key):
        if not arr:
            return 0
        lo = 0
        hi = len(arr)-1
        idx = (lo+hi)//2
        locmax = arr[hi]
        if locmax:
            if key<locmax/2:
                idx = min(idx,int(hi*1.5*(key/locmax)))
            else:
                idx = max(idx,int(hi*0.7*(key/locmax)))
        while lo<=hi:
            if arr[idx]<key:
                lo = idx + 1
            else:
                hi = idx - 1
            idx = (lo+hi)//2
        return lo

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    #print(rw)
    for i in qu:
        ans = 0
        key = i[0]-1
        for j in range(key,i[1]):
            ans += len(rw[j]) - mybs(rw[j],key)
            #print(mybs(rw[j],key),i)
        ans = "".join([str(ans),'\n'])
        stdout.write(ans)
    

if __name__=="__main__":
    n,m,q,rw,qu = getval()
    main(n,m,q,rw,qu)

Submission status: Runtime Error

Solution code:
from sys import stdin
from sys import stdout

def getval():
    n,m,q = map(int,stdin.readline().split())
    rw = [[] for i in range(n)]
    for i in [0]*m:
        l,r = map(int,stdin.readline().split())
        rw[r-1].append(l-1)
    for i in range(n):
        rw[i].sort()
    qu = [list(map(int,stdin.readline().split())) for i in range(q)]
    return n,m,q,rw,qu

def main(n,m,q,rw,qu):
    def mybs(arr,key):
        if not arr:
            return 0
        lo = 0
        hi = len(arr)-1
        idx = (lo+hi)//2
        if key<arr[hi]/2:
            idx = min(idx,int(hi*1.5*(key/arr[hi])))
        else:
            idx = max(idx,int(hi*0.7*(key/arr[hi])))
        while lo<=hi:
            if arr[idx]<key:
                lo = idx + 1
            else:
                hi = idx - 1
            idx = (lo+hi)//2
        return lo

    #For each queries, iterate from rw[p-1] to rw[q-1] and bs for p-1
    #print(rw)
    for i in qu:
        ans = 0
        key = i[0]-1
        for j in range(key,i[1]):
            ans += len(rw[j]) - mybs(rw[j],key)
            #print(mybs(rw[j],key),i)
        ans = "".join([str(ans),'\n'])
        stdout.write(ans)
    

if __name__=="__main__":
    n,m,q,rw,qu = getval()
    main(n,m,q,rw,qu)

Submission status: Runtime Error

Solution code:
from copy import deepcopy

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

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

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

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

Submission status: Runtime Error

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

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

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

for i in range(Q):
    a, b = cin()
    p[i][0] = a - 1;
    p[i][1] = b - 1;
    
def d2_add(a):
    w = len(a[0])
    h = len(a)
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

def d2_calc(da, p, q, x, y):
    if p > x or q > y:  return 0
    if p == 0 and q == 0:  return da[x][y]
    if p == 0:  return da[x][y] - da[x][q - 1]
    if q == 0:  return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

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

Submission status: Runtime Error

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

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

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

for i in range(Q):
    a, b = cin()
    p[i][0] = a - 1;
    p[i][1] = b - 1;
    
def d2_add(a):
    w = len(a[0])
    h = len(a)
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

def d2_calc(da, p, q, x, y):
    if p > x or q > y:  return 0
    if p == 0 and q == 0:  return da[x][y]
    if p == 0:  return da[x][y] - da[x][q - 1]
    if q == 0:  return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

ret = d2_add(a)
for i in range(Q):
    ans = d2_calc(ret, p[i], p[i], q[i], q[i])
    print(ans)

Submission status: Runtime Error

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

def d2_add(a):
    w = len(a[0])
    h = len(a)
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

def d2_calc(da, p, q, x, y):
    if p > x or q > y:  return 0
    if p == 0 and q == 0:  return da[x][y]
    if p == 0:  return da[x][y] - da[x][q - 1]
    if q == 0:  return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

N, M, Q = cin()
v = [[0 for _ in range(N)] for _ in range(N)]
p = [[0 for _ in range(2)] for _ in range(N)]

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

for i in range(Q):
    a, b = cin()
    p[i][0] = a - 1;
    p[i][1] = b - 1;

res = d2_add(v);

for i in range(Q):
    ans = d2_calc(res, p[i][0], p[i][0], p[i][1], p[i][1]);
    print(ans)

Submission status: Runtime Error

Solution code:
def d2_add(a):
    w = len(a[0])
    h = len(a)
    da = [[0] * w for j in range(h)]
    da[0][0] = a[0][0]
    for i in range(1, w):
        da[0][i] = da[0][i - 1] + a[0][i]
    for i in range(1, h):
        cnt_w = 0
        for j in range(w):
            cnt_w += a[i][j]
            da[i][j] = da[i - 1][j] + cnt_w
    return da

def d2_calc(da, p, q, x, y):
    if p > x or q > y:  return 0
    if p == 0 and q == 0:  return da[x][y]
    if p == 0:  return da[x][y] - da[x][q - 1]
    if q == 0:  return da[x][y] - da[p - 1][y]
    return da[x][y] - da[p - 1][y] - da[x][q - 1] + da[p - 1][q - 1]

N, M, Q = cin()
v = [[0 for _ in range(N)] for _ in range(N)]
p = [[0 for _ in range(2)] for _ in range(N)]

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

for i in range(Q):
    a, b = cin()
    p[i][0] = a - 1;
    p[i][1] = b - 1;

res = d2_add(v);

for i in range(Q):
    ans = d2_calc(res, p[i][0], p[i][0], p[i][1], p[i][1]);
    print(ans)

Submission status: Runtime Error

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

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

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

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

if __name__ == '__main__':
    abc106_d()

Submission status: Runtime Error

Solution code:
#    L,Rでタプル、bisect２回で始点の候補を選ぶ、3回目のbisectで終点のindex
# 初期入力
from bisect import bisect_right
from bisect import bisect_left
import sys
input = sys.stdin.readline  #文字列では使わない
N,M,Q = map(int, input().split())
LR =[0]*(M)
L =[0]*M
R =[0]*M
#LR_dic ={i:[] for i in range(1,N+1)}

for i in range(M):
    l,r = map(int, input().split())
    LR[i] =(l,r)
    L[i] =l
LR.sort()
L.sort()

ans =[]
for i in range(Q):
    cot =0
    p,q = map(int, input().split())
    #始点で範囲を絞る
    ind_p =bisect_left(L,p)
    ind_q =bisect_right(L,q)
    x_pq =LR[ind_p:ind_q+1]
    #Rでソートし⇒Rのみ集める⇒終点で絞る
    x_pq.sort(key=lambda x: x[1])
    x_p,x_q =zip(*x_pq)
    ans.append(bisect_right(x_q,q))
print(*ans,sep="\n")

Submission status: Runtime Error

Solution code:
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7

u=input().rstrip()
n=int(u)
u=list(u)
s=int(u[-1])
sm=0
for i in u:
    sm+=int(i)

import math
def judprime(x):
    y=math.sqrt(x)
    count=0
    for j in range(2,int(y)+1):
        if x%j==0:
            count+=1
    if count==0:
        return 1
    else:
        return 0
#print(judprime(7))
#print(judprime(42))
pri =[1,3,7,9]
if judprime(n)==1:
    print("Prime")
else:
    if s in pri and sm%3!=0:
        print("Prime")
        
    else:
        print("Not Prime")

Submission status: Runtime Error

Solution code:
class segment_():
    def __init__(self,A,n,ide_ele,segfunc):
        self.ide_ele = ide_ele
        self.num = 1 << n.bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        self.segfunc = segfunc

    def update1(self, k):
        k += self.num
        self.seg[k] += 1
        while k:
            k >>= 1
            self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

    def query(self, p, q):
        if q < p:
            return self.ide_ele
        p += self.num;
        q += self.num
        res = self.ide_ele
        while p < q:
            if p & 1 == 1:
                res = self.segfunc(res, self.seg[p])
                p += 1
            if q & 1 == 1:
                q -= 1
                res = self.segfunc(res, self.seg[q])
            p >>= 1;
            q >>= 1
        return res
      
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from operator import itemgetter

N,M,Q = map(int,readline().split())
S = segment_(N,0,lambda a, b: max(a,b))
chk = []
for i in range(M):
  L,R = map(int,readline().split())
  chk.append((1,L,R,i))
for i in range(Q):
  l,r = map(int,readline().split())
  chk.append((2,l,r,i))
  
chk.sort(key=itemgetter(2))
ans = [0]*Q
for a,l,r,i in chk:
  if a == 1:
    S.update1(l)
  else:
    ans[i] = S.query(l,r+1)
    
for i in ans:
  print(i)

Submission status: Runtime Error

Solution code:
def solve():
    from itertools import accumulate
    N, M, Q, *x = map(int, open(0).read().split())
    LR, pq = x[:2*M], x[2*M:]

    mat = [[0] * (N + 1) for _ in range(N + 1)]
    c = [[0] * (N + 1) for _ in range(N + 1)]
    # ここでマトリックス作ってる
    for l, r in zip(*[iter(LR)] * 2):
        mat[l][r] += 1

    for l in range(N+1):
        c[l] = list(accumulate(mat[l][:r+1]))

    # S計算
    for p, q in zip(*[iter(pq)] * 2):
        ans = 0
        for l in range(p, q+1):
            ans += c[l][q] - c[l][p-1]
        print(ans)
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
from itertools import accumulate


def solve():
    N, M, Q, *x = map(int, open(0).read().split())
    LR, pq = x[:2*M], x[2*M:]

    mat = [[0] * (N + 1) for _ in range(N + 1)]
    c = [[0] * (N + 1) for _ in range(N + 1)]
    # ここでマトリックス作ってる
    for l, r in zip(*[iter(LR)] * 2):
        mat[l][r] += 1

    for l in range(N+1):
        c[l] = list(accumulate(mat[l][:r+1]))

    # S計算
    for p, q in zip(*[iter(pq)] * 2):
        ans = 0
        for l in range(p,q+1):
            ans += c[l][q] - c[l][p-1]
        print(ans)
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

Solution code:
def solve():
    N, M, Q, *x = map(int, open(0).read().split())
    LR, pq = x[:2*M], x[2*M:]

    mat = [[0] * (N + 1) for _ in range(N + 1)]
    c = [[0] * (N + 1) for _ in range(N + 1)]
    # ここでマトリックス作ってる
    for l, r in zip(*[iter(LR)] * 2):
        mat[l][r] += 1

    for l in range(N+1):
        c[l] = list(accumulate(mat[l][:r+1]))

    # S計算
    for p, q in zip(*[iter(pq)] * 2):
        ans = 0
        for l in range(p,q+1):
            ans += c[l][q] - c[l][p-1]
        print(ans)
if __name__ == '__main__':
    solve()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# N**2の解法
N, M, Q = lr()
graph = np.array([[0] * (501) for _ in range(501)], dtype=np.int32)  # 1-indexed
for i in range(M):
    l, r = lr()
    graph[l][r] += 1

for i in range(M):
    graph[i] = graph[i].cumsum()

graph = np.cumsum(graph, axis=0)
for _ in range(Q):
    p, q = lr()
    answer = graph[q][q] - graph[q][p-1] - graph[p-1][q] + graph[p-1][p-1]
    print(answer)

# 30

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# N**2の解法
N, M, Q = lr()
graph = np.array([[0] * (501) for _ in range(501)])  # 1-indexed
for i in range(M):
    l, r = lr()
    graph[l][r] += 1

for i in range(M):
    graph[i] = graph[i].cumsum()

graph = np.cumsum(graph, axis=0)
for _ in range(Q):
    p, q = lr()
    answer = graph[q][q] - graph[q][p-1] - graph[p-1][q] + graph[p-1][p-1]
    print(answer)

# 30

Submission status: Runtime Error

Solution code:
# coding: utf-8
import sys
import numpy as np

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# N**2の解法
N, M, Q = lr()
graph = np.array([[0] * (N+1) for _ in range(N+1)])  # 1-indexed
for i in range(M):
    l, r = lr()
    graph[l][r] += 1

for i in range(M):
    graph[i] = graph[i].cumsum()

graph = np.cumsum(graph, axis=0)
for _ in range(Q):
    p, q = lr()
    answer = graph[q][q] - graph[q][p-1] - graph[p-1][q] + graph[p-1][p-1]
    print(answer)

# 30

Submission status: Runtime Error

Solution code:

dp = []
train = []

def subq(l, r):
    global dp, train
    if l == 0 or r == 0:
        return 0
    else:
        tmp1 = dp[l][r]
        if tmp1 != -1:
            return tmp1
        else:
            tmp2 = train[l][r] + subq(l - 1, r) + subq(l, r - 1) -  subq(l - 1, r - 1)
            dp[l][r] = tmp2
            return tmp2

def main():
    global dp, train
    n, m, q = map(int, input().split())
    dp = [[-1] * (n+1) for _ in range(n+1)]
    train = [[0] * (n+1) for _ in range(n+1)]
    for _ in range(m):
        l, r = input().split()
        l = int(l)
        r = int(r)
        train[int(l)][int(r)] += 1


    for _ in range(q):
        p, q = input().split()
        p = int(p)
        q = int(q)
        r = subq(q, q) - subq(p-1, q) - subq(q, p-1) + subq(p-1, p-1)
        print(r)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

# for i in range(N):
#     for j in range(N):
#         X[i+1][j+1] += X[i][j+1] + X[i+1][j]
# print(*X, sep='\n')
# print('')

for i in range(N+1):
    for j in range(N):
        X[i][j+1] += X[i][j]
# print(*X, sep='\n')

for i in range(N+1):
    for j in range(N):
        # print(i, j)
        X[j+1][i] += X[j][i]
ans = []
for _ in range(Q):
    p, q = map(int, input().split())
    ans.appned(X[q][q] - X[q][p-1] - X[p-1][q] + X[p-1][p-1])
    # print(ans)
# print(*X, sep='\n')
print(*ans, sep='\n')

Submission status: Runtime Error

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

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

class TwoDimSum():
    def __init__(self, h, w):
        self.counts = [[0 for _ in range(w+1)] for _ in range(h+1)]
        self.s = [[0 for _ in range(w+1)] for _ in range(h+1)]

    def add_count(self, x, y):
        # 0-indexed
        self.counts[y+1][x+1] += 1

    def build(self):
        for i in range(h):
            for j in range(w):
                self.s[i+1][j+1] = self.s[i][j+1] + self.s[i+1][j] - self.s[i][j] + self.counts[i][j]

    def solve(self, x1, y1, x2, y2):
        return self.s[x2][y2] - self.s[x1][y2] - s[x2][y1] + s[x1][y1]

counts = TwoDimSum()
for _ in range(m):
    l, r = map(int, input().split())
    counts.add_count(l-1, r-1)
counts.build()

for i in range(q):
    x, y = map(int, input().split())
    ans.append(str(counts.solve(x, x, y, y)))
print("\n".join(ans))

Submission status: Runtime Error

Solution code:
N, M, Q = map(int,input().split())
Mlist = []
for i in range(M):
    array = list(map(int, input().strip().split()))
    Mlist.append(array)
Qlist = []
for i in range(Q):
    array = list(map(int, input().strip().split()))
    Qlist.append(array)
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
        if j - 1> 0:
            q = q - r[j-1][j-2]
    print(q)

Submission status: Runtime Error

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(N)] for j in range(N)]
q = 0
r = [[0 for i in range(N)] for j in range(N)]
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(10):
    for j in range(10):
        r[i][j] = r[i][j-1] + p[i][j]
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        q = q + r[j-1][Qlist[i][1]-1]
        if j - 1> 0:
            q = q - r[j-1][j-2]
    print(q)

Submission status: Runtime Error

Solution code:
N, M, Q = map(int,input().split())
Mlist = [input().split() for l in range(M)]
Qlist = [input().split() for l in range(Q)]
Mlist.sort()
for i in range(len(Mlist)):
    for j in range(len(Mlist[i])):
        Mlist[i][j] = int(Mlist[i][j])
for i in range(len(Qlist)):
    for j in range(len(Qlist[i])):
        Qlist[i][j] = int(Qlist[i][j])
p = [[0 for i in range(10)] for j in range(10)]
q = 0
def count(k,l):
    s = k
    j = l
    p[s-1][j-1] = p[s-1][j-1] + 1
for i in range(len(Mlist)):
    count(Mlist[i][0],Mlist[i][1])
for i in range(len(Qlist)):
    q = 0
    for j in range(Qlist[i][0],Qlist[i][1]+1):
        for k in range(Qlist[i][0],Qlist[i][1]+1):
            if j <= k:
                if p[j-1][k-1] != 0:
                    q = q+ p[j-1][k-1]
    print(q)

Submission status: Runtime Error

Solution code:
# 桁dp + 二分探索
import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines

def lunlun_num(N):
    N = str(N)
    L = len(N)

    dp = [[0]*10 for j in range(L)]
    for j in range(1,int(N[0])):
        dp[0][j] = 1

    flag = True
    for i in range(L-1):
        d = int(N[i+1])
        b = int(N[i])
        
        dp[i+1][0] += dp[i][0] + dp[i][1]
        dp[i+1][9] += dp[i][8] + dp[i][9]
        for j in range(1,9):
            dp[i+1][j] += dp[i][j-1] + dp[i][j] + dp[i][j+1]
        for j in range(1,10):
            dp[i+1][j] += 1

        if flag:
            if d < b - 1:
                flag = False
            elif d <= b + 1:
                for j in range(max(0, b-1),d):
                    dp[i+1][j] += 1
            else:
                for j in range(max(0, b-1),b+2):
                    dp[i+1][j] += 1
                    flag = False

    return sum(dp[L-1]) + 1 if flag else sum(dp[L-1])


def main():
    K = int(readline())

    # xを決め打って二分探索
    left = 0
    right = 10**10
    while left + 1 < right:
        x = (left + right) // 2

        if lunlun_num(x) >= K:
            right = x
        else:
            left = x
    
    print(right)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]
debugmode = False

NN = 2 * 10 ** 6 + 100
primes = []
isprime = [True for _ in range(NN + 1)]
min_factor = [-1 for _ in range(NN + 1)]
#エラトステネスの篩
for i in range(2, NN + 1):
    if not isprime[i]:
        continue
    primes.append(i)
    for j in range(i * 2, NN + 1, i):
        isprime[j] = False

def prime_factrize(nn):
    res = []
    for p in primes:
        debug(nn, p)
        if nn == 1:
            return res
        if nn % p == 0:
            res.append(p)
            while nn % p == 0:
                nn //= p

n, m, q = MAP()
d = [1 for _ in range(n + 2)]
for i in range(m):
    prime = primes[i]
    l, r = MAP()
    d[l] *= prime
    d[r + 1] /= prime
debug(d)
for i in range(1, n + 2):
    d[i] *= d[i - 1]
    d[i] = int(round(d[i], 0))
debug(d)
for _ in range(q):
    p, q = MAP()
    l = 1
    for i in range(p, q + 1):
        l = lcm(l, d[i])
    debug(l, d[p - 1], d[q + 1])
    pp = set(prime_factrize(l))
    qq = set(prime_factrize(d[p - 1]))
    rr = set(prime_factrize(d[q + 1]))
    debug('pp', list(pp))
    debug('qq', list(qq))
    debug('rr', list(rr))
    ans = pp
    ans = ans - (pp & qq)
    ans = ans - (pp & rr)
    debug('ans', list(ans))
    print(len(ans))