Cod sursa(job #14030)

Utilizator stef2nStefan Istrate stef2n Data 8 februarie 2007 02:18:14
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <stdio.h>

#define infile "secventa.in"
#define outfile "secventa.out"
#define NMAX 500005

FILE *fin,*fout;
int n,k;
int N=0,x[NMAX],heap[NMAX],pozheap[NMAX];
int baza=-35000,start=-1;
char sir[NMAX*10];

void citire()
  {
   int j=0,semn;
   fin=fopen(infile,"r");
   fscanf(fin,"%d %d\n",&n,&k);
   fgets(sir,sizeof(sir),fin);
   for(int i=0;i<n;i++)
      {
       semn=0;
       x[i]=0;
       while(sir[j]!='-' && (sir[j]<'0' || sir[j]>'9'))
            j++;
       if(sir[j]=='-')
         semn=1;
       while(sir[j]>='0' && sir[j]<='9')
            {
             x[i]=x[i]*10+(sir[j]-'0');
             j++;
            }
       if(semn)
         x[i]=-x[i];
      }
   fclose(fin);
  }

void scriere()
  {
   fout=fopen(outfile,"w");
   fprintf(fout,"%d %d %d\n",start+1,start+k,baza);
   fclose(fout);
  }

void ridica(int poz)
  {
   int aux;
   while(poz>1)
        {
         if(x[heap[poz]] >= x[heap[poz/2]])
           return;
         pozheap[heap[poz]]=poz/2;
         pozheap[heap[poz/2]]=poz;
         aux=heap[poz];
         heap[poz]=heap[poz/2];
         heap[poz/2]=aux;
         poz/=2;
        }
  }

void scufunda(int poz)
  {
   while(2*poz<=N)
        {
         int minpoz=poz,aux;
         if(x[heap[poz]]>x[heap[2*poz]])
           minpoz=2*poz;
         if(2*poz+1<=N && x[heap[minpoz]]>x[heap[2*poz+1]])
           minpoz=2*poz+1;
         if(minpoz==poz)
           return;
         pozheap[heap[poz]]=minpoz;
         pozheap[heap[minpoz]]=poz;
         aux=heap[poz];
         heap[poz]=heap[minpoz];
         heap[minpoz]=aux;
         poz=minpoz;
        }
  }

void solve()
  {
   int i;
   for(i=0;i<k;i++)
      {
       heap[++N]=i;
       pozheap[i]=N;
       ridica(N);
      }
   start=0;
   baza=x[heap[1]];
   for(i=k;i<n;i++)
      {
       // adauga in heap
       heap[++N]=i;
       pozheap[i]=N;
       ridica(N);
       // sterge din heap
       heap[pozheap[i-k]]=heap[N];
       pozheap[heap[N]]=pozheap[i-k];
       N--;
       scufunda(pozheap[i-k]);
       // verifica solutie
       if(baza<x[heap[1]])
         {
          baza=x[heap[1]];
          start=i-k+1;
         }
      }
  }


int main()
{
citire();
solve();
scriere();
return 0;
}