DOJ logoDOJ
Problems
Recently added problemsSaved problemsWorkbooks
CategoriesDLCContestsGroupsTeamsBoard
Ranking
Solved Problem RankingStreak rankingDOJ Power ranking
Status
Call for TasksLoginRegister
DOJ logoDOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord account linking.

Problems
ProblemsCategories
Community
ContestsRankingBoardNoticesHost an external contestGuide
Account
LoginRegisterJudge Status
Policy
Terms of ServiceDLC RulesPrivacyAPI documentationLanguage runtimesContest rank rewardsRating and performance
© 2026 DOJ
All rights reserved
Editorial

Four Integer

Back to problem

Editorial

Put every sum Ai+BjA_i+B_jAi​+Bj​ in an array XXX and every sum Ck+DℓC_k+D_\ellCk​+Dℓ​ in an array YYY. Each array has length n2n^2n2. Include a separate entry for every index pair, even if several pairs give the same sum.

Sort both arrays in increasing order. Consider the smallest unprocessed value xxx of XXX and the largest unprocessed value yyy of YYY. If x+y<0x+y<0x+y<, pairing with any remaining value of still gives a negative sum, so advance on the side. If , pairing with any remaining value of gives a positive sum, so advance on the side.

If x+y=0x+y=0x+y=0, let ppp and qqq be the lengths of the current runs of xxx and yyy. Every pairing between the runs gives a valid tuple. Add and skip both runs. A value can only be matched with its negation, so no tuple is counted twice.

The time complexity is O(n2log⁡n)O(n^2\log n)O(n2logn) and the space complexity is O(n2)O(n^2)O(n2). A sum of four input values fits in a signed 32-bit integer. Use 64-bit integers for the product of the multiplicities and for the answer, which can reach 4 0004.

Solution written by GPT

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