Cod sursa(job #1997641)

Utilizator NToniBoSSNicolae Tonitza NToniBoSS Data 4 iulie 2017 23:25:31
Problema Secventa Scor 10
Compilator c Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
int v[500001],st[500001],dr[500001],s[500001];
int G()
{
    int nr=0,semn=1;
    char c=getchar();
    while(!isdigit(c) && c!='-')
        c=getchar();
    if(c=='-')
    {
        semn=-1;
        c=getchar();
    }
    while(isdigit(c))
    {
        nr=nr*10+c-'0';
        c=getchar();
    }
    return nr*semn;
}
int main()
{
    int n,k,i,u,max,a,b;
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(i=1; i<=n; i++)
        v[i]=G();
    u=0;
    for(i=1; i<=n; i++)
    {
        while(u>0 && v[s[u]]>v[i])
            dr[s[u]]=i,u--;
        s[++u]=i;
    }
    while(u>0)
        dr[s[u--]]=n+1;
    u=0;
    for(i=n; i>0; i--)
    {
        while(u>0 && v[s[u]]>v[i])
            st[s[u]]=i,u--;
        s[++u]=i;
    }
    max=-30001;
    a=n+1;
    b=n+1;
    for(i=1; i<=n; i++)
    {
        if(dr[i]-st[i]>k)
            if(v[i]>max)
            {
                max=v[i];
                a=st[i];
                b=dr[i];
            }
            else
            {
                if(v[i]==max)
                    if(a>st[i])
                    {
                        a=st[i];
                        b=dr[i];
                    }
                    else
                    {
                        if(a==st[i])
                            if(b>dr[i])
                                b=dr[i];
                    }
            }
    }
    printf("%d %d %d\n",a+1,b-1,max);

    return 0;
}