Cod sursa(job #271135)

Utilizator zbarniZajzon Barna zbarni Data 4 martie 2009 22:13:43
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.6 kb
#include<fstream.h>
#define nx 500005
int a[nx],deque[nx];

int main()
 {
  ifstream be ("secventa.in");
  ofstream ki ("secventa.out");
  int n,k,front,back,max=-30005,pos1,pos2,i;
  be>>n>>k;
  for (i=1;i<=n;++i)
    be>>a[i];
  be.close(); back=0,front=1;
  for (i=1;i<=n;++i)
   {
    while (front<=back && a[i]<a[deque[back]]) back--;
    deque[++back]=i;
    if (deque[front]==i-k) front++;
    if (i>=k && a[deque[front]]>max)
     {
      max=a[deque[front]];
      pos1=i-k+1;
      pos2=i;
     }
   }
  ki<<pos1<<" "<<pos1+k-1<<" "<<max<<'\n';
  ki.close();
  return 0;
 }