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.
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.
Auto comment: topic has been updated by LushoPlusPlus (previous revision, new revision, compare).
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:
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