Cod sursa(job #779199)

Utilizator ionut_blesneagIonut Blesneag ionut_blesneag Data 16 august 2012 23:35:16
Problema Secventa Scor 60
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<fstream>
using namespace std;

ifstream f("secventa.in");
ofstream g("secventa.out");

const int inf=30001;
int N,K,i,minim,MaxBasis,PozAbsolut,size;
int h[500001],poz[500001];
int v[500002];

void swap(int a, int b)
{int aux=h[a];
h[a]=h[b];
h[b]=aux;
}

void sink(int x)
{int son;
do{son=0;
if(2*x<=size)
   {son=2*x;
    if((2*x+1)<=size && v[h[2*x+1]]<v[h[2*x]])
      son=2*x+1;}
if(son && v[h[x]]>v[h[son]]) 
  {poz[h[x]]=son;
   poz[h[son]]=x;
  swap(x,son);
  x=son;}
else
 son=0;   
   }while(son);
}


void swim(int x)
{int father;
do{father=0;
if(x/2>=1)
  father=x/2;
if(father && v[h[father]]>v[h[x]])
 {poz[h[x]]=father;
  poz[h[father]]=x;
 swap(x,father);
 x=father;}
else
 father=0;  
   }while(father);
}


int main()
{f>>N>>K;
MaxBasis=-inf;
for(i=1; i<=N; i++)
  {f>>v[i];
   size++;
   h[size]=i;
   poz[i]=size;
   swim(size);
   if(size>K)
     {poz[h[size]]=poz[i-K];
      swap(poz[i-K],size);
      size--;
      sink(poz[i-K]);
      if(v[h[1]]>MaxBasis)
      {MaxBasis=v[h[1]];
       PozAbsolut=i;} 
       }
  }   
  
g<<PozAbsolut-K+1<<" "<<PozAbsolut<<" "<<MaxBasis;  
f.close();
g.close();
return 0;}