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

Median 2

Back to problem

Editorial

First consider only the prefix records AAA. Define X1,X2,⋯ ,XNX_1,X_2,\cdots,X_NX1​,X2​,⋯,XN​ by

Xi={Ai/2(i is odd),Ai−Xi−1(i is even).X_i=\begin{cases} A_i/2 & (i\text{ is odd}),\\ A_i-X_{i-1} & (i\text{ is even}). \end{cases}Xi​={

If AiA_iAi​ is odd for an odd iii, or if some XiX_iXi​ is outside [1,N][1,N], the answer is impossible.

For odd i=2k−1i=2k-1i=2k−1, XiX_iXi​ is the median of the first iii elements. After adding one new element, the old median must remain one of the two middle elements of the new set of size 2. Hence, for even , the two middle elements are exactly and .

This gives an interval CiAC_i^ACiA​ of values allowed for PiP_iPi​. For i=1i=1i=, we must have . For even , let and . If , then ; if , then . The case is impossible because the two middle values are distinct.

For odd i≥3i\ge 3i≥3, let l<ul<ul<u be the two middle values of the previous even-sized prefix. The new median XiX_iXi​ must lie in [l,u. If , then ; if , then ; and if , then . Thus is always one integer interval.

Position restrictions alone are not sufficient. Since XiX_iXi​ is an element already present at time iii, pos⁡(Xi)≤i\operatorname{pos}(X_i)\le ipos(Xi​). Also, if the two middle elements of an even prefix are , no value strictly between them may have appeared yet. Therefore, for every , . Collecting these restrictions gives one interval for every value .

Why the prefix conditions are sufficient

The conditions above are also sufficient. Proceed by induction on the prefix length. Suppose an odd prefix has median ccc, and the other middle value required at the next even step is q<cq<cq<c. The deadline condition guarantees that qqq has already appeared, while the release conditions guarantee that no value between qqq and cc has appeared. Hence is the element immediately below . Adding a new value makes exactly the two middle values. The case is symmetric.

Process the suffix records BBB symmetrically from right to left. According to the parity of the suffix length N−i+1N-i+1N−i+1, define

Yi={Bi/2(N−i+1 is odd),Bi−Yi+1
Ai​/2
Ai​−Xi−1​
​
(i is odd),(i is even).​
[1,N]
k2k
2k
iii
Xi−1X_{i-1}Xi−1​
XiX_iXi​
1
P1=X1P_1=X_1P1​=X1​
iii
c=Xi−1c=X_{i-1}c=Xi−1​
q=Xiq=X_iq=Xi​
q<cq<cq<c
Pi≤qP_i\le qPi​≤q
q>cq>cq>c
Pi≥qP_i\ge qPi​≥q
q=cq=cq=c
][l,u]
[l,u]
Xi=lX_i=lXi​=l
Pi<lP_i<lPi​<l
Xi=uX_i=uXi​=u
Pi>uP_i>uPi​>u
l<Xi<ul<X_i<ul<Xi​<u
Pi=XiP_i=X_iPi​=Xi​
CiAC_i^ACiA​
≤
i
l<ul<ul<u
l<v<ul<v<ul<v<u
pos⁡(v)≥i+1\operatorname{pos}(v)\ge i+1pos(v)≥i+1
LvA≤pos⁡(v)≤RvAL_v^A\le \operatorname{pos}(v)\le R_v^ALvA​≤pos(v)≤RvA​
vvv
c
qqq
ccc
Pi≤qP_i\le qPi​≤q
q,cq,cq,c
q>cq>cq>c

For an even prefix with middle values l<ul<ul<u, no previously used value lies between them. If the next median is strictly inside the interval, that value itself must be inserted. If the next median is one endpoint, a value must be inserted outside the opposite side. These are exactly the three forms encoded by CiAC_i^ACiA​. Thus every prefix median is correct.

(N−i+1 is even).Y_i=\begin{cases} B_i/2 & (N-i+1\text{ is odd}),\\ B_i-Y_{i+1} & (N-i+1\text{ is even}). \end{cases}
Yi​={Bi​/2Bi​−Yi+1​​(N−i+1 is odd),(N−i+1 is even).​

This yields an interval CiBC_i^BCiB​ for the value at position iii, and an interval LvB≤pos⁡(v)≤RvBL_v^B\le \operatorname{pos}(v)\le R_v^BLvB​≤pos(v)≤RvB​ for each value. Now YiY_iYi​ must occur inside the suffix, so pos⁡(Yi)≥i\operatorname{pos}(Y_i)\ge ipos(Yi​)≥i. If an even-length suffix has middle values l<ul<ul<u, every l<v<ul<v<ul<v<u must lie before that suffix, so pos⁡(v)≤i−1\operatorname{pos}(v)\le i-1pos(v)≤i−1.

Combining both directions gives one value interval ℓi≤Pi≤ri\ell_i\le P_i\le r_iℓi​≤Pi​≤ri​ for every position and one position interval Lv≤pos⁡(v)≤RvL_v\le \operatorname{pos}(v)\le R_vLv​≤pos(v)≤Rv​ for every value. If any intersection is empty, the instance is impossible.

Now fill positions i=1,2,⋯ ,Ni=1,2,\cdots,Ni=1,2,⋯,N from left to right. Activate a value vvv when i=Lvi=L_vi=Lv​. Among active unused values satisfying ℓi≤v≤ri\ell_i\le v\le r_iℓi​≤v≤ri​, choose the one with the smallest RvR_vRv​.

The greedy choice follows from an exchange property specific to intervals produced by median records. Suppose a feasible completion places ppp at the current position iii, while the greedy chooses qqq. Let j≥ij\ge ij≥i be the position of qqq in that completion. Since the greedy minimizes deadlines, Rq≤RpR_q\le R_pRq​≤Rp​. Because qqq can be placed at jjj, we have j≤Rqj\le R_qj≤Rq​, hence j≤Rpj\le R_pj≤Rp​. Also Lp≤i≤jL_p\le i\le jLp​≤i≤j.

It remains to check the value interval at position jjj. The derived intervals have the following property: if i<ji<ji<j, both ppp and qqq are locally allowed at iii, qqq is locally allowed at jjj, but ppp is not, then Rp<RqR_p<R_qRp​<Rq​. This follows by checking the three possible forms of a one-sided local interval. At the first boundary change that separates ppp from qqq, either ppp becomes a determined prefix middle value and therefore must already have appeared, or ppp falls strictly between the two middle values of an even suffix and therefore must appear before that suffix. In both cases this boundary contributes a deadline smaller than jjj to ppp, while qqq remains possible at jjj and hence has deadline at least jjj.

Here Rq≤RpR_q\le R_pRq​≤Rp​, so this separation is impossible. Thus ppp is also allowed at position jjj. Swapping ppp and qqq preserves feasibility, producing a completion that contains the greedy choice. Repeating this argument proves the greedy algorithm.

To build the value-position intervals, the prefix side needs range chmax updates for releases, and the suffix side needs range chmin updates for deadlines. Since only final point values are needed, lazy segment trees that store only pending extrema are sufficient, giving O(Nlog⁡N)O(N\log N)O(NlogN) total time.

For the final greedy, store value vvv at coordinate vvv in a segment tree. An active unused value stores the pair (Rv,v)(R_v,v)(Rv​,v); inactive or used values store infinity. At position iii, a range-minimum query on [ℓi,ri][\ell_i,r_i][ℓi​,ri​] gives the greedy choice. If the global minimum deadline ever becomes smaller than iii, some value has already missed its deadline and the instance is impossible.

After construction, all prefix and suffix medians may be recomputed with Fenwick-tree order statistics as a final consistency check. This does not change the complexity.

The time complexity is O(Nlog⁡N)O(N\log N)O(NlogN) and the memory complexity is O(N)O(N)O(N).

Solution written by GPT5.6