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

Maximize AND

Back to problem

Editorial

It is enough to quickly test whether there exists an AiA_iAi​ containing every set bit of a mask SSS.

Create a boolean array cancancan of size 2202^{20}220. Initially, set can[Ai]=truecan[A_i]=\mathrm{true}can[Ai​]=true for every value appearing in the sequence. Then, for each bit b=0,1,⋯ ,19b=0,1,\cdots,19b=0,1,⋯,19 and every mask SSS whose bbb-th bit is zero, apply

can[S]←can[S]∨can[S∣2b].can[S] \leftarrow can[S] \lor can[S \mathbin{|} 2^b].can[S]←can[S]∨can[S∣2b].

After this SOS DP, can[S]can[S]can[S] is true exactly when there exists an index iii such that AiA_iAi​ contains every set bit of SSS, equivalently .

To answer a query XXX, start with ans=0ans=0ans=0 and inspect bits from 191919 down to 000. If the current bit is set in XXX and can[an is true, add that bit to . Since higher bits are made 1 whenever this remains feasible, the final value is maximum.

For one test case, preprocessing takes O(N+20⋅220)O(N+20\cdot 2^{20})O(N+20⋅220) time, and all queries take O(20Q)O(20Q)O(20Q) time. The memory usage is O(220)O(2^{20}).

Proof

After the SOS DP, can[S]can[S]can[S] is true exactly when one AiA_iAi​ contains all set bits of SSS. Therefore, during a query, if can[ans∣ is true, there exists a single that simultaneously contains every bit already chosen and bit .

Solution written by GPT5.6

(Ai&S)=S(A_i \mathbin{\&} S)=S
(Ai​&S)=S
s∣2b]can[ans \mathbin{|} 2^b]
can[ans∣2b]
ansansans
O(220)
2b]can[ans \mathbin{|} 2^b]
can[ans∣2b]
AiA_iAi​
bbb

Consider bit bbb while processing bits from high to low. If bit bbb can be made 1, every value with bit bbb equal to 1 is larger than every value with the same higher bits and bit bbb equal to 0, because all lower bits together contribute at most 2b−12^b-12b−1. Thus choosing bit bbb whenever it is feasible is optimal.

Repeating this argument for every bit preserves the largest feasible prefix of the answer. At the end, the constructed value is achievable as X&AiX \mathbin{\&} A_iX&Ai​ for some iii and no larger achievable value exists. Hence the algorithm is correct.