No.647 明太子
タグ : / 解いたユーザー数 329
作問者 : moko / テスター : ciel
問題文
明太子同好会には$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もしくは右上の雲マークをクリックしてアカウントを作成してください。