Cod sursa(job #2516)

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

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

int arb[dim], q[dim];
int n, k, maxim;

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,is;
     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);
         for ( int j = i+k-1; j <= n; j++ )
         {
             if ( q[j] > maxim && j >= i+k ) continue;
            // printf("%d %d\n",i,j);
             if ( maxim > final ) 
             {
                  final = maxim;
                  ip = i;
                  is = j;
             }
         }
     }
     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);
}