### dhiraj-01's blog

By dhiraj-01, 2 months ago,

n, q <= 5000
we can skip 2 painters, so just iterate through all pairs (i, j) ignore i and jtn painter, and maximize the answer.
time complexity: O(2 * n + q * q * 3)
space complexity: O(3 * n)

thank you.

update
AC https://codeforces.com/contest/1132/submission/124404923
creating a vector in each iteration cause TLE :(

how to avoid TLE
- check time complexity will fit in the problem
- C++ — use FAST IO, use '\n' instead of endl, use int (if needed)
- make sure your debug statement will not print anything on judge
- recursive dp sometime gives TLE, try iterative
- creating vector, vector.push_back() in nested loop is scary (check this comment for better understanding)

if (nothing works)

• +31

 » 2 months ago, # | ← Rev. 3 →   +3 Time complexity is more like O(n*n*q):For every i (n) take every j > i (/2) and connect q-2 segments () and check if its max.You see that you have 3 levels of "for" in your code, right?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +9 click hereprefix sum to calculate how many painter can paint on ith section first level (i) - q second level (j) - q now i am spliting (i, j) painters into 2 or 3 parts to calculate answer ex. case(1) 1 n - - - - - - - - - - - - - - - - - | | [l1 -- r1] => ith painter range [l2 -- r2] => jth painter range no need to split here [l1, r1] => count 1 in this range, remove it [l2, r2] => count 1 in this range, remove it case(2) 1 n - - - - - - - - - - - - - - - - - | | [l1 ------------- r1] => ith painter range [l2 -- r2] => jth painter range 1 n - - - - - - - - - - - - - - - - - | | [l1 ------------- r1] => ith painter range [l2 ------------- r2] => jth painter range split into 3 parts [l1, l2 - 1] => count 1 in this range, remove it [l2, min(r1, r2)] => count 2 in this range, remove it [min(r1, r2) + 1, max(r1, r2)] => count 1 in this range, remove it 
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +8 Ah, sorry, now I see what you did in third for-loop. Then question is — do you really need so many slow long longs?
•  » » » » 2 months ago, # ^ |   +3 I have changed long long int to int still TLE (check the code again)using ll = int;
 » 2 months ago, # | ← Rev. 3 →   +7 Going to help because it's a reasonably written blog.You're correct about the solution and time complexity, that's not the issue. It's the implementation, and more specifically working heavily with vectors within the inner loop. Not all operations are created equal, so $O(q^2)$ of straightforward arithmetic will pass easily, but $O(q^2)$ of allocating new vectors is much, much heavier in practice.I've done minimal changes to the code — in particular, I've made $b$ a fixed size and hence avoided allocating any memory within the loop. All the logic is the same but the speed increase is nearly 10x (at least locally for me). Here is your accepted code: AC. You can compare it to yours to see the exact changes.Edit: I see you've figured it out yourself. Good job.
•  » » 2 months ago, # ^ |   0 yes Enchom got it. thank you very much.
•  » » 2 months ago, # ^ | ← Rev. 5 →   0 But why isn't this lines are the same allocations?b[0] = {l1, l2 - 1, 1}; b[1] = {l2, min(r1, r2), 2}; b[2] = {min(r1, r2) + 1, max(r1, r2), 1};This got AC too, with almost the same time as your's. Thought b is still a vector >. I just thrown out .push_back()'s and written above code of your's. What is the difference?
•  » » » 2 months ago, # ^ | ← Rev. 3 →   +6 Whether it's statically allocated array, or a vector with fixed size, it doesn't matter. Both yours and mine are essentially the sameThe important thing is that the lines you mentioned are not allocations, but simple assignments. There is no memory allocation/deallocation happening in the background since the vector does not change its size.