Cod sursa(job #2544)

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

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

int arb[4*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,pozf=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);
     }
     
     int s=1;
     Q(1,1,n,1,k);
     
     if ( maxim > final ) 
     {
          final = maxim;
          ip = s;
          is = k;
          pozf = poz;
     }
     
     for ( int i = k; i <= n; i++ )
     {
         if ( q[i] > maxim )
         {
              maxim = 34000;
              Q(1,1,n,s+1,i);
              if ( maxim > final && i-s >= k ) 
              {
                    final = maxim;
                    ip = s+1;
                    is = i;
                    pozf = poz;
                    s=poz;
              }
         }
         
     }
     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]; 
               if ( q[st] == maxim ) poz = st;
          }
          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);
}