Cod sursa(job #2161939)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 11 martie 2018 22:09:17
Problema Secventa Scor 10
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.27 kb
#include <fstream>
#include <deque>
#include <climits>
#include <iostream>
#include <cstring>
using namespace std;
ifstream f("secventa.in");
ofstream g("secventa.out");

deque <int> d;
int n,k,i,maxim=INT_MIN,semn,nr,poz,v[50001];
char s[50001];
int main()
{
    f>>n>>k;
    char c=f.get();
    f.getline(s,500100);

    int j=0;
    semn=1;
    for(i=0;i<=strlen(s)-1;i++)
    {


      if(s[i]=='-')semn=-1;
      else if('0'<=s[i]&&s[i]<='9')
      {
          nr=0;
          while('0'<=s[i]&&s[i]<='9')
            {nr=nr*10+(s[i]-'0');i++;}

        j++;v[j]=nr*semn;
        semn=1;
      }



    }



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

        while(d.size()>=1&&v[d.front()]>=v[i])
        {
            d.pop_front();
        }

        d.push_front(i);
    }

    if(v[d.back()]>maxim)
    {
        maxim=v[d.back()];
        poz=k;
    }


    for(i=k+1; i<=n; i++)
    {
        while(d.size()>=1&&d.back()<=i-k)d.pop_back();
        while(d.size()>=1&&v[d.front()]>=v[i])
        {
            d.pop_front();
        }
        d.push_front(i);

        if(v[d.back()]>maxim)
        {
            maxim=v[d.back()];
            poz=i;
        }
    }

    g<<poz-k+1<<" "<<poz<<" "<<maxim;

    return 0;
}