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())
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:
    else:
        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])

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N, M, Q = map(int, input().split())
trains = []
for _ in range(M):
    a, b = map(int, input().split())
    trains.append([a, b])

query = []
for _ in range(Q):
    a, b = map(int, input().split())
    query.append([a, b])


def solve():
    # i駅目以前に(i駅も含む)出発した電車
    start_acc = [0]*(N+2)
    # i駅目以前に(i駅も含む)終点を迎えた電車
    finished_acc = [0]*(N+2)

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

    # 各駅の出発・到着数をカウント
    for start, dest in train:
        start_acc[start] += 1
        finished_acc[dest] += 1

    # 累積和にする
    for i in range(1, N+2):
        start_acc[i] += start_acc[i-1]
        finished_acc[i] += finished_acc[i-1]

    # qs~qdの数 = qD(を含む)までに終わった数 - qs(を含む)までに終わったやつ - qs(を含まない)より前に出発したやつ
    ans = []
    for qs, qd in query:
        a = finished_acc[qd] - finished_acc[qs-1] - start_acc[qs-1]
        ans.append(a)

    return ans


def solve2():
    start = [set() for _ in range(N+1)]
    end = [set() for _ in range(N+1)]

    for i in range(M):
        tr = trains[i]
        s = tr[0]
        g = tr[1]
        start[s].add(i)
        end[g].add(i)

    for i in range(1, N+1):
        start[i] |= start[i-1]
        end[i] |= end[i-1]

    ans = []
    for ds, dq in query:

        ans.append(len((start[dq] - start[ds-1]) & (end[dq] - end[ds-1])))

    return ans


ans = solve2()
for a in ans:
    print(a)

Submission status: Runtime Error

Solution code:
n,m,q = map(int,input().split())
LR = []
ansl = []
for _ in range(m):
    LR.append(list(map(int,input().split())))
for _ in range(q):
    p,q = map(int,input().split())
    ans = 0
    for i in range(m):
        if p<=LR[i][0] and LR[i][1] <= q:
            ans += 1
    ansl.append(ans)
for i in range(q):
    print(ansl[i])

Submission status: Runtime Error

Solution code:
import bisect
import numpy as np
N,M,Q = map(int,input().split())
lr = [0]*M
for i in range(M):
    l,r = map(int,input().split())
    lr[i] = [l,r]
lr = sorted(lr,key=lambda x:x[0])
lr_t = list(np.array(lr).transpose())
index_dict={}
r_dict={} 
d = {}
for i in range(N):
    index_dict[i+1]=bisect.bisect_left(lr_t[0],i+1)
    r_dict[i+1]=sorted(lr_t[1][index_dict[i+1]:])
for i in range(Q):
    p,q = map(int,input().split())
    if p not in d:
        d[p]={}
        I = index_dict[p]
        r = r_dict[p]
        I = bisect.bisect(r,q)
        print(I)
        d[p][q]=I
    else:
        if q not in d[p]:
            I = index_dict[p]
            r = r_dict[p]
            I = bisect.bisect(r,q)
            print(I)
            d[p][q]=I
        else:
            print(d[p][q])

Submission status: Runtime Error

Solution code:
def m():
    n, M, Q = map(int, input().split())
    a = [[0 for _ in range(n+1)] for _ in range(n+1)]
    for i in range(M):
        l, r = map(int, input().split())
        a[l][r] += 1

    for i in range(1, n+1):
        p, q = map(int, input().split())
        ans = 0
        for j in range(p, q+1):
            for k in range(p, q + 1):
                ans += a[j][k]
        print(ans)

m()

Submission status: Runtime Error

Solution code:
n,m,q = map(int, input().split())
m_dict = dict()
for i in range(1,m+1):
  m_dict[i] = []
for i in range(m):
  s,e = map(int, input().split())
  m_dict[s].append(e)
for i in range(q):
  s,e = map(int, input().split())
  cnt = 0
  for j in range(s,e+1):
    cnt += len([ k for k in m_dict[j] if k <= e ])
  print(cnt)

Submission status: Runtime Error

Solution code:
n,m,q = map(int, input().split())
m_dict = dict()
for i in range(1,m+1):
  m_dict[i] = []
