Cod sursa(job #979332)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 1 august 2013 11:47:17
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.24 kb
#include<stdio.h>
#include<deque>
#include<string.h>
#include<ctype.h>
using namespace std;
short int v[500002];
deque<unsigned>d;
char s[3500005];
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out", "w", stdout);
    unsigned n,k,p,i,l,w=1;
    short int m;
    bool t;
    scanf("%u%u\n",&n,&k);
    gets(s);
    l=strlen(s);
    t=0;
    for(i=0;i<l;i++)
    {
        if(s[i]=='-')
        {
            t=1;
        }
        else
        if(s[i]>='0' && s[i]<='9')
        {
            v[w]=v[w]*10+s[i]-48;
        }
        else
        {
            if(t)
            {
                t=0;
                v[w]=v[w]*-1;
            }
            w++;
        }

    }
    for(i=1;i<=k;i++)
    {
        while(!d.empty() && v[d.back()]>v[i])
            d.pop_back();
        d.push_back(i);
    }
    m=v[d.front()];
    p=k;
    for(i=k+1;i<=n;i++)
        {
        while(!d.empty() && v[d.back()]>v[i])
            d.pop_back();
        d.push_back(i);
        if(d.front()<=i-k)
            d.pop_front();
        if(v[d.front()]>m)
        {
            m=v[d.front()];
            p=i;
        }
    }
    printf("%u %u %hd\n",p-k+1,p,m);
    return 0;
}