Pagini recente » Cod sursa (job #2850228) | Cod sursa (job #667827) | Cod sursa (job #2121228) | Cod sursa (job #376510) | Cod sursa (job #347231)
Cod sursa(job #347231)
#include <fstream>
#define fin "secventa.in"
#define fout "secventa.out"
#define nMax 500001
#define Inf 30001
using namespace std;
int n,k,poz,pozs,maximum=-Inf;
int s[nMax], mheap[nMax], c[nMax];
void citeste(){
fstream in(fin, ios::in);
in>>n>>k;
for(int i=1;i<=n;i++)
in>>s[i];
in.close();
}
void combina(int i, int len){
int tata, fiu, aux;
tata=i; fiu=2*i;
while(fiu<=len){
if(fiu+1<=len)
fiu=(mheap[fiu]<mheap[fiu+1])?fiu:fiu+1;
if(mheap[tata]>mheap[fiu]){
aux=mheap[tata];
mheap[tata]=mheap[fiu];
mheap[fiu]=aux;
tata=fiu; fiu*=2;
}else break;
}
}
void do_heap(){
for(int i=1;i<=k;i++)
mheap[i]=s[i];
combina(1,k);
c[1]=mheap[1];
maximum=c[1], poz=1;
}
void Secventa(){
do_heap();
for(int i=2;i<=n-k+1;i++){
for(int j=1;j<=k;j++)
if(mheap[j]==s[i-1])
mheap[j]=s[i];
combina(1,k);
c[i]=mheap[1];
if(maximum<c[i])
maximum=c[i],poz=i;
}
pozs=poz+k;
while(s[pozs]>=maximum&&pozs<=n) pozs++;
}
void tipar(){
fstream out(fout,ios::out);
out<<poz<<" "<<--pozs<<" "<<maximum<<endl;
out.close();
}
int main(void){
citeste();
Secventa();
tipar();
return 0;
}