問題一覧 > 通常問題

No.1282 Display Elements

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 134
作問者 : platinumplatinum / テスター : leafirbyleafirby
2 ProblemId : 4441 / 出題時の順位表
問題文最終更新日: 2020-11-06 22:16:25

問題文

A君、B君はそれぞれ$\ N\ $枚のカードを持っています。
$i\ $番目のカードには、それぞれ正の整数$\ a_i,\ b_i\ $が書かれています。
二人はこれから次の操作を繰り返します。$i\ $回目 $(i=1,\ 2,\ \dots,\ N)$ の操作は次の通りです。

・B君が$\ i\ $番目のカードを場に出す。次にA君がまだ選んでいないカードから一枚選んで提示する。
・A君が提示したカードに書かれた整数と、場にあるカードに書かれた整数を一枚ずつ比較する。
 提示したカードに書かれた整数の方が大きいたびに、A君は$\ 1\ $点を得る。

このとき、A君が獲得できる得点の最大値を求めてください。


22:16 追記:「カードの数字」という表現を、「カードに書かれた整数」に変更しました。

入力

$N$
$a_1\ a_2\ \dots\ a_N$
$b_1\ b_2\ \dots\ b_N$

・入力は全て整数である。
・$1 \le N \le 10^5$
・$1 \le a_i, b_i \le 10^9$

出力

A君が獲得できる得点の最大値を出力してください。

サンプル

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

はじめにB君が $3$ が書かれた一枚目のカードを場に出します。
A君は $1$ を提示するべきですが $1$ ターン目は得点を獲得できません。
次にB君が $4$ が書かれた二枚目のカードを場に出します。
A君は残った $5$ が書かれたカードを提示します。これは $3$, $4$ より大きく、 $2$ 点を獲得します。
提示する順番を逆にすると $1$ 点しか獲得できないので、得点の最大値である $2$ を出力します。

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

このケースではどのような順番でカードを提示しても結果は変わりません。

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

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