Cod sursa(job #2028820)

Utilizator victoreVictor Popa victore Data 28 septembrie 2017 18:30:29
Problema Secventa Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.2 kb
#include <cstdio>
#include<queue>
#include<cstring>

using namespace std;

typedef pair<int,int> ii;
deque <ii> q;


const int nmax=500005;
const int buffmax=3500005;


char s[buffmax];

inline bool isnum(char ch)
{
    return (ch >= '0' && ch <= '9');
}

int main()
{
    freopen("secventa.in","r",stdin);
    freopen("secventa.out","w",stdout);

    int n,i,k,l,lmax,x,baza,bazmax,a=1,b=1,ind;

    scanf("%d%d\n",&n,&k);

    gets(s+1);
    n=strlen(s+1);
    int semn=1;

    for(ind=1,i=1;i<=n;i++,ind++)
    {
        semn=1;
        x=0;
        for(;i<=n && s[i] == ' ';++i);

        if(s[i] =='-')
            semn=-1,++i;

        for(;i<=n && isnum(s[i]);++i)
            x = x*10 + (s[i] - '0');

        x*=semn;

        while(!q.empty()&&q.back().first>=x)
            q.pop_back();
        while(!q.empty()&&ind-q.front().second+1>k)
            q.pop_front();
        q.push_back(ii(x,ind));
        baza=q.front().first;
        if(i>=k)
        {
            if(baza>bazmax || ind==k)
            {
                bazmax=baza;
                a=ind-k+1;
                b=ind;
            }
        }
    }
    printf("%d %d %d",a,b,bazmax);
}