Loading problem...

Preparing the statement, recent submissions, and submit form.

DOJ

Community online judge with OI-style subtask scoring, Elo ratings, and Discord-backed certification.

Problems

Problems Categories

Community

Contests Ranking Board Notices Host an external contest Guide

Account

Policy

Editorial

Can BCD Run Without Difficulty Inversions?

Back to problem

Editorial

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

\max\bigl(0,A_j-\max(P_j,Q_j)\bigr).

Sum this expression over all $j$ . Precompute the suffix minima $Q_j$ , then scan from left to right while maintaining $P_j$ . Both time and space complexity are .

Proof

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

Problem $j$ is the first failure exactly when $P_j\leq s<A_j$ , 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.

)

O

(

N

)

O(N)

O (N)

≤

Q_j\leq s

\max(0,A_j-\max(P_j,Q_j))