Cod sursa(job #112660)

Utilizator mgntMarius B mgnt Data 6 decembrie 2007 14:48:57
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.28 kb
#include <cstdio>
#include <cstdlib>
#include <memory>
using namespace std;

int const minval = -30000;
int const maxval = +30000;
int const maxlen = 500000;
int a[maxlen];
int val_c[1+maxlen], * val_v=& val_c[1];
int pos_c[1+maxlen], * pos_v=& pos_c[1];
int c_c[maxval-minval+1];
int *c= &c_c[-minval];

char iobuf[BUFSIZ];
char line [10240];

int
main() {
  register int i, j, t, n, k, pos, val, q1, q2;

  FILE * fin;
  fin=fopen("secventa.in","r");
  setbuf(fin, iobuf);
  fscanf(fin, "%d %d\n", &n, &k);
  
  for(i=0;i<n;i++) fscanf(fin, "%d", &a[i]);

  fclose(fin);
  
  for(i=minval;i<=maxval;i++) c[i]=-1;
  for(i=0;i<k;i++) c[a[i]]=i;
  for(i=minval, j=0; i<=maxval; i++)
    if(-1!=c[i]) {
      val_v[j]=i;
      pos_v[j]=c[i];
      ++j;
    }
  
  pos=0;
  val=val_v[0];
  q1=0;
  q2=-1+j;
  pos_v[-1]=-1;
  val_v[-1]=-1+minval;
  for(i=k;i<n;i++) {

    t=a[i];
    while(val_v[q2]>=t) --q2;
    ++q2;
    val_v[q2]=t;
    pos_v[q2]=i;

     if(i-k>=pos_v[q1])
    {
      val_v[q1]=-1+minval;
      ++q1;
    }
    
    if(val<val_v[q1]) {
      val=val_v[q1];
      pos=i-k+1;
    }
  }

  FILE * fout;
  fout=fopen("secventa.out", "w");
  fprintf (fout, "%d %d %d\n", 1+pos, pos+k, val);
  fclose(fout);
  return 0;
}