Cod sursa(job #916043)

Utilizator dariusdariusMarian Darius dariusdarius Data 15 martie 2013 19:04:23
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include<stdio.h>
#include<stack>
using namespace std;
stack<int> stk;
int st[500005];
int dr[500005];
int  a[500005];
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int n,k,i;
    scanf("%d%d",&n,&k);
    for(i=1;i<=n;i++)
        scanf("%d",&a[i]);
    stk.push(0);
    for(i=1;i<=n;i++)
    {
        while(stk.size()>1 && a[stk.top()]>=a[i])
            stk.pop();
        st[i]=stk.top()+1;
        stk.push(i);
    }
    while(!stk.empty()) stk.pop();
    stk.push(n+1);
    for(i=n;i>=1;i--)
    {
        while(stk.size()>1 && a[stk.top()]>=a[i])
            stk.pop();
        dr[i]=stk.top()-1;
        stk.push(i);
    }
    int sol=-30001,start,finish;
    for(i=1;i<=n;i++)
        if(dr[i]-st[i]+1>=k && sol<a[i])
        {
            sol=a[i];
            start=st[i];
            finish=dr[i];
        }
    printf("%d %d %d\n",start,finish,sol);
    return 0;
}