Cod sursa(job #1643460)

Utilizator trutruvasilicaHuhurez Marius trutruvasilica Data 9 martie 2016 18:55:44
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.08 kb
#include <cstdio>
#include <deque>
using namespace std;
deque<int>Q;
int v[500001];
char buff[2000001];
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    int n,i,k,maxi=-300000,in=0,sf=0,ok,j=0;
    scanf("%d %d\n",&n,&k);
    fgets(buff,2000001,stdin);
    for(i=1;i<=n;++i)
    {
        ok=0;
        if(buff[j]==' ') j++;
        if(buff[j]=='-')
        {
            ok=1;
            j++;
        }
        while(buff[j]>='0'&&buff[j]<='9')
        {
            v[i]=v[i]*10+buff[j]-'0';
            j++;
        }
        if(ok==1) v[i]=-v[i];
        while(Q.size())
        {
            if(Q.front()<i-k+1) Q.pop_front();
            else break;
        }
        while(Q.size())
        {
          if(v[i]<v[Q.back()]) Q.pop_back();
          else break;
        }
        Q.push_back(i);
        if(i>=k&&v[Q.front()]>maxi)
        {
            in=i-k+1;
            sf=i;
            maxi=v[Q.front()];
        }
    }
    printf("%d %d %d",in,sf,maxi);
    //fout<<in<<" "<<sf<<" "<<maxi;
}