183AC - ABC106D: AtCoder Express 2

ABC106-D (400 points)

問題

東西に伸びる 本の線路沿いに西から順に の 個の都市が並んでいる.
本の列車がそれぞれ都市 と の区間を走っているとき, 個の区間 に完全に含まれる列車の本数をそれぞれ求める.

• 
• 
• 
• 
• 

方針

• 以下の記事に完全にお世話になりました.

http://hama-du-competitive.hatenablog.com/entry/2017/04/22/185540

• 想定解は二次元累積和.

# 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][1])
print(train_query)
# 辞書をソートするとリストが返ってくることに注意

StartPoints = [0 for _ in range(N)] # 対象区間の開始位置
ans = [0 for _ in range(Q)] # 各クエリに対する答え

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

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