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



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

asked 18 Aug '15, 18:50

akhileshydv20's gravatar image

accept rate: 0%

You may have a look at my friend's solution.


answered 18 Aug '15, 19:47

likecs's gravatar image

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 :)


answered 18 Aug '15, 20:49

abbas's gravatar image

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


answered 19 Aug '15, 14:46

prrateekk's gravatar image

accept rate: 12%

toggle preview

Follow this question

By Email:

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



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "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:


question asked: 18 Aug '15, 18:50

question was seen: 529 times

last updated: 19 Aug '15, 14:46