外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

T - Massive Excessive Impressive Cat Food

作成者 nekooooooo、siooisi、jammy、trueryob

テスター siooisi、tau0529、trueryob

配点 525 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

巨大な整数を KK 進数で表し、00 でない桁のみを連想配列で管理します。

加算に伴う繰り上げでは途中の桁が 00 になるため、繰り上げを含めた桁の更新回数は償却 O(M+Q)O(M+Q) 回です。一方、減算では繰り下がりが非常に多く発生する可能性があります。

そこで、減算を加算に置き換えることを考えます。

閾値 UU に加えて、C=0, Z=0C=0,\ Z=0 を管理します。実際のキャットフードの個数を C−ZC-Z として、

  • ti=1t_i=1 のとき、CC に xiKyix_iK^{y_i} を加える。
  • ti=2t_i=2 のとき、ZZ と UU の両方に xiKyix_iK^{y_i} を加える。

とします。

このように管理すると、各クエリの直後に C≥UC\ge U なら byebye, neko!、C<ZC<Z なら byebye, world! となります。

巨大整数の比較は上位の桁から順に行うことで、O(M+Q)O(M+Q) 時間で実行できます。

よって、全体の時間計算量は O((M+Q)2)O((M+Q)^2) となり、十分高速です。

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。