JOI '18 P1 - Bubble Sort 2

View as PDF

Points: 20 (partial)
Time limit: 5.0s
Memory limit: 512M

Problem type
Allowed languages
C++

Bubble sort is an algorithm to sort a sequence. Let's say we are going to sort a sequence of length in non-decreasing order. Bubble sort swaps two adjacent numbers when they are not in the correct order. Swaps are done by repeatedly passing through the sequence. Precisely speaking, in a pass, we swap and if , for in this order. It is known that any sequence can be sorted in non-decreasing order by some passes. For a sequence , we define the number of passes by bubble sort as the number of passes needed to sort using the above algorithm.

JOI-kun has a sequence of length . He is going to process queries of modifying values of . To be specific, in the ()-th query (), the value of is changed into .

JOI-kun wants to know the number of passes by bubble sort for the sequence after processing each query.

Example

Given a sequence of length and queries: , .

1. For the first query, the value of is changed into . We obtain .
2. For the second query, the value of is changed into . We obtain .

Bubble sort for :

• is not sorted, so the first pass starts. Since , we swap them to get . Since , we don't swap them. Since , we don't swap them.
• Now is sorted, so the bubble sort ends.

Hence, the number of passes by bubble sort is for .

Bubble sort for :

• is not sorted, so the first pass starts. Since , we swap them to get . Since , we swap them to get . Since , we don't swap them.
• is not sorted yet, so the second pass starts. Since , we swap them to get . Since , we don't swap them. Since , we don't swap them.
• Now is sorted, so the bubble sort ends.

Hence, then number of passes by bubble sort is for .

There are 4 subtasks. The score and the constraints for each subtask are as follows:

1 17
2 21
3 22
4 40

Implementation details

You should implement the following function countScans to answer queries.

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V);

• A: array of integers of length representing the initial values of the sequence.
• X, V: arrays of integers of length representing queries.
• This function should return an array of integers of length . For each , should be the number of passes by bubble sort for the sequence right after processing ()-th query.