HackerEarth Challenge-- Deepu and Array

Question

[ The Challenge is Over ]

Problem:

An Array of positive elements. Deepu Wants to reduce the elements of the array. He calls a function Hit(X) which reduces the all the elements in the array which are greater than X by 1.

he will call this array many times . Print the array after many calls to Hit(X).

Input:

n----- no of elements in array 10^5.

n elements ----- 1<=element<=10^9.

x----- no of calls to Hit(X) x elements----- 1<=element<=10^9.

output:

Print The array after call to Hit(X) x times.

Time limit--5 secs.

My solution gave Time Limit Exceeded.

My approach:

1. keep an Original Array
2. Create a vector of pairs of array elements and their index in the array Sort the vector elements [ ascending ].
3. Do LowerBound() of C++ STL to get the position of element in the vector where elements are equal to give element x.
4. From this element decrease the elements which are greater than x by 1 till end in the original array from the index in the pair.
5. Repeat step 3 & 4 for every x.
6. Print the Original array.

I think my solution has complexity n^2.

Can someone Give me an Optimized solution

Thanks

My Code

    #define _CRT_DISABLE_PERFCRIT_LOCKS

    // lower_bound/upper_bound example
    #include <iostream>     // std::cout
    #include <algorithm>    // std::lower_bound, std::upper_bound, std::sort
    #include <vector>       // std::vector
    #include <utility>

    using namespace std;


    bool pairCompare(const std::pair<long long int, unsigned int>& firstElem, const std::pair<long long int, unsigned int>& secondElem) {
        return firstElem.first < secondElem.first;

    }

    int main() {

        ios_base::sync_with_stdio(false);
        cin.tie(NULL);

        unsigned int n, m;

        long long int arr[100000], x,temp;

        vector<pair<long long int, unsigned int> > vect(100000);

        cin >> n;

        for (unsigned int i = 0; i < n; i++)
        {
            cin >> temp;
            arr[i] = temp;

            vect[i].first = temp;
            vect[i].second = i;
        }

        sort(vect.begin(), vect.begin() + n, pairCompare);


        cin >> m;

        vector<pair<long long int, unsigned int> >::iterator low;



        while (m--)
        {
                    cin >> x;



            low = lower_bound(vect.begin(), vect.begin() + n, make_pair(x,2), pairCompare);

            if (low != vect.begin() + n)
            {

                    for (unsigned int i = low - vect.begin(); i < n; i++)
                    {

                        if (vect[i].first != x)
                        {
                            vect[i].first -= 1;

                            arr[vect[i].second] -= 1;
                        }
                    }
            }




        }


        for (unsigned int i = 0; i < n; i++)
        {

            cout << arr[i]<<" ";
        }


        return 0;
    }

Answer 1

First sort the input array in non-decreasing order. The input array will remain sorted after each of the update operations is run because we are looking for elements greater than x and decrementing them so the worst that could happen is that some elements become equal to x after the operation: array is still sorted.

You can update a range quickly by using a lazy segment tree update. You have to remember the original positions so that you can print the array at the end.