Cod sursa(job #289413)

Utilizator DraStiKDragos Oprica DraStiK Data 26 martie 2009 18:51:35
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.05 kb
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#define DIM 500005
#define INF -30005
int a[DIM],b[DIM];
char c[DIM/10000*DIM];
int n,k,nrt,in,t;
void read ()
{
	int i,nr=0,ok=1;
	scanf ("%d%d\n",&n,&k);
	gets (c);
	t=strlen (c);
	n=0;
	for (i=0; i<t; ++i)
		if (isdigit (c[i]))
			nr=nr*10+c[i]-'0';
		else if (c[i]=='-')
			ok=-1;
		else
		{
			a[++n]=nr*ok;
			nr=0;
			ok=1;
		}
	if (nr)
		a[++n]=nr;
}
void solve ()
{
    int st=1,dr=0,i;
    for (i=1; i<k; ++i)
    {
        while (st<=dr && a[i]<=a[b[dr]])
            --dr;
        b[++dr]=i;
    }
    for (i=k, nrt=INF; i<=n; ++i)
    {
        while (st<=dr && a[i]<=a[b[dr]])
            --dr;
        b[++dr]=i;
        while (st<=dr && b[st]<i-k+1)
            ++st;
        if (a[b[st]]>nrt)
        {
            nrt=a[b[st]];
            in=i;
        }
    }
    printf ("%d %d %d",in-k+1,in,nrt);
}
int main ()
{
	freopen ("secventa.in","r",stdin);
	freopen ("secventa.out","w",stdout);
    read ();
    solve ();
    return 0;
}