for i in range(m):
  s,e = map(int, input().split())
  m_dict[s].append(e)
for i in range(q):
  s,e = map(int, input().split())
  cnt = 0
  for j in m_dict.keys():
    if len(m_dict[j]) == 0: continue
    elif j < s: continue  
    elif e < j: break  
    else: cnt += len([ k for k in m_dict[j] if k <= e ])
  print(cnt)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
a=list(map(int,input().split()))
a[0]=a[0]%m
for i in range(n-1):
    a[i+1]=(a[i]+a[i+1])%m
result=0
for i in range(n):
    if a[i]==0:
        result+=1

a.sort()
num=a[0]
b=0
for i in range(n):
    if a[i]==num:
        b+=1
    else:
        result+=b*(b-1)/2
        b=1
        num=a[i]
print(int(result+b*(b-1)/2))

Submission status: Runtime Error

Solution code:
'''
    N  都市　西から順に1,2,3...N
    M　列車の数
    Q　質問の数
    L, R 列車iが走行する都市の区間
    p, q 都市pから都市qまでの区間に、走る区間が完全に含まれている
    　　　列車の数を問う
'''

def logic(N, M, Q, L, R, p, q):
    ret = []
    for pq in range(len(p)):
        count = 0
        for lr in range(len(L)):
            if p[pq] <= L[lr] and R[lr] <= q[pq]:
                count += 1
        ret.append(count)
    return ret


def main():
    N, M, Q = map(int, input().split())
    L, R, p, q = [], [], [], []
    for __ in range(N):
        LR = list(map(int, input().split()))
        L.append(LR[0])
        R.append(LR[1])
    for __ in range(Q):
        pq = list(map(int, input().split()))
        p.append(pq[0])
        q.append(pq[1])
    ret = logic(N, M, Q, L, R, p, q)
    [print(st) for st in ret]


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
N,M,Q = map(int,raw_input().split())
a = []
for i in range(M):
  b = map(int,raw_input().split())
  a.append(b)
for i in range(N):
  c,d = map(int,raw_input().split())
  x = 0
  for j in range(M):
    e = a[j]
    if c <= int(e[0]) and d >= int(e[1]):
      x += 1
  print x

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

Solution code:
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

Submission status: Runtime Error

Solution code:
N,M,Q = map(int,input().split())
T = [[0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(M):
  L,R = map(int, input().split())
  T[L][R] += 1
pprint(T)
for l in range(1,N+1):
  for r in range(1,N+1):
    T[l][r] += T[l-1][r]+T[l][r-1]-T[l-1][r-1]
ans = []
pprint(T)
for i in range(Q):
  p,q = map(int, input().split())
  ans.append(T[p-1][p-1]+T[q][q]-T[p-1][q]-T[q][p-1])
print('\n'.join(map(str,ans)))
quit()

Submission status: Runtime Error

Solution code:
a = list(map(int, input().split()))
 
p = [list(map(int, input().split())) for i in range(M)]
q = [list(map(int, input().split())) for i in range(Q)]
 
res = [[0]*N for i in range(N)]
 
def lsadd(L,R):
    L-=1
    R-=1
    for i in range(0,L+1):  
        res[i][R] += 1
 
for l,r in p:
    lsadd(l,r)
 
for l,r in q:
    print(sum(res[l-1][:r]))

Submission status: Runtime Error

Solution code:
#include <iostream>

using namespace std;

int data[600][600];
int data_s[600][600];
int L[200009];
int R[200009];
int p[100009];
int q[100009];

int main(int argc, char** argv) {
    int N, M, Q;
    cin >> N >> M >> Q;
    for (int i = 1; i <= M; i++) {
        cin >> L[i] >> R[i];
        data[L[i]][R[i]]++;
    }
    for (int i = 1; i <= Q; i++) cin >> p[i] >> q[i];
    for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) data_s[i][j] = data_s[i][j - 1] + data[i][j];
    for (int i = 1; i <= N; i++) for (int j = 1; j <= N; j++) data_s[i][j] = data_s[i - 1][j] + data_s[i][j];
    for (int i = 1; i <= Q; i++) {
        int ans = 0;
        ans += data_s[q[i]][q[i]] - data_s[p[i] - 1][q[i]] - data_s[q[i]][p[i] - 1] + data_s[p[i] - 1][p[i] - 1];
        cout << ans << endl;
    }
}

Submission status: Runtime Error

Solution code:

def solve(s,e):
	res=0
	for i in range(s,e+1):
		res+=train[i][e+1]-train[i][s]
	return res

city,dnum,qnum=map(int,input().split())

train=[[0 for i in range(city+1)] for i in range(city+1)]

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

for i in train:
	tmp=0
	for j in i:
		tmp+=j
		j=tmp
	
querry=[list(map(int,input().split())) for i in range(qnum)]

for q in querry:
	print(solve(*q))

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))

