Cod sursa(job #749291)

Utilizator iris88Nagy Aliz iris88 Data 16 mai 2012 16:42:15
Problema Secventa Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.96 kb
#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;
}