Cod sursa(job #2129906)

Utilizator MoldovanAndrei1Moldovan Andrei MoldovanAndrei1 Data 13 februarie 2018 11:23:16
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <cstdio>
#include <stack>
using namespace std;
int v1[500005],v2[500005],v[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",&v[i]);
    stack<int>s;
    v[n+1]=-30001;
    s.push(n+1);
    for(i=n;i>=1;i--)
    {
        if(v[i]<v[s.top()])
        {
            s.pop();
            while(v[i]<v[s.top()])s.pop();
        }
            v2[i]=s.top();
            s.push(i);
    //printf("\n\n");
    }
    while(!s.empty())s.pop();
    v[0]=-30001;
    s.push(0);
    for(i=1;i<=n;i++)
    {
        while(v[i]<v[s.top()])
            s.pop();
        v1[i]=s.top();
        s.push(i);
    }
    int max1=0,st,dr;
    for(i=1;i<=n;i++)
    {
        if(v2[i]-v1[i]-1>=k)
        {
            if(v[i]>max1)
            {
                max1=v[i];
                st=v1[i]+1;
                dr=v2[i]+k;
            }
        }
    }
    printf("%d %d %d\n",st,dr,max1);
    return 0;
}