k = [0 for i in range(a[0])] for j in range(a[0])

for i in range(a[1]):
    m,n = map(int,input().split())
    k[m-1][n-1] += 1

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

Submission status: Runtime Error

Solution code:
a = list(map(int,input().split()))

k = [0 for i in range(a[0])] for j in range(a[0])

for i in range(a[1]):
    m,n = map(int,input().split())
    k[m][n] += 1

for i in range(a[2]):
    p = 0
    for j in range(m):
        for k in range(n):
            p += k[m][n]
    print(p)

Submission status: Runtime Error

Solution code:
n, m, q = map(int, input().split())
cum = [[0]
for i in range(m):
    li, ri = map(int, input().split())
    lis.append(li)
    ris.append(ri)

for i in range(q):
    pi, qi = map(int, input().split())
    total = 0
    for (li, ri) in zip(lis, ris):
        if pi <= li and ri <= qi:
            total += 1
    print(total)

Submission status: Runtime Error

Solution code:
n,m,Q=[int(x) for x in input().split()]
lr,p,q=[(0,0)],[],[]
l,r=0,1
for _ in [1]*m:
    li,ri=[int(x) for x in input().split()]
    lr.append((li,ri))
lr=sorted(lr)
# print(lr)
for _ in [1]*Q:
    pi,qi=[int(x) for x in input().split()]
    p.append(pi)
    q.append(qi)
for i in range(Q):
    ans=0
    first=0
    last=m+1
    index=0
    while first<=last:
        # print(first,last)
        index=(first+last)//2
        if lr[index-1][l] < p[i] <= lr[index][l]:
            break
        elif lr[index][l]<p[i]:
            first =index+1
        elif p[i] <= lr[index-1][l]:
            last=index-1

    for j in range(index,m+1):
        if lr[j][r] <= q[i]:
            ans+=1
    print(ans)

Submission status: Runtime Error

Solution code:
# input
N, M, Q = map(int, input().split())
train_query = {} # 対象区間とクエリを一緒にソート
for i in range(M + Q):
    train_query[i] = list(map(int, input().split()))

train_query = sorted(train_query.items(), key=lambda x: x[1], reverse = True)
# 辞書をソートするとリストが返ってくることに注意

a = [0 for _ in range(N)]

for j in range(M + Q):
    if train_query[j][0] < M: # 対象区間
        a[train_query[j][1][0]] = 1
    else: # クエリ
        ans = sum(a[train_query[j][1][0]:train_query[j][1][1]])
        print(ans)

Submission status: Runtime Error

Solution code:
import sys
s = sys.stdin.readlines()
N,M,Q = map(int,s[0].split())

Section = [[0]*N for _ in range(N)]
for L,R in (map(int, e.split()) for e in s[1:M+1):
    Section[L-1][R-1] += 1

Sum = [[0]*(N+1) for _ in range(N+1)]
for i in range(N):
    for j in range(N):
        Sum[i+1][j+1] = Sum[i][j+1]+Sum[i+1][j]-Sum[i][j]+Section[i][j]

Ans = [[0]*N for _ in range(N)]
for i in range(N):
    for j in range(i,N):
        Ans[i][j] = Sum[j+1][j+1]-Sum[i][j+1]

for p,q in (map(int, e.split()) for e in s[M+1:]
    print(Ans[p-1][q-1])