Recent CP News

Signal Range || Let’s Place towers in a well way

Signal Range – Let’s do it guys it’s easy

Various signal range towers are present in a city.Towers are aligned in a straight horizontal line(from left to right) and each tower transmits a signal in the right to left direction.Tower A shall block the signal of Tower B if Tower A is present to the left of Tower B and Tower A is taller than Tower B. So, the range of a signal of a given tower can be defined as :

{(the number of contiguous towers just to the left of the given tower whose height is less than or equal to the height of the given tower) + 1}.

You need to find the range of each tower.

INPUT

The first line contains an integer T specifying the number of test cases.

The second line contains an integer n specifying the number of towers.

The third line contains n space separated integers(H[i]) denoting the height of each tower.

OUTPUT

Print the range of each tower (separated by a space).

Constraints

1 <= T <= 10

2 <= n <= 10^6

1 <= H[i] <= 10^8

SAMPLE INPUT

1
7
100 80 60 70 60 75 85

SAMPLE OUTPUT

1 1 1 2 1 4 6

Explanation

The 6th tower has a range 4 because there are 3 contiguous towers(3rd 4th and 5th towers) just to the left of the 6th tower whose height is less than the height of the 6th tower.

Solution with Explanation

#include <iostream>
#include<algorithm>
#include<stack>
#include <stdio.h>
#include <math.h>
#include <fstream>

using namespace std;
int ar[1000000];
int main()
{

       int n;
       cin>>n;
       while(n!=0)
       {

           int l;

           cin>>l;
                 for(int i=0;i<l;i++)
           {  
               cin>>ar[i];     //array to store heights of towers
           }
           int* span=new int[l];  //array to store the answer
           std::stack<int> st;   //stack to store INDICES of array "ar"
           span[0]=1;                
           st.push(0);
           for(int i=1;i<l;i++)
           {
               while(!st.empty()&&ar[st.top()]<=ar[i])
               {
                   st.pop();                    //pop elements in stack while its non empty and the current height is greater than the height stored at the top of the stack
               }
               if(st.empty())
                   span[i]=i+1;           //when all elements are popped ,span is simply index+1
               else
                   span[i]=i-st.top();    //span is the difference of indices 
               st.push(i);
           }

       for(int i=0;i<l;i++)
       {

           cout<<span[i]<<" ";    //print the answer
       }
           cout<<"\n";
           n--;
       }

Refer this linkĀ http://www.geeksforgeeks.org/the-stock-span-problem/

to get an idea about efficient solving techniques.

Source-HackerEarth

{Code With Code@ter}

Give Your Reviews




Leave a Reply