Cod sursa(job #976214)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 22 iulie 2013 19:32:55
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include<stdio.h>
#include<stack>
using namespace std;
short int v[500004];
struct sp
{
    short int v;
    unsigned c,p;
};
stack<sp>a,b;
unsigned s[500004],s2[500004];
int main()
{
freopen("secventa.in","r",stdin);
freopen("secventa.out","w",stdout);
unsigned n,i,k,st,dr;
sp x;
short int m;
scanf("%u%u",&n,&k);
for(i=1;i<=n;i++)
{
    scanf("%hu",&v[i]);
    x.v=v[i];
    x.c=0;
    while(!a.empty())
    {
        if(v[i]>a.top().v)
            break;
            x.c=x.c+a.top().c+1;
        a.pop();
    }
    s[i]=x.c;
    a.push(x);
}
m=-30001;
for(i=n;i>=1;i--)
{
    x.v=v[i];
    x.c=0;
    while(!b.empty())
    {
        if(v[i]>b.top().v)
            break;
            x.c=x.c+b.top().c+1;
        b.pop();
    }
    s2[i]=x.c;
    if(s[i]+s2[i]+1>=k && v[i]>=m)
    {
        if(v[i]>m)
        {
            st=i-s[i];
            dr=i+s2[i];
            m=v[i];

        }
        else
            if(v[i]==m && (i-s[i]<st || (i-s[i]==st && i+s2[i]>dr)))
            {
               st=i-s[i];
            dr=i+s2[i];
            }
    }
    b.push(x);
}
printf("%u %u %u\n",st,dr,m);
    return 0;
}