Cod sursa(job #403639)

Utilizator jupanubv92Popescu Marius jupanubv92 Data 25 februarie 2010 09:51:50
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<stdio.h>
#include<deque>
#define Nmx 500002

using namespace std;

int n,k,a[Nmx];
deque <int> D;

void citire()
{
    int max=-5000213,pz,pzf,dm=100;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
    }
    for(int i=n;i>=1;--i)
    {
        while(D.size()>0&&D.back()>a[i])
            D.pop_back();
        D.push_back(a[i]);
        if(n-i+1>=k)
        {
            if(n-i+1>k)
                if(D.front()==a[i+k])
                    D.pop_front();
            if(max<D.front())
            {
                max=D.front();
                int j=i+k,dist=k;
                while(a[j]>max&&j<=n)
                    ++j,dist++;
                dm=dist;
                pz=i;
                pzf=j-1;
            }
            else if(max==D.front())
            {
                int j=i+k,dist=k;
                while(a[j]>max&&j<=n)
                    ++j,dist++;
                if(dm<dist)
                {
                    dm=dist;
                    pz=i;
                    pzf=j-1;
                }
            }
        }
    }
    printf("%d %d %d\n",pz,pzf,max);
}

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    citire();
    return 0;
}