Pagini recente » Cod sursa (job #2314643) | Cod sursa (job #2514843) | Cod sursa (job #1120755) | Cod sursa (job #2453540) | Cod sursa (job #749216)
Cod sursa(job #749216)
#include <fstream>
#include <iostream>
#include <limits.h>
using namespace std;
typedef struct heapelem{
int key,index;
}heapelem;
heapelem heap[500001];
int secv[500001];
int baza[500001];
void heapify(int k,int n)
{
while (k<n){
int l = 2*k+1;
int r = 2*k+2;
int max = k;
if (l<n && heap[l].key<heap[k].key) max = l;
if (r<n && heap[r].key<heap[max].key) max= r;
if (max!=k)
{
int aux = heap[k].key;
heap[k].key=heap[max].key;
heap[max].key=aux;
aux = heap[k].index;
heap[k].index=heap[max].index;
heap[max].index=aux;
k=max;
}
else return;
}
}
void heapifyup(int k)
{
while (k>0 && heap[k].key<heap[(k-1)/2].key)
{
int max = (k-1)/2;
int aux = heap[k].key;
heap[k].key=heap[max].key;
heap[max].key=aux;
aux = heap[k].index;
heap[k].index=heap[max].index;
heap[max].index=aux;
k = (k-1)/2;
}
}
heapelem* extractmin(int &n)
{
int k=0;
int max = (n-1);
int aux = heap[k].key;
heap[k].key=heap[max].key;
heap[max].key=aux;
aux = heap[k].index;
heap[k].index=heap[max].index;
heap[max].index=aux;
n--;
heapify(0,n);
return &heap[n];
}
int main()
{
ifstream f("secventa.in",ios::in);
int n,k;
f>>n>>k;
for (int i=0;i<n;i++)
f>>secv[i];
int heapsize = 0;
f.close();
int maxim;
secv[n] = INT_MIN;
if (k==1)
{
maxim = secv[0];
for (int i=1;i<n;i++)
if (secv[i]>secv[maxim]) maxim = secv[i];
baza[maxim] = secv[maxim];
}
else{
for (int i=0;i<k;i++)
{
if (secv[i]<secv[i+1]){
heap[heapsize].key=secv[i];
heap[heapsize].index = i;
heapifyup(heapsize);
heapsize++;}
baza[i]=heap[0].key;
}
maxim = k-1;
for (int i=k;i<n;i++)
{
if (secv[i]<secv[i+1]){
heap[heapsize].key = secv[i];
heap[heapsize].index = i;
heapifyup(heapsize);
heapsize++;
}
while (heap[0].index<i-k+1)
{
extractmin(heapsize);
}
if (secv[i]>heap[0].key)
baza[i] = heap[0].key;
else
baza[i] = secv[i];
if (baza[i]>baza[maxim])
maxim=i;
}
}
ofstream g("secventa.out",ios::out);
g<<maxim-k+2<<" "<<maxim+1<<" "<<baza[maxim]<<endl;
g.close();
return 0;
}