Cod sursa(job #1218547)

Utilizator cojocarugabiReality cojocarugabi Data 11 august 2014 17:29:39
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.89 kb
# include <cstdio>
# include <iostream>
# include <deque>
# define nmax 500005
# define Simax -30005
using namespace std;
int S[nmax];
char c[nmax*10];
deque <int> Q;
int main(void)
{
    int n,k;
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);
    scanf("%d%d\n",&n,&k);
    gets(c+1);
    int j=1;
    for (int i=1;i<=n;++i)
    {
        bool ind=1;
        S[i]=0;
        while (c[j]==' ') ++j;
        if (c[j]=='-') ++j,ind=0;
        while ('0'<=c[j] && c[j]<='9') S[i]=S[i]*10+(c[j]-'0'),++j;
        if (!ind) S[i]=-S[i];
    }
    int Max=Simax;
    int p,u;
    for (int i=1;i<=n;++i)
    {
        while (!Q.empty() && S[i]<=S[Q.back()]) Q.pop_back();
        Q.push_back(i);
        if (Q.front()<=i-k) Q.pop_front();
        if (S[Q.front()]>Max && i>=k) Max=S[Q.front()],p=i-k+1,u=i;
    }
    printf("%d %d %d\n",p,u,Max);
}