Pagini recente » Cod sursa (job #3029992) | Cod sursa (job #1158412) | Cod sursa (job #3185329) | Cod sursa (job #2963062) | Cod sursa (job #2676281)
#include <fstream>
#include <stack>
using namespace std;
stack <int> st;
const int NMAX = 500005;
int v[NMAX], L[NMAX], R[NMAX];
int main()
{
ifstream cin("secventa.in");
ofstream cout("secventa.out");
int n, k, maxx = 0, sum, stanga = 0, dreapta = 0;
cin >> n >> k;
for(int i = 1; i <= n; i ++)
{
cin >> v[i];
}
v[0] = v[n + 1] = -1e7;
st.push(0);
for(int i = 1; i <= n; i ++)
{
while(!st.empty() && v[i] < v[st.top()])
{
st.pop();
}
L[i] = st.top();
st.push(i);
}
while(!st.empty())
{
st.pop();
}
st.push(n + 1);
for(int i = n; i >= 1; i --)
{
while(!st.empty() && v[i] < v[st.top()])
{
st.pop();
}
R[i] = st.top();
st.push(i);
}
for(int i = 1; i <= n; i ++)
{
sum = R[i] - L[i] - 1;
if(sum >= k)
{
if(v[i] == maxx)
{
if(L[i] < stanga)
{
maxx = v[i];
stanga = L[i] + 1;
dreapta = R[i] - 1;
}
else if(L[i] == stanga)
{
if(R[i] < dreapta)
{
maxx = v[i];
stanga = L[i] + 1;
dreapta = R[i] - 1;
}
}
}
if(v[i] > maxx)
{
maxx = v[i];
stanga = L[i] + 1;
dreapta = R[i] - 1;
}
}
}
cout << stanga << " " << dreapta << " " << maxx;
return 0;
}