Cod sursa(job #2046193)

Utilizator Radu_FilipescuFilipescu Radu Radu_Filipescu Data 23 octombrie 2017 15:54:09
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.81 kb
#include <fstream>
#include <deque>

using namespace std;

ifstream fin("secventa.in");
ofstream fout("secventa.out");

int n,k;
int a[500005];
int maxx;
int ssec,fsec;

deque <int> d;

void Read()
{
   fin>>n>>k;

   for(int i=1; i<=n; ++i)
      fin>>a[i];

   fin.close();
}

void Do()
{
  for(int i=1; i<=n; ++i)
  {
    while(!d.empty() && a[i]<=a[d.back()])
      d.pop_back();
    d.push_back(i);


    if(i-k==d.front()) d.pop_front();

    if(i>=k)
      if(a[d.front()]>maxx) { maxx=a[d.front()];
                              ssec=i-k+1;
                              fsec=i;
                            }
  }
}

void Print()
{
   fout<<ssec<<' '<<fsec<<' '<<maxx<<'\n';

   fout.close();
}

int main()
{
    Read();
    Do();
    Print();

    return 0;
}