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

×

WOUT(AUG15)

I used segment tree with lazy propagation on problem WOUT but still got tle for 2nd subtask. Why?

This is link to my solution..please suggest any modification

https://www.codechef.com/viewsolution/7746551

asked 18 Aug '15, 18:50

akhileshydv20's gravatar image

2★akhileshydv20
173
accept rate: 0%


You may have a look at my friend's solution. https://www.codechef.com/viewsolution/7698077

link

answered 18 Aug '15, 19:47

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

The main reason you are getting TLE is because your are trying to set 10^7 size array to 0 for every test case.
10^7 * 10^3 = 10^10 (TLE).
Also your lazy propagation seems to be slow....I tried replacing your memset with update tree calls and yet a few cases gave TLE.

I am not sure how you can solve it with segment tree in the given time limit but you can try my solution. link

My Algo is as follows:
Let a be the no. of l values <= i
Let b be the no.of h values < i
No of blocks to remove in that row = N - a + b

Then you can sum up all H consecutive row ans and find the minimum in O(N)

Note:I sorted l,h values so over all complexity is O(NLogN), but you can use counting sort to do it in O(N).

Hope this helps :)

link

answered 18 Aug '15, 20:49

abbas's gravatar image

4★abbas
4118
accept rate: 28%

You used memset to set two arrays each of length 10^7.

Also the test cases limit was 1000.

Considering you have 100 test cases only,memset would take >3s on ideone.

Here check it out-link

link

answered 19 Aug '15, 14:46

prrateekk's gravatar image

3★prrateekk
534216
accept rate: 12%

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:

×9

question asked: 18 Aug '15, 18:50

question was seen: 529 times

last updated: 19 Aug '15, 14:46