LushoPlusPlus's blog

By LushoPlusPlus, history, 6 years ago, In English

Hello Codeforces.

Last week i just trying to solve this problem bubblesort2 so i just was able to solve until the first 2 subtasks, these is my solutions for the first 2 subtask.

SUBTASK 1 and 2:

I create an array of pases, for each i (0<=i <n), I store Pases[i]=Solve(i)

Solve(i) --> , in it, I will store the amount of prior numbers greater than A[i].

and the maximun passes is gonna be the answer.

and finally for the update I just do the same but here in O(n), how?

let's : Pos= X[i], Nuevo=V[i], Antiguo=A[Pos];

I update A[pos]=Nuevo;

after that i change the value of Pases[i], just calling the funtion Solve(i), I mean:

Pases[Pos]=Solve(Pos);

and in order to update all the numbers after Pos (Pos+1 <= j < n), I just use this condition:

if(Antiguo >= b and Nuevo < b) Pases[j]--; if(Antiguo <= b and Nuevo > b) Pases[j]++;

i finally y just find the maximun value.

Here is my Code

this solution gives me 38 points, but now i can't continue anymore, because i don't know how to solve the 3rd subtask and the last one. please help me I am with this problem the last week.

  • Vote: I like it
  • -4
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by LushoPlusPlus (previous revision, new revision, compare).

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

First of all sorry for my bad English.

This question is nearly same as USACO 2018 Silver 1. question. You can reach it from : here

You can reach the question's official solution from here Official solution's complexity is O(nlogn).

Another solution is: For each element k in array A you need to find how many elements m have 2 occasions:

  1. indice of m is smaller than indice of k
  2. value of m is smaller than value of m

Answer is (maximum of numbers we found) + 1

To solve this we can use a segment tree where every node of this segment tree is a std::vector , and use binary search while we answer queries.

it's time complexity is O(n * (logn) * (logn))

If you don't understand you can see :this link