Cod sursa(job #329060)

Utilizator hasegandaniHasegan Daniel hasegandani Data 4 iulie 2009 16:13:08
Problema Secventa Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.39 kb
#include<stdio.h>

#define Nmax 50001

int n,k,a[Nmax],St[Nmax],cui[Nmax],poz[Nmax],max,p1,p2;

void qsort(int,int);
void swap(int,int);

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d",&n,&k);
    for(int i=1;i<=k;++i)
        {
        scanf("%d",&a[i]);
        St[i]=a[i];
        poz[i]=i;
        cui[i]=i;
        }
    qsort(1,k);
    max=St[1]; p1=1; p2=k;
    
    for(int i=k+1;i<=n;++i)
        {
        scanf("%d",&a[i]);
        
        St[poz[i-k]]=a[i];
        poz[i]=poz[i-k];
        cui[poz[i]]=i;

	while (St[poz[i]]<St[poz[i]-1] && poz[i]>=0)
	    swap(poz[i],poz[i]-1);
	while (St[poz[i]]>St[poz[i]+1] && poz[i]+1<=k)
            swap(poz[i],poz[i]+1);
            
        if (max<St[1])
            {
            max=St[1];
            p1=i-k+1;
            p2=i;
            }
        }

    printf("%d %d %d\n",max,p1,p2);
    
    return 0;
}

void qsort(int in,int sf)
{
    int x=in-1;

    for(int i=in;i<=sf;++i)
	if (St[i]<=St[sf])
            swap(i,++x);
    
    if (in<x-1) qsort(in,x-1);
    if (x+1<sf) qsort(x+1,sf);
}

void swap(int i,int j)
{
    int aux;
    
    aux=St[i];
    St[i]=St[j];
    St[j]=aux;
    
    aux=cui[i];
    cui[i]=cui[j];
    cui[j]=aux;
    
    aux=poz[cui[i]];
    poz[cui[i]]=poz[cui[j]];
    poz[cui[j]]=aux;
}