以下页面来自日本信息收集官方发布的原题PDF,已完整保存并渲染到本地。


可复制的 PDF 提取文本
Typhoon: 台風
input ファイル“typhoon.in”
output 標準出力
ソースファイルtyphoon.c/typhoon.cpp
時間制限2 秒/ データ
台風による被害を受けやすいある一直線の道がある.この道での台風による被害は,必ず連
続した一つの区間である.この道には,道に沿ってk 個の観測地点があり,道の一方の端点に
近い観測地点から順に1 からk まで番号がつけられている.
この道に被害を加えたn 個の台風の記録がある.台風i 号についての記録は,台風i 号による
被害を受けた観測地点のうち,最も番号の小さい観測地点の番号ai と,最も番号の大きい観測
地点の番号bi という形で記録されている.台風には,古いものから順に1 号からn 号まで番号
がつけられている.
最近,この道での台風による被害を研究することが気象学の大きな進歩に繋がることが分か
り,研究を進めるため,「観測地点pj がqj 号からrj 号までの台風のうち何個の台風により被害
を受けたか」という情報がm 個必要となった.
台風の記録と,研究を進めるために情報が必要とされる,観測地点と台風の番号の範囲の組
(以降これをクエリーと呼ぶ)が与えられたとき,それぞれのクエリーについて,被害を与えた
台風の個数を出力するプログラムを作成せよ.
Input. 入力ファイルtyphoon.in の1 行目には,3 つの整数n, m, k が空白を区切りとして書
かれている.これらは,記録にある台風の数がn 個,与えられるクエリーの数がm 個,観測地
点の数がk 個であることを表す.1 ≦n, m ≦100, 000,1 ≦k ≦1, 000, 000, 000 を満たす.
1 + i 行目(1 ≦i ≦n) には,2 つの整数ai, bi が空白を区切りとして書かれている.これらは,
台風i 号の被害を受けた観測地点の,最も番号の小さい観測地点の番号がai,最も番号の大き
い観測地点の番号がbi であることを表す.1 ≦ai ≦bi ≦k を満たす.
1 + n + j 行目(1 ≦j ≦m) には,3 つの整数pj, qj, rj が空白を区切りとして書かれている.
これらは,j 番目のクエリーの,地点の番号がpj で,台風の番号の範囲がqj からrj までである
ことを表す.1 ≦pj ≦k,1 ≦qj ≦rj ≦n を満たす.
Output. 出力は,標準出力に行うこと.与えられたクエリーについて,被害を与えた台風の
個数を与えられた順に改行区切りで出力せよ.つまり,j 行目(1 ≦j ≦m) に観測地点pj がqj
号からrj 号までの台風のうち何個の台風により被害を受けたかを表す1 つの整数を出力せよ.
台風–1/2
採点基準採点用データのうち,配点の10%分については,n, m, k ≦1000 を満たし,配点の別
の30%分については,全てのj についてqj = 1, rj = n を満たす.
例
typhoon.in 標準出力
3 3 10 1
1 7 3
5 10 2
3 5
1 1 1
5 1 3
5 2 3
台風–2/2