Cod sursa(job #33764)

Utilizator cos_minBondane Cosmin cos_min Data 19 martie 2007 19:52:08
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.76 kb
#include <stdio.h>
#include <fstream>
using namespace std;

#define in "secventa.in"
#define out "secventa.out"
#define dim 500001
#define dimi 500001*6+500001

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

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=-34000,ip=0,is=0;
    // freopen(in,"r",stdin);
     freopen(out,"w",stdout);
     FILE *fin = fopen(in,"r");
     
     fscanf(fin,"%d%d",&n,&k);
     fscanf(fin,"\n");
     
    /* for ( int i = 1; i <= n; i++ )
     {
        scanf("%d",&q[i]);
        Update(1,1,n,i);
         /*if ( i-k >= 0 )
         {
              maxim = 34000;
              Q(1,1,n,i-k+1,i);
              if ( maxim > final ) 
              {
                 final = maxim;
                 ip = i-k+1;
                 is = i;
              }
         }
     }*/
     
     fscanf(fin,"\n");
        int j = 0;
        int minus=1;
        int v = 0;
        int aux=0;
        
        fgets(linie,dimi,fin);
        
        while ( linie[j] != '\n' )
        {
              if ( linie[j] == ' ' )
              {
                   aux *= minus;
                   v += 1;
                   q[v] = aux;
                   aux=0;
                   minus = 1;
                   Update(1,1,n,v);
              } 
              else if ( linie[j] == '-' ) minus = -1;
              else
              {
                  aux *= 10;
                  aux += (int)linie[j] - 48;
              }
              
              j++;
        }
        
        q[n] = aux*minus;
        Update(1,1,n,n);
     
     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);
}