Cod sursa(job #110726)

Utilizator marinMari n marin Data 27 noiembrie 2007 17:21:17
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.82 kb
#include<stdio.h>

#define MAX 1000
#define MAX_VALUE 5001;

long int x,y,z,n,k,i,j,s,m,pdoi,pa,pb,iMax, jMax;
long int v[MAX];


//void pune()

long int getPoz(long int i){
  return pdoi+i;
}

void set(long int i, long int x){
  while (i!=0) {
    if (v[i]>x) {
      v[i]=x;
    }
    i=i/2;
  }
}


long int get(long int a, long int b){
  long int rez = MAX_VALUE;
  if (rez>v[a]) rez = v[a];
  if (rez>v[b]) rez = v[b];
  while (a!=b) {
//    pa=a/2;
//    pb=b/2;
//    if (a==2*pa+1) s+=v[a-1];
//    if (b==2*pb) s+=v[b+1];
//    a=pa;
//    b=pb;
    pa=a/2;
    pb=b/2;

    if (a==2*pa) {
      if ((v[pa]<v[a]) && (v[pa]<rez))
	rez=v[pa];
    }
    if (b==2*pb+1){
      if ((v[pb]<v[b]) && (v[pb]<rez))
	rez=v[pb];
    }

    if (pa==pb) break;
/*    if (a==2*pa) {
      if (rez>v[2*pa+1]) rez=v[2*pa+1];
    } else {
      if (rez>v[a]) rez=v[a];
    }

    if (b==2*pb+1){
      if (rez>v[2*pb]) rez=v[2*pb];
    } else {
      if (rez>v[b]) rez=v[b];
    }*/

    a=pa;
    b=pb;


  }
  return rez;
}


int main(){
  FILE *f = fopen("secventa.in","r");

  FILE *g = fopen("secventa.out","w");

  fscanf(f,"%ld %ld",&n, &k);
  m=n;x=0;
  while (m!=0) {
    x++;
    m/=2;
  }
  pdoi = (1<<(x))-1;


  m=n;
  while (m%2==0) {
    m/=2;
  }
  if (m==1) {
    pdoi = pdoi/2;
  }


  for (i=1;i<2*pdoi+2;i++) {
    v[i]=MAX_VALUE;
  }


  for (i=1;i<=n;i++){
    fscanf(f,"%ld",&x);
    set(getPoz(i),x);
  }

  long int bMax = -MAX_VALUE;

  for (i=1;i<=n-k+1;i++) {
    long int st = getPoz(i);
    long int dr = getPoz(i+k-1);
    long int temp = get(st, dr);

    if (temp>bMax) {
      bMax = temp;
      iMax = i;
      jMax = i+k-1;
    }
  }

  fprintf(g,"%ld %ld %ld",iMax, jMax, bMax);
  fclose(f);
  fclose(g);
  return 0;
}