Cod sursa(job #341197)

Utilizator Alexa_ioana_14Antoche Ioana Alexandra Alexa_ioana_14 Data 17 august 2009 18:26:56
Problema Secventa Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.19 kb
#include<cstdio>
#define N 500002
#include<algorithm>
using namespace std;
int n,k,v[N],p,u,maxim,sf,inc,d[N],num;
char s[N];
void citire()
{
	freopen("secventa.in","r",stdin);
	freopen("secventa.out","w",stdout);
	scanf("%d%d\n",&n,&k);
	fgets(s,N-1,stdin);
	for (int i=0; num!=n; ++i)
	{
		int nr=0;
		int semn=1;
		if (s[i]=='-')
		{
			semn=-1;++i;
		}
		bool ok=false;
		while(s[i]>='0'&&s[i]<='9'&&s[i])
		{
			nr=nr*10+(s[i]-'0');++i;ok=true;
		}
		if (ok)
		v[++num]=nr*semn;
	}
	//printf("%d",num);
	for (int i=1; i<=k; ++i)   
    {   
        //scanf("%d",&v[i]);   
        while (p!=u&&v[i]<=v[d[u-1]])   
            --u;   
        d[u++]=i;   
    }   
    maxim=v[d[p]];   
    inc=1;sf=k;   
    for (int i=k+1; i<=n; ++i)   
    {   
        //scanf("%d",&v[i]);   
        int g=i-d[p];   
        if (g==k)   
            ++p;   
        while (u!=p&&v[i]<=v[d[u-1]])   
            --u;   
        d[u++]=i;   
        if (maxim<v[d[p]])   
        {   
            maxim=v[d[p]];   
            inc=i-k+1;   
            sf=i;   
        }   
    }   
    printf("%d %d %d",inc,sf,maxim);   
}   

int main()
{
	citire();
	
	return 0;
}