Weirdfn : tle

[zukow_sof]

I don't understand how your heap is working, are you sure it is always balanced? Anyway, I got AC when using prioryty queues from stl.

[gooey_kablooie_sof]

I don't think your heaps are balanced as zukow suspected. The number of elements in the heaps should differ atmost by 1. And don't use the % operator heavily. The expression :

val = (((a*hleft[0])%mod + (b*(i+1))%mod + c%mod))%mod;

is equal to this :

val = (a*hleft[0] + b * (i + 1) + c) % mod;

if a, b and c are int64 types.

[anuragmsingh]

Thanku ACed..!!

[zukow_sof]

Your queues use seems to be valid. Interesting way to avoid changing comparison operator btw. I assume that you tested it!

The problem is that your code will often overflow, mainly here on multiplication:

x=((a*median)%MOD+b*i+c)%MOD;

To avoid problems, just use long long everywhere.

[kapil_bajaj_sof]

I am also getting TLE. I have used two heaps min and max. Earlier I was using STL's priority queue but it timed out so I created own heap but again timing out. Can some please point what could be the case taking most time. Here is the code:

AC

[vishwakarmav]

stl priority_queue wont time out.
I got AC in 5.15sec with stl only.

[vishwakarmav]

Hint : use mod operation only where it is necessary and heap of (long int ) is sufficient for this problem

[kapil_bajaj_sof]

Thank you. It got accepted.

[lollypop_sof]

I used two STL priority_queue (for left tree and right tree) and optimized my I/O, but still got TLE. How did this happen?

[kartikaditya]

I get WA for this code after 5 secs. What could be wrong with it?
Can anyone suggest a input for which this fails.

-Thanks

Edited with latest code and still WA after 5.01 secs

[bbone=c,324]
/**
* AC! Hence removed code
*/
[/bbone]

[fitcat]

There is a little bug in placing f into the queues. Try this:

1
1000000006 1000000006 1000000006 4

[kartikaditya]

Very nice catch! Thanks a lot for the input provided
Got AC in 5.02 secs.

[schrodinger]

I'm getting TLE for this code. What optimizations are needed to get AC. I'm using max priority queue for the left half and min priority queue for right half. median would be the top of max queue.

#include <iostream>
#include <queue>
using namespace std;
#define MOD 1000000007
typedef unsigned long long lng;
int main()
{
    //freopen("in","r",stdin);
    int a, b, c, n;
    int  t;
    cin >> t;
    for (int I=1; I<= t; I++ )
    {
        priority_queue<int> maxpq;
        priority_queue<int, vector<int>, greater<int> > minpq;
        cin >> a >> b >> c >> n;
        lng sum = 1LL;
        maxpq.push(1);
        for (int J=2; J<=n;J++)
        {
            lng top = lng (maxpq.top());
            lng tempsum = ((lng(a)*lng(maxpq.top()))%MOD + (lng(b)*lng(J))%MOD + lng(c))%MOD;
            sum += tempsum;
            int tmp = int(tempsum);
            if (J&1)
        {
            if (tmp > minpq.top())
            {
                int move = minpq.top();
                minpq.pop();
                maxpq.push(move);
                minpq.push(tmp);
            }
            else maxpq.push(tmp);
        }
        else
        {
            if (tmp > maxpq.top())
                minpq.push(tmp);
            else
            {
                int move = maxpq.top();
                maxpq.pop();
                minpq.push(move);
                maxpq.push(tmp);
            }
        }

    }
    cout << sum << endl;
}
return 0;
}

[leppyr64]

Don't use cin/cout.
Avoid casting datatypes.

[leppyr64]

Why not just make everything in those calculations lng?

[schrodinger]

I've replace cin/cout to scanf/printf and changed this line to

int tempsum = ((lng(a)*lng(maxpq.top()))%MOD + (lng(b)*lng(J))%MOD + c)%MOD;

but it's still TLE. What else I could do to optimize in this line or code?

[schrodinger]

I thought making all calculations lng would be more time consuming than to use type casting in just single line. Is it a wrong assumption?

@leppy: Now I've made all calculations lng but it's still TLE

[leppyr64]

If you have to make the calculation with long, then storing it as long is more efficient. Every time you typecast you program has to allocate memory for a new variable, initialize it, then perform the calculation.

[leppyr64]

When you edit posts I don't receive notification that you have changed something.

Limit your usage of %

[schrodinger]

@leppy: thanks. got AC
changes I've made:

lng tempsum = ((a*maxpq.top()) + (b*J) + c)%MOD;

TLE was because of unnecessary use of MOD.