問題一覧 > 通常問題

No.647 明太子

レベル : / 実行時間制限 : 1ケース 4.500秒 / メモリ制限 : 256 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 320
作問者 : mokomoko / テスター : cielciel
4 ProblemId : 2103 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2018-05-12 22:55:04

問題文

明太子同好会には$N$人のメンバーがいる。
今日は年に一度の明太子パーティーの日なので、メンバー達は明太子を買いに行くことにした。

明太子直売所では$M$種類の明太子が販売されており、$i$番の明太子の値段は$X_i$円、辛さは$Y_i$である。

$j$番のメンバーは$A_j$円以内で辛さが$B_j$以上の明太子を見ると購入せずにはいられなくなり、そのような条件に合う明太子は1種類につき1つ、必ず購入する。しかし、明太子にこだわりがある彼らがどちらか1つでも条件に合わない明太子は絶対に購入しない。

明太子同好会では最も多くの人が買ってきた明太子を「奇跡の明太子」とし1年間毎食欠かさず食べる文化があるのでどの明太子が最も多くの人に購入されたかを知りたい。

最も多く購入された明太子が複数ある場合は、全て「奇跡の明太子」に選ばれるようになる。

明太子同好会の代わりに「奇跡の明太子」に選ばれる明太子を求めてください。

2018/03/18 制約が4.5秒になりました。

入力

$N$
$A_1\ B_1$
$.$
$.$
$A_N\ B_N$
$M$
$X_1\ Y_1$
$.$
$.$
$X_M\ Y_M$

$1 \le N \le 10^4$
$1 \le M \le 10^3$
$1 \le X_i,Y_i,A_i,B_i \le 10^8$

出力

明太子同好会で「奇跡の明太子」に選ばれる明太子の番号を1行に1つずつ、昇順に出力してください。
1つも明太子が明太子同好会のメンバーに購入されなかった場合は0を出力してください。
また、最後には改行してください。

サンプル

サンプル1
入力
3
6 4
5 2
2 5
2
4 3
5 4
出力
2

1番の明太子は2番のメンバーに、2番の明太子は1,2番のメンバーにそれぞれ購入されます。
3番のメンバーは条件に合う明太子がないため1つも明太子を購入しません。

サンプル2
入力
5
5 7
6 3
4 1
8 6
5 4
3
2 4
6 5
4 2
出力
1

1番の明太子は2,3,5番のメンバーに、2番の明太子は1番のメンバーに、3番の明太子は3番のメンバーにそれぞれ購入されます。

サンプル3
入力
4
8 6
3 5
4 2
7 3
1
10 2
出力
0

明太子同好会のメンバーは全員、1つも明太子を購入することができません。

サンプル4
入力
3
3 4
1 7
5 3
4
1 5
2 6
5 2
6 7
出力
1
2

1番の明太子と2番の明太子はそれぞれ2人のメンバーに購入されます。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。