SRTO3 - Editorial

editorial
, ,
1

PROBLEM LINK:

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

Author: moonlight_cl25
Tester: mexomerf
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

Sorting

PROBLEM:

You have two integer arrays A and B, of lengths N and M.
For each i = 1, 2, 3, \ldots, M in order, sort the last B_i elements of A.
Print the final array.

EXPLANATION:

Let’s look at what happens with two consecutive sort operations, B_i and B_{i+1}.

If B_i \geq B_{i+1}, the last B_{i+1} elements of A are already sorted by the i-th operation, so the (i+1)-th operation doesn’t change them at all.
We can just pretend this operation doesn’t exist.

If B_i \lt B_{i+1}, the last B_{i+1} elements of A will be sorted.
But then, the result of the i-th operation doesn’t matter at all! The set of elements sorted would be the same, so this time we can pretend the i-th operation doesn’t exist.

Together, this brings us to a simple conclusion.
Let K = \max(B_1, B_2, \ldots, B_M).
Then, the last K elements of A must be sorted

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Editorialist's code (Python) 
for _ in range(int(input())):
    n, m = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    mx = max(b)
    a = a[:n-mx] + sorted(a[n-mx:])
    print(*a)
1 Like