Cod sursa(job #749245)

Utilizator iris88Nagy Aliz iris88 Data 16 mai 2012 11:50:51
Problema Secventa Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.65 kb
#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;
  int currmin = 0;
  baza[n] = INT_MIN;
  maxim =n;
  for (int i=0;i<n-k+1;i=currmin+1)
  {
    currmin =i;
    for (int j=i+1;j<k+i+1;j++)
      if (secv[j]<secv[currmin])
        currmin = j;
    baza[i] = secv[currmin];
    if (baza[i]>baza[maxim])
      maxim = i;
  }
 /* 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;    
      int i =k;
      while (i<n)
      {
        
          heap[heapsize].key = secv[i];
          heap[heapsize].index = i;
          heapifyup(heapsize);
          heapsize++;        
        while (heap[0].index<i-k+1)
        {
          extractmin(heapsize);
        }      
          baza[i] = secv[i];
        if (baza[i]>baza[maxim])
          maxim=i;
        i = heap[0].index+k;
      }
  }
*/
  ofstream g("secventa.out",ios::out);
  g<<maxim+1<<" "<<maxim+k<<" "<<baza[maxim]<<endl;
  g.close();
  return 0;
}