How do I deal with large arrays in c++/STL?

Question

I am trying to solve this problem arraysub on spoj. I have coded it using a sliding window concept and I am using a max-heap to store the elements of the current window. The problem constraints are of the order 10^5 and I am getting SIGABRT error for my submission. I've read on wiki that this error results if there's a memory leak or problem initialising large arrays. How do I deal with this? long long, long long int, long long unsigned int, doesn't seem to work. Please help. Below is my code:

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<long, long> Pair;
long  *a = new long[1000001], *output = new long[1000001];
long n, k;

void slidingWindowMax()
{
    priority_queue<Pair> Q;
    for(int i=0;i<k; i++)
        Q.push(Pair(a[i], i));

    for(int i=k; i<n; i++)
    {
        Pair p = Q.top();
        output[i-k] = p.first;

        while(p.second <= i-k)
        {
            Q.pop();
            p = Q.top();
        }

        Q.push(Pair(a[i], i));
    }
    output[n-k] = Q.top().first;

    for(int i=0;i<(n-k+1);i++)
    {
        cout << output[i] << " ";
    }
}



int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
        cin >> a[i];
    cin >> k;

    slidingWindowMax();
    return 0;
}

Did you try deleting the memory you allocated in the beginning of the program? Like `delete [] a` Or why not simply try `long int a[100001]` — user007, Jul 19 '15 at 16:34
Moreover your question says that the problem constraint is `10^5` and in your question you allocate `a[1000001]` that is `10^6` a typo perhaps! Just telling :P — user007, Jul 19 '15 at 16:40
You should provide some example input to reproduce the problem. I just played around with it and made the `while` loop infinite by doing so, but who knows if this is the real problem? — Christian Hackl, Jul 19 '15 at 16:47
@user007 Damn that was a typo. You got it right! However, I am getting a time limit exceeded now. I must think of some better approach. If you can help me? — Abhishek Kusnoor, Jul 19 '15 at 16:48
The size seems far away from maximum of size_t, the maximum number of elements the standars allows for any array. — Christophe, Jul 19 '15 at 17:32
It seems the code is not correct if you want to remove first element of the sub-array toward the end of each loop iteration. I think STL heap of pairs might not be suitable. If you maintain a self-balanced binary search tree of appearing values along with their counts in the current subarray, then when you move to the next subarray you remove one occurrence of the beginning value of the previous subarray (deleting the node if the count becomes 0), and then insert the next end value into the tree (adding to the count if the value already exists, otherwise create a node). — user2566092, Jul 19 '15 at 19:00
Yes! Check this http://ideone.com/vTdWDs I added a print statement in your while loop, and you can see not much gets printed! I assume that you try to pop out the left most element from the queue! That doesn't actually happen! I would have rather implemented my own priority queue, and I would have kept track of the position at which the element is located and then call `heapify` on my priorityqueue! The would have taken O(nlogk) time and I think there would be no TLE either then! — user007, Jul 19 '15 at 19:18
And you might want to check this as well, if you cannot move any further http://stackoverflow.com/questions/8031939/finding-maximum-for-every-window-of-size-k-in-an-array — user007, Jul 19 '15 at 19:19
@user007 The link helped! I am certainly tracking the index of the deleted element by using an STL Pair. I will try out implementing my own priority queue though. There is a very good dp implementation in the link you provided. Many thanks! — Abhishek Kusnoor, Jul 20 '15 at 14:41

How do I deal with large arrays in c++/STL?

0 Answers0