×

# WOUT(AUG15)

 0 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 17●3 accept rate: 0%

 0 You may have a look at my friend's solution. https://www.codechef.com/viewsolution/7698077 answered 18 Aug '15, 19:47 6★likecs 3.7k●24●81 accept rate: 9%
 0 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 4★abbas 411●8 accept rate: 28%
 0 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 534●2●16 accept rate: 12%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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