Cod sursa(job #139760)

Utilizator ConsstantinTabacu Raul Consstantin Data 20 februarie 2008 16:59:51
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.91 kb
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define nmax 5000004

int N, K, i, A[nmax], bottom, top, ult, V[nmax], P[nmax], max, aaa, bbb, l, nr=1;

char S[nmax<<3];

 int main(){
     max = -200;
     freopen("secventa.in", "r", stdin);
     freopen("secventa.out", "w", stdout);
     scanf("%d %d\n", &N, &K);
     gets(S);
     A[1] = atoi(strtok(S, " \n"));
     for (i = 2; i <= N; i++)
	  A[i] = atoi(strtok(NULL, " \n"));
      for (i = 1, bottom = 0, top = -1, ult = 0; i <= N - K + 1; i++){
	  while (ult < i + K - 1 && ult < N) {
	      ult++;
	      while (top >= bottom && V[top] >= A[ult])
		  top--;
	      top++;
	      V[top] = A[ult];
	      P[top] = ult;
	  }
	  while (P[bottom] < i)
	      bottom++;
	  if (V[bottom] > max){
	      max = V[bottom];
	      aaa = i;
	      bbb = i+K-1;
	  }
      }
      printf("%d %d %d\n", aaa, bbb, max);
      return 0;
  }