Cod sursa(job #1429985)

Utilizator lraduRadu Lucut lradu Data 7 mai 2015 18:12:03
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.56 kb
#include <iostream>
#include <fstream>


using namespace std;
int n,k;
int first,mxm=-30001,last,le,ri;
int v[500001],deque[500001];

int main()
{

 ifstream f("secventa.in");
 ofstream g("secventa.out");

 f>>n>>k;
 for (int i=1; i<=n; i++) f>>v[i];

 le=1;
 ri=0;
 for(int i=1;i<=n;i++)
 {
  while(le<=ri && v[i]<=v[deque[ri]])
   --ri;

  deque[++ri]=i;

  if(deque[le]==i-k)
   ++le;

  if(i>=k)
   if(v[deque[le]]>mxm)
   {
    mxm=v[deque[le]];
    first=i-k+1;
    last=i;
   }
 }

 g<<first<<" "<<last<<" "<<mxm;

 return 0;
}