JOI '18 P1 - Bubble Sort 2

View as PDF

Submit solution

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 A_0, A_1, \ldots, A_{N-1} of length N 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 A_i and A_{i+1} if A_i > A_{i+1}, for i = 0, 1, \ldots, N - 2 in this order. It is known that any sequence can be sorted in non-decreasing order by some passes. For a sequence A, we define the number of passes by bubble sort as the number of passes needed to sort A using the above algorithm.

JOI-kun has a sequence A of length N. He is going to process Q queries of modifying values of A. To be specific, in the (j+1)-th query (0 \le j \le Q-1), the value of A_{X_j} is changed into V_j.

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

Example

Given a sequence A = \{1,2,3,4\} of length N = 4 and Q = 2 queries: X = \{0,2\}, V = \{3,1\}.

  1. For the first query, the value of A_0 is changed into 3. We obtain A = \{3, 2, 3, 4\}.
  2. For the second query, the value of A_2 is changed into 1. We obtain A = \{3, 2, 1, 4\}.

Bubble sort for A = \{3, 2, 3, 4\}:

  • A is not sorted, so the first pass starts. Since A_0 > A_1, we swap them to get A = \{2,3,3,4\}. Since A_1 \le A_2, we don't swap them. Since A_2 \le A_3, we don't swap them.
  • Now A is sorted, so the bubble sort ends.

Hence, the number of passes by bubble sort is 1 for A = \{3, 2, 3, 4\}.

Bubble sort for A = \{3, 2, 1, 4\}:

  • A is not sorted, so the first pass starts. Since A_0 > A_1, we swap them to get A = \{2,3,1,4\}. Since A_1 > A_2, we swap them to get A = {2,1,3,4}. Since A_2 \le A_3, we don't swap them.
  • A is not sorted yet, so the second pass starts. Since A_0 > A_1, we swap them to get A = \{1,2,3,4\}. Since A_1 \le A_2, we don't swap them. Since A_2 \le A_3, we don't swap them.
  • Now A is sorted, so the bubble sort ends.

Hence, then number of passes by bubble sort is 2 for A = \{3, 2, 1, 4\}.

Subtasks

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

Subtask Score N Q A, V
1 17 1 \le N \le 2\ 000 1 \le Q \le 2\ 000 1 \le A_i, V_j \le 1\ 000\ 000\ 000
2 21 1 \le N \le 8\ 000 1 \le Q \le 8\ 000 1 \le A_i, V_j \le 1\ 000\ 000\ 000
3 22 1 \le N \le 50\ 000 1 \le Q \le 50\ 000 1 \le A_i, V_j \le 100
4 40 1 \le N \le 500\ 000 1 \le Q \le 500\ 000 1 \le A_i, V_j \le 1\ 000\ 000\ 000

Implementation details

You should implement the following function countScans to answer Q queries.

std::vector<int> countScans(std::vector<int> A, std::vector<int> X, std::vector<int> V);
  • A: array of integers of length N representing the initial values of the sequence.
  • X, V: arrays of integers of length Q representing queries.
  • This function should return an array S of integers of length Q. For each 0 \le j \le Q - 1, S_j should be the number of passes by bubble sort for the sequence right after processing (j + 1)-th query.

Comments

There are no comments at the moment.