DOJ logoDOJ
問題
最近追加された問題保存した問題Workbooks
カテゴリDLCコンテストグループチーム掲示板
ランキング
正解数ランキングストリークランキングDOJ Powerランキング
提出状況
問題募集ログイン新規登録
DOJ logoDOJ

OI形式のサブタスク採点、Eloレーティング、Discord連携を備えたオンラインジャッジです。

問題
問題一覧カテゴリ
コミュニティ
コンテストランキング掲示板お知らせ外部のコンテストを開催するガイド
アカウント
ログイン新規登録ジャッジ状態
ポリシー
利用規約DLCの利用規則プライバシーAPI 文書言語ランタイムコンテストの順位報酬レーティングとパフォーマンス
© 2026 DOJ
All rights reserved
解説

Four Integer

問題に戻る

解説

すべての Ai+BjA_i+B_jAi​+Bj​ を配列 XXX に、すべての Ck+DℓC_k+D_\ellCk​+Dℓ​ を配列 YYY に入れる。各配列の長さは n2n^2n2 になる。和が等しくても、添字の組ごとに一つの要素として格納する。

両配列を昇順に並べる。XXX の未処理の最小値 xxx と YYY の未処理の最大値 yyy を見る。x+y<0x+y<0x+y<0 のとき、 と の残りのどの要素を足しても負になるため、 側を進める。 のとき、 と の残りのどの要素を足しても正になるため、 側を進める。

x+y=0x+y=0x+y=0 のとき、xxx と yyy が連続する個数をそれぞれ p,qp,qp,q とする。両方の区間から一つずつ選ぶ pqpq 通りを答えに加え、両側で対応する区間を飛ばす。各値と対になるのは符号を反転した値だけなので、同じ添字の組を二度数えることはない。

時間計算量は O(n2log⁡n)O(n^2\log n)O(n2logn)、空間計算量は O(n2)O(n^2)O(n2) である。四つの入力値の和は 32 ビット符号付き整数に収まる。出現回数の積と答えは最大 4 0004=256 000 000  なので、64 ビット整数で計算する。

Solution written by GPT

xx
x
YYY
XXX
x+y>0x+y>0x+y>0
yyy
XXX
YYY
pq
000 0004\,000^4=256\,000\,000\,000\,000
40004=256000000000000