Cod sursa(job #1714974)

Utilizator TibiraducanuTiberiu Raducanu Tibiraducanu Data 9 iunie 2016 20:19:00
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include <cstdio>
#include <deque>
#include <cstring>

using namespace std;

deque <int> q;

char s[5000005];
int v[500005];

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

    int n,k,i=0,maxx=-3000000,sf,nr,cnt=0,t;
    bool sem;

    scanf("%d%d\n",&n,&k);

    gets(s);
    t=strlen(s);

    i=0;

    while(i<t)
    {
        sem=0;

        while(s[i]<'0' || s[i]>'9')
        {
            if(s[i]=='-') sem=1;
            i++;
        }

        nr=0;
        while(s[i]>='0' and s[i]<='9')
        {
            nr=nr*10+(s[i]-'0');
            i++;
        }

        if(sem==1) nr*=-1;
        cnt++;
        v[cnt]=nr;
    }

    //for(i=1;i<=n;i++) printf("%d ",v[i]);
    //printf("\n");

    for(i=1;i<=n;i++)
    {

        while(!q.empty())
        {
            if(v[q.back()] >= v[i] ) q.pop_back();
            else break;
        }
        q.push_back(i);

        while(q.front() < i-k+1) q.pop_front();

        if(i>=k and v[q.front()]>maxx)
        {
            maxx=v[q.front()];
            sf=i;
        }
    }

    printf("%d %d %d\n",sf-k+1,sf,maxx);

    return 0;
}