Cod sursa(job #1059105)

Utilizator radu2004GOLD radu radu2004 Data 16 decembrie 2013 10:22:05
Problema Secventa Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.09 kb
#include <stdio.h>

using namespace std;
int h[500002],a[500001],poz[500001],k,i,nr,n,max1,st,sf;
FILE *f,*g;
void swap (int i,int j)
{
    int aux;
    aux=h[i];
    h[i]=h[j];
    h[j]=aux;
    poz[h[i]]=i;
    poz[h[j]]=j;
}
void up (int k)
{
   int t=k/2;
    if (a[h[t]]>a[h[k]] && t>=1)
    {
        swap (t,k);
        up (t);
    }
}
void dw (int k)
{
    int st=k*2;
    if (st<=nr)
    {
        if (a[h[st]]>a[h[st+1]] && st+1<=n) st++;
        if (a[h[st]]<a[h[k]])
        {
            swap (st,k);
            dw (st);
        }
    }
}
int main()
{f=fopen ("secventa.in","r");
 g=fopen ("secventa.out","w");
 fscanf (f,"%d%d",&n,&k);
 for (i=1;i<=n;i++) fscanf (f,"%d",&a[i]);
 for (i=1;i<=k;i++)
  {
      h[++nr]=i;
      poz[i]=nr;
      up(nr);
  }
 max1=a[h[1]];
 st=1;
 sf=k;
 for (i=k+1;i<=n;i++)
 {
     h[poz[i-k]]=i;
     poz[i]=poz[i-k];
     up (poz[i]);
     dw (poz[i]);
     if (a[h[1]]>max1)
     {
         max1=a[h[1]];
         st=i-k+1;
         sf=i;
     }
 }
fprintf (g,"%d %d %d",st,sf,max1);
    return 0;
}