Cod sursa(job #132747)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 6 februarie 2008 16:05:13
Problema Secventa Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
// Problema 014.Secventa (infoarena). Varianta cu deque.
// Complexitate O(N)
#include <fstream.h>
int n, k, v[500000], deque[500000], qend, qbegin, min = -32000;

int main()
{
   ifstream in("secventa.in");
   ofstream out("secventa.out");

   int i, pi, pf;
   in>>n>>k;
   for (i = 1; i <= n; i++) in>>v[i];

   qbegin = 1;

   for (i = 1; i < k; i++)
   {
      qend++;
      while (qend > qbegin && v[i] <= v[deque[qend-1]]) qend--;
      deque[qend] = i;
   }

   for (i = k; i <= n; i++)
   {
      qend++;
      while (qend > qbegin && v[i] <= v[deque[qend-1]]) qend--;
      deque[qend] = i;

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

      if (v[deque[qbegin]] > min)
      {
	 min = v[deque[qbegin]];
	 pi = i - k + 1;
	 pf = i;
      }
   }
  out<<pi<<" "<<pf<<" "<<min;
   return 0;
}