Блог пользователя PoisonousPython

I need some help with this problem...
Автор PoisonousPython, история, 8 лет назад, По-английски

Hi! First off, I just wanted to ask if this problem is solvable using segment trees: http://codeforces.me/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://codeforces.me/contest/52/submission/24460216 Thanks!

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

→ Ответить
»
8 лет назад, # |
← Rev. 21   Проголосовать: нравится 0 Проголосовать: не нравится

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

Or see my submission

→ Ответить