Cod sursa(job #14030)
#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;
}