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

Can BCD Run Without Difficulty Inversions?

Back to problem

Editorial

Let PjP_jPj​ be the maximum difficulty before problem jjj, and QjQ_jQj​ the minimum difficulty after it. Use Pj=0P_j=0Pj​=0 when there is no earlier problem and Qj=M+1Q_j=M+1Qj​=M+1 when there is no later problem. The number of victims whose first failure is problem jjj is

max⁡(0,Aj−max⁡(Pj,Qj)).\max\bigl(0,A_j-\max(P_j,Q_j)\bigr).max(0,Aj​−max(Pj​,Q

Sum this expression over all jjj. Precompute the suffix minima QjQ_jQj​, then scan from left to right while maintaining PjP_jPj​. Both time and space complexity are .

Proof

With the problems sorted by difficulty, a participant of skill sss solves every problem of difficulty at most sss. They are therefore a victim exactly when a solvable problem appears after the first problem that stops them.

Problem jjj is the first failure exactly when Pj≤s<AjP_j\leq s<A_jPj​, and a later problem is solvable exactly when . The number of skill values satisfying both conditions is . Each victim has a unique first failure, so the sum counts every victim exactly once.

j​
)
)
.
O(N)O(N)
O(N)
≤
s<
Aj​
Qj≤sQ_j\leq sQj​≤s
max⁡(0,Aj−max⁡(Pj,Qj))\max(0,A_j-\max(P_j,Q_j))max(0,Aj​−max(Pj​,Qj​))