PoisonousPython's blog

I need some help with this problem...
By PoisonousPython, history, 8 years ago, In English

Hi! First off, I just wanted to ask if this problem is solvable using segment trees: http://mirror.codeforces.com/problemset/problem/52/C

I wrote a solution which uses segment trees but it gives me TLE on test 8. Can you please give me a hint at least? That would be quite helpful.

Here is the code: http://mirror.codeforces.com/contest/52/submission/24460216 Thanks!

  • Vote: I like it
  • +1
  • Vote: I do not like it

Comments Comments (2)
| Write comment?
»
8 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Yes it is, however it appears you are using them quite ineffectively. Judging by the following lines in your code it seems that for each inc function you are updating each element in the segment separately:

            if(ct[0]>ct[1]){
                for(ll j=ct[0]; j<n; j++)A[j]+=ct[2];
                update(0, n-1, ct[0], n-1, 0);
                for(ll j=0; j<=ct[1]; j++)A[j]+=ct[2];
                update(0, n-1, 0, ct[1], 0);
            }else{
                for(ll j=ct[0]; j<=ct[1]; j++)A[j]+=ct[2];
                update(0, n-1, ct[0], ct[1], 0);
            }

This is quite ineffective, if there were for example 200000 queries that update the whole array, your code will have running time . One possible way of improving time is a technique called lazy propagation, which lets you update any segment in time, bringing the overall complexity down to , which will pass.

→ Reply
»
8 years ago, # |
← Rev. 21   Vote: I like it 0 Vote: I do not like it

segment tree has implementation your case: increment interval and query maximum (it's easy to convert query minimum).

Or see my submission

→ Reply