D. Mike and Feet
Mike is the president of country What-The-Fatherland. There are n bears living in this country besides Mike. All of them are standing in a line and they are numbered from 1 to n from left to right. i-th bear is exactly ai feet high.
A group of bears is a non-empty contiguous segment of the line. The size of a group is the number of bears in that group. The strengthof a group is the minimum height of the bear in that group.
Mike is a curious to know for each x such that 1 ≤ x ≤ n the maximum strength among all groups of size x.
Input
The first line of input contains integer n (1 ≤ n ≤ 2 × 105), the number of bears.
The second line contains n integers separated by space, a1, a2, ..., an (1 ≤ ai ≤ 109), heights of bears.
Output
Print n integers in one line. For each x from 1 to n, print the maximum strength among all groups of size x.
Examples
input
10 1 2 3 4 5 4 3 2 1 6
output
6 4 4 3 3 2 2 1 1 1
For each i, find the largest j that aj < ai and show it by li (if there is no such j, then li = 0).
Also, find the smallest j that aj < ai and show it by ri (if there is no such j, then ri = n + 1).
This can be done in O(n) with a stack. Pseudo code of the first part (second part is also like that) :
stack s // initially empty
for i = 1 to n
while s is not empty and a[s.top()] >= a[i]
do s.pop()
if s is empty
then l[i] = 0
otherwise
l[i] = s.top()
s.push(i)
Consider that you are asked to print n integers, ans1, ans2, ..., ansn. Obviously, ans1 ≥ ans2 ≥ ... ≥ ansn.
For each i, we know that ai can be minimum element in groups of size 1, 2, ..., ri - li - 1.
Se we need a data structure for us to do this:
We have array ans1, ans2, ..., ansn and all its elements are initially equal to 0. Also, n queries. Each query gives x, val and want us to perform ans1 = max(ans1, val), ans2 = max(ans2, val), ..., ansx = max(ansx, val). We want the final array.
This can be done in O(n) with a maximum partial sum (keeping maximum instead of sum), read here for more information about partial sum.
Time complexity: 
=============================CODE==============================================
#include<bits/stdc++.h>
using namespace std;
typedef long long int lli;
stack<pair<lli,int> > s;
lli arr[1000000];
int fforward[1000000];
int bbackward[1000000];
vector<lli> ans;
vector<pair<int,lli> > span;
int main()
{
int n;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
for(int i=0;i<n;i++)
{
//cout<<" going to use "<<arr[i]<<endl;
if( s.empty() || s.top().first<=arr[i] )
{
// cout<<" push"<<endl;;
s.push({arr[i],i});
}
else
{
while(!s.empty() && s.top().first>arr[i])
{
fforward[s.top().second]=(i-s.top().second);
// cout<<"pop "<<s.top().first<<" "<<" ans is "<<fforward[s.top().second]<<endl;
s.pop();
}
s.push({arr[i],i});
}
}
while(!s.empty())
{
fforward[s.top().second]=(n-s.top().second);
s.pop();
}
/*for(int i=0;i<n;i++) cout<<fforward[i]<<" ";
cout<<endl;*/
for(int i=n-1;i>=0;i--)
{
//cout<<" going to use "<<arr[i]<<endl;
if( s.empty() || s.top().first<=arr[i] )
{
// cout<<" push"<<endl;;
s.push({arr[i],i});
}
else
{
while(!s.empty() && s.top().first>arr[i])
{
bbackward[s.top().second]=(s.top().second-i);
// cout<<"pop "<<s.top().first<<" "<<" ans is "<<fforward[s.top().second]<<endl;
s.pop();
}
s.push({arr[i],i});
}
}
while(!s.empty())
{
bbackward[s.top().second]=(s.top().second+1);
s.pop();
}
for(int i=0;i<n;i++)
{
span.push_back({fforward[i]+bbackward[i]-1,arr[i]});
// cumulated[i]=fforward[i]+bbackward[i]-1;
}
// for(int i=0;i<n;i++)cout<<cumulated[i]<<" ";
//cout<<endl;
sort(span.begin(),span.end());
int start=n-1;
set<lli> sset;
for(int sp=n;sp>=1;sp--)
{
while(start>=0 && span[start].first>=sp)
{
sset.insert(span[start].second);
start--;
}
ans.push_back(*sset.rbegin());
}
for(int i=n-1;i>=0;i--) cout<<ans[i]<<" ";
}
No comments:
Post a Comment