Cod sursa(job #299666)

Utilizator blasterzMircea Dima blasterz Data 6 aprilie 2009 22:08:23
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.11 kb
using namespace std;
#include<cstdio>
#define nmax 500001
#define inf 0x3f3f3f3f
#define dim 8192

char ax[dim];
int pz;

inline void cit(int &x)
{
    x=0;
    while((ax[pz] < '0' || ax[pz] > '9') && ax[pz] != '-')
	if(++pz == dim) fread(ax,1,dim,stdin),pz=0;

    int neg=0;

    if(ax[pz] == '-')
    {
	neg=1;
	if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
    }

    while(ax[pz] >= '0' && ax[pz] <= '9')
    {
	x=x*10+ax[pz]-'0';
	if(++pz == dim) fread(ax,1,dim,stdin),pz=0;
    }

    if(neg) x=-x;
}


int v[nmax],s,f,max,in,n,k,a[nmax];

void read()
{   
    int i;
    freopen("secventa.in","r",stdin);
//    scanf("%d%d",&n,&k);
    cit(n);cit(k);
    for(i=1;i<=n;i++)
	cit(a[i]);
	//scanf("%d",&a[i]);
}

int main()
{
    read();
    s=1;f=0;int i;
    v[++f]=1;
    for(i=2;i<k;i++)
    {
	while(s<=f && a[i]<=a[v[f]]) f--;
	v[++f]=i;
    }
    max=-inf;
    for(i=k;i<=n;i++)
    {
	while(s<=f && a[i]<=a[v[f]]) f--;
	v[++f]=i;
	while(s<=f && v[s]<=i-k)   s++;
	if(a[v[s]]>max)
	{
	    max=a[v[s]];
	    in=i-k+1;;
	}
    }
    freopen("secventa.out","w",stdout);
    printf("%d %d %d\n",in,in+k-1,max);
    return 0;
}