You are not logged in. Please login at www.codechef.com to post your questions!

×

D. Array Restoration Getting TLE

Problem MySol .

My Approach - Answer is no if there exist $i < j$ in range minIndx of j to maxIdx of j. For This I have used segment tree. Time Complexity according to me - $O((n+q)*logn)$ Which Should pass TL.

asked 18 Aug '18, 04:27

aryanc403's gravatar image

5★aryanc403
2.3k1516
accept rate: 11%

closed 18 Aug '18, 12:05


what is your approach?? how you have used segment tree? i think solution possible without segment tree .

link

answered 18 Aug '18, 10:42

sna902055's gravatar image

5★sna902055
425
accept rate: 7%

I'm using segment tree. But I have not inserted 0 in tree. Instead using INF. And for given range l,r. I'm returning smallest no in this range. And using condition @vishesh345 's answer.

(18 Aug '18, 12:02) aryanc4035★

Can you elaborate your condition for no solution. According to me it was that if there exist i<j<k such that a[i] = a[k] and a[j] is smaller then answer is no. Can you briefly explain your approach.

link

answered 18 Aug '18, 11:43

vishesh345's gravatar image

3★vishesh345
444
accept rate: 0%

1

Yes, I'm using this condition. Along with checking if no q exist or not in given array. Or if it can be inserted or not.

(18 Aug '18, 12:00) aryanc4035★

Thank you friends. I have got AC on 33rd submission xD. I just removed one linear loop for inserting q by using some more variables. And removed handling of special case of 1.

link

answered 18 Aug '18, 12:03

aryanc403's gravatar image

5★aryanc403
2.3k1516
accept rate: 11%

edited 18 Aug '18, 12:03

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,699
×655

question asked: 18 Aug '18, 04:27

question was seen: 136 times

last updated: 18 Aug '18, 12:05