Cod sursa(job #132739)

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

int main()
{
   freopen("secventa.in","r",stdin);
   freopen("secventa.out","w",stdout);

   int i, pi, pf;
   scanf("%d %d", &n, &k);
   for (i = 1; i <= n; i++) scanf("%d",v+i);

   qbegin = 1;

   for (i = 1; 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;
      }
   }
   printf("%d %d %d\n", pi, pf, min);
   return 0;
}