WAIT1 - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

N people buy tickets for an event in the order 1, 2, \ldots, N.
Person i arrives at the event at time A_i.
A person can enter only after everyone with a smaller ticket number has entered already. As soon as this condition is satisfied, they can enter immediately; otherwise they must wait.

Find the total wait time across all N people.

EXPLANATION:

The i-th person must wait for the people 1, 2, \ldots, i-1 to enter first.

Thus, no matter what, their entrance time is limited by the largest of the entry times of the first i-1 people, i.e by \max(A_1, \ldots, A_{i-1}).

Of course, person i’s entry time is limited by their own arrival time as well.
Thus, a stricter bound on their entry time is

\max(A_1, A_2, \ldots, A_i)

Clearly, person i will be able to enter at this time; since by then everyone with a smaller-numbered ticket would’ve arrived and been able to enter as well.

Thus, the waiting time for person i equals

\max(A_1, \ldots, A_i) - A_i

The answer is the sum of this value across all 1 \le i \le N.

This is easy to compute in \mathcal{O}(N) time by maintaining prefix maximums of the input array.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    pmax = 0
    ans = 0
    for x in a:
        pmax = max(pmax, x)
        ans += pmax - x
    print(ans)
WAIT2 - Editorial