Medeali's blog

Help on a problem.
By Medeali, history, 18 months ago, In English

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

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

»
18 months ago, hide # |
 
Vote: I like it +8 Vote: I do not like it

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

→ Reply
»
18 months ago, hide # |
 
Vote: I like it +3 Vote: I do not like it

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

→ Reply
  • »
    »
    18 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    thanks , i see now ,and since that build function has total of 2n calls this makes the complexity bad

    → Reply