Cod sursa(job #928644)

Utilizator CStefanPChitanu Stefan Petru CStefanP Data 26 martie 2013 16:39:07
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include<cstdio>
#include<deque>
#include<cstring>
char s[5000005];
int n,i,j,k,pr,ba,a[500006];
using namespace std;
deque<int> c;
int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d %d\n",&n,&k);
    int max=-999999;
    gets(s);
	char *p=s;
	i=1;
	while (*p)
	{
		bool ok=false;
		if (*p=='-') ok=true,++p;
		while (*p>='0' && *p<='9')
			a[i]=a[i]*10+*p-'0',++p;
		++p;
		if (ok) a[i]=-a[i];
		i++;
	}
    for (i=n;i>=1;i--)
    {
        while((!c.empty())&&(a[c.back()]>a[i])) c.pop_back();
        c.push_back(i);
        if (c.front()>=i+k) c.pop_front();
        if ((a[c.front()]>=max)&&(i<=n-k+1))
        {
            max=a[c.front()];
            pr=c.back();
        }
    }
    printf("%d %d %d",pr,pr+k-1,max);
    return 0;
}