Cod sursa(job #14024)
#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;
void citire()
{
fin=fopen(infile,"r");
fscanf(fin,"%d %d",&n,&k);
for(int i=0;i<n;i++)
fscanf(fin,"%d",&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;
}