Cod sursa(job #1507492)

Utilizator LucianTLucian Trepteanu LucianT Data 21 octombrie 2015 18:13:54
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.95 kb
#include <cstdio>
#include <algorithm>
#include <deque>
#include <climits>
#include <cstring>
#define maxN 500005
using namespace std;
deque <int> q;
int p,n,k,i,maxx=-INT_MAX,v[maxN];
char s[8*maxN];
int pr,ul;
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d\n",&n,&k);
    p=1;
    gets(s+1);
    n=strlen(s+1);
    while(p<=n)
    {
        i++;
        int semn=1;
        if(s[p]=='-')
            semn*=(-1),p++;
        v[i]=0;
        //parsare
        while(s[p]<='9' && s[p]>='0')
            v[i]=v[i]*10+s[p]-'0',p++;
        v[i]=v[i]*semn;
        while(!q.empty() && v[i]<v[q.back()])
            q.pop_back();
        q.push_back(i);
        if(i>=k && maxx<v[q.front()])
            maxx=v[q.front()],pr=i+1-k,ul=i;
        if(q.size() && q.front()==i+1-k)
            q.pop_front();
        p++;
    }
    printf("%d %d %d",pr,ul,maxx);
    return 0;
}