Pagini recente » Cod sursa (job #749459) | Cod sursa (job #304277) | Cod sursa (job #1145621) | Cod sursa (job #1057926) | Cod sursa (job #749291)
Cod sursa(job #749291)
#include <fstream>
#include <iostream>
#include <limits.h>
#include <time.h>
#include <stdio.h>
using namespace std;
typedef struct heapelem{
int key,index;
}heapelem;
heapelem heap[500001];
int secv[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()
{
FILE *f= fopen("secventa.in","r");
int n,k;
fscanf(f,"%d %d",&n,&k);
for (int i=0;i<n;i++)
fscanf(f,"%d",&secv[i]);
fclose(f);
int maxim;
secv[n] = INT_MIN;
int currmin = -1;
maxim =0;
int maxi = INT_MIN;
int heapsize = 0;
/*for (int i=0;i<n-k+1;i=currmin+1)
{
currmin =i;
int cmin = secv[i];
for (int j=i+1;j<k+i;j++)
if (secv[j]<cmin){
currmin = j;
cmin = secv[j];
}
if (cmin>maxi){
maxim = i;
maxi = cmin;
}
}*/
bool ordered = false;
int i =0;
while (i<n-1 &&ordered)
{
if (secv[i]>secv[i+1])
ordered = false;
}
if (ordered)
{
maxim = n-k;
maxi = secv[n-k];
}
else{
if (k==1)
{
maxim = 0;
maxi=secv[0];
for (int i=1;i<n;i++)
if (secv[i]>maxi) {maxim = i;maxi=secv[i];};
}
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++;}
}
maxim = 0;
maxi = heap[0].key;
int i =heap[0].index+k;
while (i<n)
{
while (heap[0].index<i-k+1)
{
extractmin(heapsize);
}
heap[heapsize].key = secv[i];
heap[heapsize].index = i;
heapifyup(heapsize);
heapsize++;
if (heap[0].key>maxi){
maxim=i-k+1;
maxi = heap[0].key;
}
i++;
}
}
}
ofstream g("secventa.out",ios::out);
g<<maxim+1<<" "<<maxim+k<<" "<<maxi<<endl;
g.close();
return 0;
}