Cod sursa(job #2161958)

Utilizator AndreiD31Dragan Andrei AndreiD31 Data 11 martie 2018 22:15:58
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 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,j,semn,nr,poz,v[500005];
char s[5*500005];
int main()
{
    f>>n>>k;
    char c=f.get();
    f.getline(s,sizeof(s));


   j=0;semn=1;
   for(i=1;i<=n;i++)
   {
        if(s[j]=='-'){semn=-1;j++;}
        while('0'<=s[j]&&s[j]<='9'){v[i]=v[i]*10+(s[j]-'0');j++;}
        v[i]=v[i]*semn;
         semn=1;
        j++;

   }



    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;
}