Блог пользователя Medeali

Автор Medeali, история, 12 месяцев назад, По-английски

I i am trying to solve this problem https://oj.uz/problem/view/APIO23_sequence, my idea is to basically go through each distinct element and find the max answer with a subarray of whose median is that element ,for that for each element i go through each positions in the array and do some updates using a segment tree range update,along with a binary search, my code's complexity should be O(N log N) because the segment tree updates or calculations are not inside the binary search ,however this only passed for N>=2e3.Can someone help identiy the source of TLE. Here is link to my submission https://oj.uz/submission/1182100

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

If you go through each element and then go through each position that is already n squared

»
12 месяцев назад, скрыть # |
 
Проголосовать: нравится +3 Проголосовать: не нравится

In your build function, you pass the vector by value. So you keep recursively creating new copies of the vector.

Passing it by reference should suffice ==> Submission