Cod sursa(job #72344)

Utilizator info_arrandrei gigea info_arr Data 13 iulie 2007 15:10:17
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb

#include <cstdio>
#include <fstream>

using namespace std;

#define MAX_N 100005
#define INF 0x3f3f3f3

int a[MAX_N]; 
int arb[MAX_N<<1];
int N,K,i,A,B;
int ANSWER;
int in,out,KBAS;

int MIN (int a, int b)
{
    if (a<b) return a; else return b;
}

void buildtree (int ind, int li, int lf)
{
  int mj;
  if (li==lf) arb[ind]=a[li];
  else
   {
      mj=(li+lf)>>1;
      buildtree(ind*2,li,mj);
      buildtree(ind*2+1,mj+1,lf);
      arb[ind]=MIN(arb[ind*2],arb[ind*2+1]);
   }
}

int query (int ind, int li, int lf, int A, int B)
{
   int mj;
   if (li>=A && lf<=B) return arb[ind];
   if(lf<A || li>B)
     return INF;
   mj=(li+lf)>>1;
   return MIN( query(2*ind,li,mj,A,B) , query(2*ind+1,mj+1,lf,A,B) );
}


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

     scanf("%d %d",&N,&K);
     for (i=1; i<=N; i++) scanf("%d",a+i);

     buildtree(1,1,N);

     for (i=1; i<=N-K+1; i++) 
      {
    	ANSWER = query(1,1,N,i,i+K-1);
    	if (ANSWER>KBAS)
    	 {
           KBAS=ANSWER;
           in=i;
           out=i+K-1;
         }  
      }
     printf("%d %d %d\n",in,out,KBAS);
     return 0;
}