Cod sursa(job #2550)

Utilizator cos_minBondane Cosmin cos_min Data 17 decembrie 2006 18:50:32
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.63 kb
#include <stdio.h>
#include <fstream>
using namespace std;

#define in "secventa.in"
#define out "secventa.out"
#define dim 500001

int arb[5*dim+1], q[dim];
int n, k, maxim, poz=0;

void Read();
void Q(int nod, int st, int dr, int cs, int cd);
void Update(int nod, int st, int dr, int a);

int main()
{
    Read();
    return 0; 
}

void Read()
{
     int final=-1,ip=0,is=0;
     freopen(in,"r",stdin);
     freopen(out,"w",stdout);
     
     scanf("%d%d",&n,&k);
     
     for ( int i = 1; i <= n; i++ )
     {
         scanf("%d",&q[i]);
         Update(1,1,n,i);
     }
     
     for ( int i = 1; i <= n-k+1; i++ )
     {
         maxim = 34000;
         Q(1,1,n,i,i+k-1);
         if ( maxim > final ) 
         {
              final = maxim;
              ip = i;
              is = i+k-1;
         }
     }
     printf("%d %d %d ",ip,is,final);
}

void Update(int nod, int st, int dr, int a)
{
     if ( st == dr )
     {
          arb[nod] = q[a];
          return;
     } 
     
     int mij = (st+dr)/2;
     if ( a <= mij ) Update(2*nod,st,mij,a);
     if ( a > mij ) Update(2*nod+1,mij+1,dr,a);
     
     if ( arb[2*nod] > arb[2*nod+1] ) arb[nod] = arb[2*nod+1];
     else                             arb[nod] = arb[2*nod];
}

void Q(int nod,int st, int dr, int cs, int cd)
{
     if ( cs <= st && dr <= cd )
     {
          if ( maxim > arb[nod] ) 
          {
               maxim = arb[nod]; 
          }
          return;
     }
     
     int mij = (st+dr)/2;
     
     if ( cs <= mij ) Q(2*nod,st,mij,cs,cd);
     if ( mij < cd  ) Q(2*nod+1,mij+1,dr,cs,cd);
}