Pagini recente » Cod sursa (job #2408979) | Cod sursa (job #1056598) | Cod sursa (job #71342) | Cod sursa (job #3254792) | Cod sursa (job #1059098)
#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]])
{
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=h[i];
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;
}